如果我们使用链表实现存储桶,那么存储桶排序的复杂性如何是O(n + k)？

Question

我很好奇为什么如果我们使用链接列表实现的存储桶,则存储桶排序的运行时间为O(n + k).例如,假设我们有这个输入:

n = no of element= 8
k = range = 3

array = 2,2,1,1,1,3,1,3

桶将如下所示:

1: 1 -> 1 -> 1 -> 1
2: 2 -> 2
3: 3 -> 3

插入这些桶的总时间是O(n),假设我们在链表中存储尾指针.

要删除,我们必须转到每个存储桶,然后删除该存储桶中的每个节点.因此,当我们遍历每个链表时,复杂性应该是O(K*桶的链接列表的平均长度).

但是,我读到了bucket sort的复杂性是O(n + k).为什么这不符合我的分析？请更正我,因为我仍在学习计算复杂性.

Answer 1

您的分析几乎是正确的,但有一个重要的细节,你错过了.

现在,你是正确的,迭代输入数组以将元素分配到存储桶需要时间O(n).但是,如果您说组装阵列所需的总时间为O(k*(每个桶的平均元素数)),则略微偏离.注意,因为有n个元素和k个桶,对于O(n)的总运行时间,这将出现O(k*(n/k))= O(n).要知道为什么真正的答案是O(n + k),我们需要更仔细地研究那个大O项.

对于初学者来说,你绝对正确的是你在每个桶上花费的平均时间是O(n/k).然后你说因为有k个桶,所以总运行时间是O(k*(n/k))= O(n).然而,这是不正确的:特别是,k*O(n/k)= O(n)并非如此.其原因是术语O(n/k)隐藏了一个常数因子.当您访问每个桶并查看它包含的元素时,它不会花费n/k时间,甚至不需要n/k时间的常数倍.例如,如果存储桶为空,会发生什么？在这种情况下,您仍然需要花费一些时间来查看存储桶,因为您必须确定不应该迭代它的元素.因此,每个桶所需时间的更精确表示类似于c ₀(n/k)+ c ₁,其中c ₀和c ₁是特定于实现的常量.该表达式当然是O(n/k).

捕获是将此表达式乘以k以获得完成的工作总量时发生的情况.如果你计算

k*(c ₀(n/k)+ c ₁)

你得到

c ₀ n + c ₁ k

如您所见,此表达式直接取决于k,因此总运行时间为O(n + k).

得出这个结果的更直接的方法是查看桶排序的第二步的代码,如下所示:

For each bucket b:
    For each element x in b:
        Append x to the array.

整体做了多少工作？好吧,有k个不同的桶,所以最外面的循环必须至少花费O(k)时间,因为我们必须查看每个桶.在内部,内部循环总共执行O(n)次,因为总共有n个元素分布在桶中.从这里,我们得到O(n + k)总运行时间.

这很重要的原因在于,这意味着如果您尝试使用大量存储桶(例如,大于n)进行存储桶排序,则运行时可能会被扫描所有存储桶所需的时间占据主导地位您实际使用的桶,即使它们中的大多数都是空的.基数排序有用的原因是它使用多次重复的桶排序,其中只有两个桶,它们在时间O(n + 2)= O(n)中运行.因为你只需要进行O(lg U)迭代(其中U是数组中的最大值),运行时是O(n lg U)而不是你从桶中得到的O(n + U)排序,这更糟糕.

希望这可以帮助!