algorithm - 任意の数のプロセッサで O(1) 時間で実行する並列ランク ソートの作成方法

Question

O(n^2) 個のプロセッサで O(log n) 時間かかる並列ランクソートの実装を知っています。同時書き込みを使用すると、O(n^2) で O(1) の実行時間を得ることができます。プロセッサ。同時読み取りを使用せず、実行時間が O(1) である他の方法はありますか。

Answer 1

比較ベースの並べ替えには、少なくとも O(n log n) の比較が必要です。同時読み取りを許可しない場合、O(1) で n 個の値を並べ替えると、値を最大で O(n) 回読み取る (または操作する) ことができます。したがって、同時読み取りのない O(1) 並列ソートは、かなり風変わりなものでなければならないと思います。実際、最小の入力値である可能性がある最初の値など、並べ替えによって出力される単一の値を考えてみましょう。これは、n 個の入力値すべてに依存します。同時読み取りがなければ、単一の値を計算するプロセスを、各ノードで制限された次数とルートで計算された値を持つツリーとして表すことができると思います。かかる時間は、少なくとも O(log n) でなければならないツリーの深さです。