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