マージ アルゴリズムは、2 つの入力配列の最小要素を繰り返し比較し、2 つのうち小さい方を出力に移動することによって、2 つの並べ替えられた入力配列を並べ替えられた出力配列にマージします。
次に、同じ長さの 3 つの並べ替えられた入力配列 (A1、A2、および A3) を (並べ替えられた) 出力配列にマージする必要があります。2 つの方法があります。
上記の Merge アルゴリズムを使用して A1 と A2 を A4 にマージし、同じアルゴリズムを使用して A4 と A3 を出力配列にマージします。
3 つの入力配列の最小要素を繰り返し比較し、3 つの最小要素を出力配列に移動することにより、上記の Merge アルゴリズムを修正します。
上記の 2 つのアルゴリズムのうち、配列要素の移動 (つまり、代入) の最悪のケースのみを考慮した場合、どちらがより効率的ですか?
配列要素の比較の最悪のケースのみを考慮した場合、上記の 2 つのアルゴリズムのどちらがより効率的ですか?
これら 2 つのアルゴリズムのうち、最悪の場合に全体的な効率が高いのはどちらですか?
関心があるのが配列書き込みの数だけである場合、2 番目のバージョン (3 方向マージ) は最初のアルゴリズム (2 方向マージの 2 つのインスタンス) よりも高速です。3 方向マージ アルゴリズムは、3 つの範囲すべてを 1 つのパスでマージするため、正確に 3n 回の書き込みを行います (n は任意のシーケンスの長さです)。最初のアプローチでは、範囲の 2 つをマージして 2n 回の書き込みを行い、次にそのシーケンスを 3 番目のシーケンスとマージして、3n 回の書き込みを行い、正味合計 5n 回の書き込みを行います。
より一般的には、要素の範囲が k 個あり、すべての長さが n であるとします。これらの範囲をペアごとにマージし、それらのマージをペアごとに再度マージするなどの場合、長さ n の範囲をマージする大まかな k/2 回のマージ ステップを実行し、次に長さ 2n の範囲を k/4 回マージし、次に k/8 回マージします。長さ 4n など。これにより、合計が得られます。
kn/2 + kn/2 + ... + kn/2 (log n 回)
O(kn lg n) である配列書き込みの正味数の場合。一方、各ステップで k-way 比較を使用すると、正確に kn 回の書き込みが行われ、はるかに小さくなります。
ここで、各設定で何回比較を行うかを考えてみましょう。3 方向マージでは、出力シーケンスに書き込まれる各要素は、3 つの値の最小値を見つける必要があります。これには 2 つの比較が必要です。1 つは最初の 2 つのシーケンスの最初の値を比較し、もう 1 つはこれら 2 つの値の最小値を 3 番目の配列の最初の値と比較します。したがって、結果のシーケンスに書き出される値ごとに、2 つの比較を使用します。3n の値が書き込まれるため、合計で最大 6n 回の比較を行う必要があります。
これを行うためのより良い方法は、シーケンスを最初の要素で比較する最小ヒープにシーケンスを格納することです。各ステップで、最初の値が最も小さいヒープからシーケンスをデキューし、その値を結果に書き込み、シーケンスの残りをヒープにエンキューします。k シーケンスの場合、ヒープ挿入は O(lg k) で実行されるため、書き出される各要素には最大で O(lg k) の比較が必要であることを意味します。書き出された kn 個の要素のそれぞれに O(lg k) の処理時間が必要なため、これにより正味実行時間は O(kn lg k) になります。
もう 1 つのバージョンでは、標準の双方向マージを実行することから始めます。これには、書き出された要素ごとに 1 つの比較が必要であり、正味合計 2n の比較になります。マージの 2 番目のパスでは、マージされる 3G 要素があるため、最悪の場合、合計 3n 回の比較が行われます。これにより、合計 5n 回の比較が行われます。上記のペアワイズ マージに一般化された構造を使用する場合、O(kn lg n) 比較を使用する必要があります。これは、書き込まれる各要素に 1 つの比較が必要であり、O(kn lg n) 書き込みを行うためです。
つまり、k=3 の特定のケースでは、9n のメモリ読み取りと書き込みのネットに対して、3 方向マージが 3n の書き込みと 6n の比較を行うことがわかります。反復双方向マージでは、5n 回の書き込みと 5n 回の比較が行われ、正味合計 10n 回のメモリ読み取りと書き込みが行われるため、3 方向マージ バージョンの方が優れています。
一般化された構造を考慮すると、k-way マージは、合計 O(nk lg k) のメモリ操作に対して O(nk) 回の書き込みと O(nk lg k) の比較を行います。反復双方向マージ アルゴリズムは、合計 O(nk lg n) 回のメモリ操作に対して O(nk lg n) 回の書き込みと O(nk lg n) 回の比較を行います。したがって、少数の長いシーケンスでは k-way マージの方が漸近的に優れていますが、多くの短いシーケンスでは反復マージ ソートの方が高速です。
お役に立てれば！