4

EREW PRAMの n 個のプロセッサで n 個の整数をソートするためのコスト最適アルゴリズムを取得する可能性はありますか?

4

1 に答える 1

1

はい、O(n) プロセッサを使用して O(log n) で EREW PRAM の入力 (整数だけでなく) を理論的にソートする「Parallel Merge Sort」という名前の Richard Cole によるアルゴリズムがあります。

http://epubs.siam.org/doi/abs/10.1137/0217049

于 2013-01-14T06:52:36.237 に答える