次のアルゴリズムを調査しています。
3 つすべてが最良の場合でも線形時間で実行できることはわかっていますが、並べ替えをカウントする場合を除いて、それらのケースがいつ発生するかを理解するのに苦労しています。
これがソートのカウントに関する私の理解であり、可能であれば他の2つのアルゴリズムに対する答えが欲しいです:
ソートしたい情報の間に大きなギャップがない場合、カウントソートは線形時間で実行されます。たとえば、1、10^5、および 545 などは大きな配列を作成し、メモリとトラバーサルを使用して効率的ではないため、これはカウントソートを使用する「最悪のケース」になります。ギャップは小さいです。
線形時間が発生したときの基数とバケットソートの最良のケースの条件を理解するのを手伝ってくれる人がいれば、私は感謝しています。
各アルゴリズムを個別に分析し、どのような場合に線形時間で実行されるかを判断できるかどうかを確認することから始めましょう。
まず、カウントソートを見てみましょう。アルゴリズムは次のように機能します。
最初のステップは、メイン配列を反復処理することにより、時間 O(n) で実行できます。配列の最大値が U であるとしましょう。この場合、配列要素をゼロにする必要があるため、ステップ 2 には O(U) の時間がかかります。3 番目のステップには O(n) の時間がかかります。周波数配列の各要素を 1 回 (O(U)) だけアクセスし、出力配列 O(n) に合計 n 回書き込むため、最後のステップには O(n + U) の時間がかかります。これは、総実行時間がO(n + U)であることを意味します。これは、並べ替える必要がある要素の総数 (配列が大きいほど並べ替えに時間がかかります) と、配列内の要素のサイズ (数値が大きいほど、それに比例してより多くの実行時間が必要になります) の両方に依存することに注意してください。
このランタイムを O(n) にしたい場合は、U = O(n) を要求する必要があります。そうすれば、O(n + U) = O(n + n) = O(n) になります。これは、配列の長さが増加するのとほぼ同じ割合で、配列内の最大要素のサイズが増加する必要があることを意味します。たとえば、配列内のすべての要素が 1 .. n の範囲内にあることが保証されている場合、並べ替えのカウントが完了するまでに O(n) の時間がかかります。それらの要素がその範囲内でどのように分布しているかは問題ではありません。
基数ソートは基本的に、ソートする配列内の数値の桁ごとに 1 回、カウントソートを繰り返し実行することによって機能します。基数ソートの背後にある重要なアイデアは、前のアルゴリズムの U の値をできるだけ低く保つことです。固定基数を選択することにより、U の値は一定の値に制限されます。たとえば、2 進基数ソートを使用して一度に 1 ビット進む場合、ソートする配列の各要素は、基本的に 0 または 1 として扱われます。これは、基数ソートの各ラウンドに時間がかかることを意味します O( n) 完了します。配列全体をソートするのに必要なラウンド数は、配列内の最大数の桁数、すなわち Θ(log U) によって与えられます。これは、アルゴリズムの合計実行時間が O(n log U) になることを意味します。
今回の利点は、log U が U よりもはるかにゆっくりと成長することです。たとえば、2 300は宇宙の原子の総数ですが、lg (2 300 ) = 300 とかなり小さいです。
log U はどの固定コンピュータでも定数であると主張する人もいます。32 ビット コンピューターでは、すべての整数は 32 ビットです (任意精度の整数ライブラリを使用している場合を除きます。これは今のところ無視します)。64 ビット システムでは、すべての整数は 64 ビットです。最初のケースではログ U = 32、2 番目のログでは U = 64 です。実行時間が O(n) になるため、固定システムの場合、基数ソートには常に線形時間がかかると主張できます。ただし、定数はシステムによって異なります。より理論的に考えており、より正確にしたい場合は、O(n log U) = O(n) であるため、log U = O(1) である限り、基数ソートは線形時間で実行されると言えます。これは、数値のビット数に一定の上限がある場合、基数ソートが線形時間で実行されることが保証されることを意味します。
バケット ソート アルゴリズムは、最下位桁ではなく最上位桁を使用して要素を分散することを除いて、基数ソートに似ています。これは、分析が以前とほとんど同じであることを意味します - log U = O(1) である限り、アルゴリズムは線形時間で実行されます。
お役に立てれば！