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

In order to merge the buckets, they first need to be sorted. Consider the pseudocode given in the Wikipedia article:

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]

The nextSort(buckets[i]) sorts each of the individual buckets. Generally, a different sort is used to sort the buckets (i.e. insertion sort), as once you get down and size, different, non-recursive sorts often give you better performance.

Now, consider the case where all n elements end up in the same bucket. If we use insertion sort to sort individual buckets, this could lead to the worst case performance of O(n^2). I think the answer must be dependent on the sort you choose to sort the individual buckets.

于 2012-03-20T17:53:26.297 に答える
2

すべての要素が同じバケットに属するとアルゴリズムが判断した場合はどうなりますか？その場合、要素が追加されるたびに、そのバケット内のリンクリストをトラバースする必要があります。それは1ステップ、次に2、次に3、4、5... nを取ります。したがって、時間は1からnまでのすべての数値の合計であり、 （n ^ 2 + n）/ 2、つまりO（n ^ 2）です。

もちろん、これは「最悪の場合」（1つのバケット内のすべての要素）です。要素を配置するバケットを計算するアルゴリズムは、通常、この動作を回避するように設計されています。

于 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 に答える