本で与えられているように、基数ソートは一般に LSB から MSB に行われます。しかし、MSB から LSB を使用することで、入力要素をより小さなパーティションに分割できると思います。次に、MSB ファースト基数ソートが LSB ファースト基数ソートよりも漸近的に悪化する可能性があることを示す例を作成する必要があります。これは私の割り当ての問題です。
1829 次
2 に答える
1
ソートの範囲を [1, n2] とします。つまり、[1, n] の範囲でバケットのソートを 2 回適用する必要があります。MSB ファースト ソートを使用する場合、制限時間は ∑(i=1 to n) O(ni +n) です。ここで、ni は (MSB の) バケット内の要素の数です。LSB の範囲は [1, n] です。また、[1, n] の範囲で m 個の数値を並べ替えるには、O(m + n) の時間がかかります。∑(i=1 to n) O(ni +n) = n + ∑(i=1 to n) n の値は Ω(n2) になります。
于 2012-09-08T12:49:09.103 に答える