私は、アルゴリズムの紹介第 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 プロシージャをマルチスレッド化していないことに注意してください。例を挙げた説明は本当に役に立ちます。前もって感謝します。
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はますます少なくなります。