0

私は、アルゴリズムの紹介第 3 版のマルチスレッド マージ ソートを読んでいる最中でした。ただし、次の Merge-Sort アルゴリズムに必要なプロセッサの数と混同しています。

MERGE-SORT(A, p, r)
1 if p < r
2 q = (p+r)/2
3 spawn MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 sync
6 MERGE(A, p, q, r)

MERGE は標準のマージ アルゴリズムです。このアルゴリズムに必要なプロセッサの数は?? 私はそれがO(N)であるべきだと仮定していますが、本はそれがO(log n)であると主張していますが、なぜですか? MERGE プロシージャをマルチスレッド化していないことに注意してください。例を挙げた説明は本当に役に立ちます。前もって感謝します。

4

1 に答える 1

0

O(log n)値は、アルゴリズムを実行するために「必要な」CPUの数ではなく、アルゴリズムによって達成される実際の「並列処理」です。MERGE自体は並列化されていないため、O(n)プロセッサがすべて使用可能であっても、それらのプロセッサを十分に活用することはできません。

つまり、マージソートのシングルスレッドのシリアル時間計算量はO(n log n)です。'n'はマージのコストと考えることができ、'log n'は、配列をマージできるステージに到達させるためのマージソートの再帰呼び出しでカウントされる要素と考えることができます。再帰を並列化するが、マージがまだシリアルである場合、O(log n)係数を保存しますが、O(n)係数はそこに残ります。したがって、十分なプロセッサが使用可能な場合、並列処理はO(log n)のオーダーになりますが、O(n)に到達することはできません。

言い換えると、O(n)CPUが使用可能であっても、それらのほとんどはすぐにアイドル状態になり、大規模なMERGEが発生し始めると動作するCPUはますます少なくなります。

于 2012-05-18T14:55:52.473 に答える