如果我们使用链表实现存储桶，存储桶排序的复杂度如何为O（n + k）？

如果我们使用链表实现存储桶，存储桶排序的复杂度如何为O（n + k）？

您的分析 几乎 是正确的，但是您缺少一个重要的细节。

现在，您是正确的，遍历输入数组以将元素分布到存储桶中需要花费时间O（n）。但是，当您说组装数组所需的总时间为O（k
（每个存储桶中的平均元素数））时，您的情况会稍微有些偏离。请注意，由于存在n个元素和k个存储桶，因此总运行时间为O（n），这将得出O（k （n /
k））= O（n）。要了解为什么真正的答案是O（n + k），我们需要更仔细地看一下big-O项。

对于初学者，您绝对正确，您在每个存储分区上花费的平均时间为O（n / k）。然后，您说由于有k个存储桶，因此总运行时间为O（k （n / k））=
O（n）。但是，这是不正确的：特别是k * O（n / k）= O（n）
并非* 正确。这是因为项O（n /
k）隐藏了一个常数因子。当您访问每个存储桶并查看其中包含的元素时，它并不需要n / k时间，甚至不需要n /
k时间的某个常数倍。例如，如果存储桶为空会怎样？在那种情况下，您仍然要花一些时间在存储桶上，因为您必须确定不应迭代其元素。0（n / k）+ c 1，其中c
0和c 1是特定于实现的常量。该表达式当然是O（n / k）。

当您将此表达式乘以k以获取完成的工作量时，就会发生问题。如果你计算

k *（c 0（n / k）+ c 1）

你得到

c 0 n + c 1 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）排序，这更糟。

希望这可以帮助！