铲斗分类的最坏情况复杂度是多少？

Question

我刚读了关于Bucket sort的Wikipedia页面.在本文中,他们说最坏的情况是O(n²).但我认为最坏的情况复杂性是O(n + k),其中k是桶的数量.这就是我计算这种复杂性的方法:

1. 将元素添加到存储桶.使用链表这是O(1)
2. 浏览列表并将元素放入正确的存储桶= O(n)
3. 合并桶= O(k)
4. O(1)*O(n)+ O(k)= O(n + k)

我错过了什么吗？

Answer 1

为了合并桶,首先需要对它们进行排序.考虑维基百科文章中给出的伪代码:

function bucketSort(array, n) is
  buckets ? new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

对nextSort(buckets[i])每个桶进行分类.通常,使用不同的排序来对存储桶进行排序(即插入排序),因为一旦您关闭并调整大小,不同的非递归排序通常会为您提供更好的性能.

现在,考虑所有n元素最终都在同一个桶中的情况.如果我们使用插入排序来对各个桶进行排序,这可能会导致最糟糕的情况O(n^2).我认为答案必须取决于您选择对各个存储桶进行排序的排序.

Answer 2

如果算法判定每个元素都属于同一个桶怎么办？那么每次添加元素时都需要遍历该桶中的链表。这需要 1 步，然后 2 步，然后 3,4,5... n。因此，时间是从 1 到n的所有数字之和，即 (n^2 + n)/2，即 O(n^2)。

当然，这是“最坏的情况”（所有元素都在一个桶中）——计算将元素放置在哪个桶中的算法通常旨在避免这种行为。