4

是否有可能获得一个成本最优算法，用于EREW PRAM的 n 个处理器对 n 个整数进行排序？

4

1 回答 1

1

是的，Richard Cole 有一个名为“Parallel Merge Sort”的算法，它理论上使用 O(n) 处理器在 O(log n) 中对 EREW PRAM 上的输入（不仅仅是整数）进行排序。

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

于 2013-01-14T06:52:36.237 回答