arrays - 一定時間 O(1) で n 個の共通 CREW プロセッサを使用して、サイズ n の並べ替えられた配列で要素 x を見つけることができますか?

Question

n要素の配列が与えられた場合、一般的なCRCWプロセッサを使用して一定時間でその配列内の要素xの位置を見つける方法は?

x が指定された配列にないと仮定しましょう。定数時間 O(1) の配列で x の位置を見つけることさえ可能ですか?

CREW は、同時に読み取ることができますが、排他的に書き込むことができるタイプのプロセッサです。

psこれは割り当てではありません。

Answer 1

並列アルゴリズムのバックグラウンドはあまりありませんが、n コアを使用して次のことを行うことでこれを実行できると思います。

• 結果を「見つかりません」に設定
• n 個のプロセッサのそれぞれに次を実行させます。各プロセッサには異なるインデックス k が割り当てられています。配列の k 番目の要素が x の場合、結果を k に設定します。

すべてのプロセッサが実行を終了すると、結果変数が設定されていた場合、要素 k を保持する配列のインデックスが保持されます。また、各プロセッサは O(1) の作業のみを行います。

これがお役に立てば幸いです。この理由が有効でない場合はお知らせください。