8

我刚刚阅读了有关Bucket sort的维基百科页面。在这篇文章中，他们说最坏情况的复杂度是 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)

我错过了什么吗？

4

5 回答 5

10

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

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). 我认为答案必须取决于您选择对各个存储桶进行排序的排序。

于 2012-03-20T17:53:26.297 回答
2

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

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

于 2012-03-20T17:48:24.683 回答
2

如果您可以保证每个桶代表一个唯一值（等效项），那么正如您所指出的，最坏情况的时间复杂度将是 O(m+n)。

于 2012-03-20T17:56:42.853 回答
1

桶排序假设输入来自均匀分布。这意味着每个存储桶中都有一些项目。反过来，这会导致 O(n) 的良好平均运行时间。实际上，如果在每个桶中插入 n 个元素，使得 O(1) 个元素落在每个不同的桶中（插入需要每个项目 O(1)），那么使用插入排序对桶进行排序平均需要 O(1)以及（几乎所有关于算法的教科书都证明了这一点）。由于您必须对 n 个桶进行排序，因此平均复杂度为 O(n)。

现在，假设输入不是从均匀分布中提取的。正如@mfrankli 已经指出的那样，在最坏的情况下，这可能会导致所有项目都落在例如第一个桶中的情况。在这种情况下，插入排序在最坏的情况下需要 O(n^2)。

请注意，您可以使用以下技巧来保持相同的平均 O(n) 复杂度，同时在最坏的情况下提供 O(n log n) 复杂度。与其使用插入排序，不如在最坏的情况下简单地使用复杂度为 O(n log n) 的算法：合并排序或堆排序（但不是快速排序，平均仅实现 O(n log n)）。

于 2012-03-20T19:54:27.470 回答
1

这是@perreal 的附加答案。我试图将它作为评论发布，但它太长了。@perreal 正确地指出了桶排序何时最有意义。不同的答案对正在排序的数据做出不同的假设。例如，如果要排序的键是字符串，那么可能的键的范围将太大（大于桶数组），我们将不得不只使用字符串的第一个字符作为桶位置或其他策略。必须对各个桶进行排序，因为它们保存具有不同键的项目，导致 O(n^2)。

但是如果我们对键是已知范围内的整数的数据进行排序，那么桶总是已经排序，因为桶中的键是相等的，这导致了线性时间排序。不仅桶是排序的，而且排序是稳定的，因为我们可以按照添加的顺序从桶数组中拉出项目。

我想补充的是，如果由于要排序的键的性质而面临 O(n^2)，则桶排序可能不是正确的方法。当您有一系列与输入大小成正比的可能键时，您可以通过让每个桶只保存一个键的值来利用线性时间桶排序。

于 2018-01-02T20:42:22.340 回答