私は配列40のサイズを持っていて、探している要素が位置38にあるとしましょう。 単純なループを持つと、38ステップかかるでしょうか？ しかし、2つのループを並列に実行すると変数 "found" がfalseに設定され、要素が見つかるとtrueに変更されます。どちらが速いでしょうか？
最初のループ、インデックス0 第二のループから開始され、それだけで、4つのステップ右かかりますので、基本的に
インデックス40から開始されますか？要素を見つける。要素が配列の中央にある場合、最悪の場合があります。右？
2つのスレッド間の状態を同期させるために必要な作業によって異なります。
0の作業が必要な場合は、ストレートスルーアルゴリズムより平均して50％高速です。
一方、Xよりも多くの作業が必要な場合は、遅くなり始めます（非常にそうです）。
アルゴリズムの観点からは、私はこれがあなたが行きたいとは思わない。 2つのスレッドもO（n）ランタイムになります。データをソートして（n log n）、バイナリ検索を行ってデータを取得するとします。特に1回ソートして多くの検索に使用できます。
okありがとうございました – pantelis
アルゴリズムの複雑さについて言えば、これはまだ線形検索です。反復ごとに2つの要素を探索しているだけで、アルゴリズムがO（n）であるという事実は変わりません。
実際のパフォーマンスでは、このアルゴリズムは単一のプロセッサを使用したリニア検索よりも遅くなる可能性があります。検索では要素ごとに処理がほとんど行われないため、アルゴリズムはメモリにバインドされているため、複数のプロセッサを使用する利点はありません。また、2つの場所で検索しているため、このアルゴリズムは効率的なキャッシュではありません。そして、bwawokが指摘しているように、同期の際に多くの時間が失われるでしょう。
よくその線形検索対並行線形検索。しかし、私はo（n）とo（n）の両方がO（n）に簡素化されると思うので、アルゴリズムのパフォーマンスの変更は正しくありません;） – bwawok
と並行して実行している場合は、CPUパワーを2つに分け+若干のオーバーヘッドを作成します。たとえば、というマルチコアマシンで検索を実行している場合は、提案されたアルゴリズムでは、悪いケースが20ステップです。あなたは複雑さのクラスを変更していません。あなたが言及した4つのステップがどこから来ているのですか？
要素が38/40の位置にある場合は配列の2番目のループで、2番目のステップで配置されます。 最初のループはすでに2つのステップを実行しています。 2 + 2 = 4となる。 – pantelis
平均で実行時に違いはありません。
あなたがアイテムを検索する場合、元のアルゴリズムは、次の検索順序で処理します10
のうちの一例を見てみましょう：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
をより悪い場合は、最後の項目（10のステップを取って）であります。
第2のアルゴリズムは、次の検索順序で処理するが：
1, 3, 5, 7, 9, 10, 8, 6, 4, 2
このシナリオでは最悪の場合は、アイテム6（10の手順をとる）です。
アルゴリズム1が高速な場合があります。
アルゴリズム2が高速な場合があります。
両方とも平均で - O（n）です。
これをバイナリ検索順序（ソートされた配列）と比較することは面白いことです。
4, 3, 2, 3, 1, 4, 3, 2, 4, 3
最大4つのステップを完了します。
なぜこれをやりたいですか？あなたがアレイ上で検索を行うために「ホイールを再構成しようとしている」のように聞こえます。 –
私は車輪を再発明しようとしていません。私はちょうどこの質問を持っていて、どちらが速くなるのか把握しようとしています。 – pantelis
あなたは単に最悪の場合があると断言していますか？それが「中」の場合、ステップ数は同じである可能性があります。 –