python-3.x - 为什么桶排序的时间复杂度是 O(n^2) 而不是 O(log(n) * n^2)?
问题描述
import math
def insertionSort(arr):
for i in range(len(arr)-1):
for j in range(i+1, len(arr)):
if arr[j] < arr[i]:
arr[j], arr[i] = arr[i], arr[j]
return arr
def bucketSort(arr):
no_of_buck = round(math.sqrt(len(arr)))
bucketArr = [[] for _ in range(no_of_buck)]
n = len(bucketArr)
maximumVal = max(arr)
for i in arr:
appropriate_bucket = math.ceil(i * n / maximumVal)
bucketArr[appropriate_bucket-1].append(i)
for i in bucketArr:
i = insertionSort(i)
arr = []
for i in bucketArr:
arr.extend(i)
print(arr)
插入排序本身是一个 O(n^2) 操作,外循环上升到元素数量的平方根,即 O(sqrt(n)),所以它应该是 O(log(n) * n^2)
解决方案
插入排序本身是一个 O(n^2) 操作,外循环上升到元素数量的平方根,即 O(sqrt(n)),所以它应该是 O(log(n) * n^2)
您已经给出了一个论点,为什么时间复杂度可能是 O(n 2.5 ),而不是 O(log(n) * n^2),尽管有一个相对简单的原因为什么它们都不是严格的上限(宽松的上限没有错,但没那么有趣,在某些情况下可能被视为错误)。
项目总数仍然只有n
.
在最坏的情况下,所有项目都在一个桶中,这就是 O(n²) 时间复杂度的来源。所有其他项目在桶上的分布都更好。桶不可能都很大,这是您的论点隐含的假设。
这就是为什么“乘以嵌套循环的时间复杂度”的经验法则只是经验法则的一个例子。