3

カウントソートはバケツソートの一種です。次のように使用しているとしましょう。

  • Aソートする配列にしましょう
  • 最大k要素とする
  • bucket[]バケットの配列にしましょう
  • 各バケットをリンクされたリストにします (開始ポインターと終了ポインターを使用)。

次に、疑似コードでは、ソートのカウントは次のようになります。

Counting-Sort (A[], bucket[], k)

1.  Init bucket[]
2.  for i -> 1 to n
3.        add A[i] to bucket[A[i].key].end
4.  for i -> 1 to k
5.        concatenate bucket[i].start to bucket[0].end
6.        bucket[0].end=bucket[i].end
7.  copy bucket[0] to A

行ごとの時間の複雑さ:

1）O（1）で配列を初期化する方法（単純ではありませんが方法）があることは知っています

2,3) O(n)

4,5) O(k)

6) O(n)

これにより、O(k+n) の正味ランタイムが得られます。これは、k >> n の場合は Ω(n) であり、これは私たちにとって悪いことです。しかし、行 4、5 を変更して空のバケットをスキップできるとしたらどうでしょうか? このようにして、k が何であるかを無視して O(n) を持つことになります。

誰もこれを行う方法を知っていますか? それとも無理ですか？

4

2 に答える 2

1

1 つのオプションは、実際に使用されているバケットを含む補助 BST を保持することです。バケットに何かを追加するときはいつでも、それがそこに配置される最初のエントリである場合は、そのバケットの値も BST に追加します。

すべてを連結したい場合は、BST を並べ替えた順序で反復処理し、見つけたバケットだけを連結することができます。

実際に使用される z 個のバケットがある場合、これには O(n + z log z) かかります。バケットの数が実際に使用される数と比較して多い場合、これははるかに高速になる可能性があります。

より一般的には、O(f(z)) 時間で使用されている z 個の異なるバケットをソートする方法があれば、O(n + f(z)) 時間でバケットソートを行うことができます。実際に使用するバケットの 2 番目の配列を維持し、初めて使用するときにバケットを配列に追加します。バケットを反復処理する前に、使用中のバケットのインデックスを O(f(z)) 時間で並べ替え、その配列全体を反復処理して、アクセスするバケットを決定します。たとえば、y-Fast ツリーを使用した場合、O(n + z log log z) で並べ替えることができます。

お役に立てれば！

于 2011-08-31T22:42:08.953 に答える
0

バケット配列を連想配列に変換すると、O（n log n）が得られますが、（平均して）並べ替えの場合よりもうまくいくとは思いません。

一般的な場合、 O（n）は不可能です。

于 2011-08-31T22:44:49.110 に答える