如果我们使用链表实现桶排序，那么桶排序的复杂度是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 *桶链表的平均长度)。

然而，我读到桶排序的复杂度是O(n + k)，为什么这与我的分析不一致?请纠正我，因为我还在学习计算复杂性。

Answer 1

你的分析几乎是正确的，但是你漏掉了一个重要的细节。

现在，您是正确的，遍历输入数组以将元素分配到bucket中需要花费O(n)时间。但是，当您说组装数组所需的总时间为O(k *(每个桶的平均元素数))时，您就有点错了。请注意，因为有n个元素和k个桶，这将得到O(k * (n/k)) = O(n)，总的运行时间为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的常数倍的时间。例如，如果桶是空的会发生什么?在这种情况下，您仍然需要花费一些时间来查看bucket，因为您必须确定不应该对其元素进行迭代。因此，每个桶所需时间的更准确表示形式是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)，这要差得多。

希望这对你有帮助!