配列内のすべての要素の上限が特定の数値であることがわかっている場合、カウントソートは線形時間で知られています。一般的な配列を使用する場合、配列を線形時間でスキャンして、配列の最大値を見つけてから、カウントソートを適用することはできませんか?
1304 次
3 に答える
8
カウントソートを実行するには、上限を知っているだけでは十分ではありません。すべてのカウンターに収まる十分なメモリが必要です。
64 ビット整数の配列を調べて、最大の要素が 2^60 であることがわかった状況を考えてみましょう。これは次の 2 つのことを意味します。
- O(2^60) メモリが必要です。
- ソートを完了するには O(2^60) かかります。
O(2^60)が同じであるという事実は、O(1)ここではほとんど役に立ちません。定数係数が単に大きすぎるからです。これは、疑似多項式時間アルゴリズムでよく発生する問題です。
于 2014-07-28T18:33:05.020 に答える
2
最大数が 235684121 のようなものであるとします。その場合、バケットを保持するために信じられないほどの量の RAM を消費することになります。
于 2014-07-28T18:31:30.540 に答える