我刚刚看了一下斗维基百科页面排序。在这篇文章中，他们说，最坏的情况下复杂度为O（N²）。但我认为最坏的情况下复杂度为O（n + k），其中k为桶的数量。这是我如何计算这种复杂性：

I just read the Wikipedia page about Bucket sort. In this article they say that the worst case complexity is O(n²). But I thought the worst case complexity was O(n + k) where k are the number of buckets. This is how I calculate this complexity:

我缺少的东西？

推荐答案

如果该算法决定了每个元素在同一个桶所属？在这种情况下，需要每一个元素被添加时间待运行链表在于桶。这需要1步，则2，则3，4，5 ...的 N 的。因此，时间是所有数字的总和为1至 N 的其中为（n ^ 2 + N）/ 2，这是O（n ^ 2）。

What if the algorithm decides that every element belongs in the same bucket? In that case, the linked list in that bucket needs to be traversed every time an element is added. That takes 1 step, then 2, then 3, 4, 5... n . Thus the time is the sum of all of the numbers from 1 to n which is (n^2 + n)/2, which is O(n^2).

当然，这是最坏的情况（在一个桶中的所有元素） - 该算法来计算把它桶元素通常被设计来避免这种行为

Of course, this is "worst case" (all the elements in one bucket) - the algorithm to calculate which bucket to place an element is generally designed to avoid this behavior.