アルゴリズム - 検索をスキップ

たとえば、サイズ n の配列 arr[] とサイズ m のブロック (ジャンプ対象) があるとします。次に、インデックス arr[0]、arr[m]、arr[2m]... ..arr[km] などを検索します。間隔を見つけたら (arr [km]

次の配列を検討します: (0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610)。配列の長さは 16 です。スキップされるブロック サイズが 4 であると仮定すると、スキップ検索では次の手順で 55 が見つかります。

ステップ 1: インデックス 0 からインデックス 4 にジャンプします;
ステップ 2: インデックス 4 からインデックス 8 にジャンプします;
ステップ 3: インデックス 8 からインデックス 16 にジャンプします;
ステップ 4: インデックス 16 の要素は 55 より大きいため、インデックス 9 まで 1 ステップ戻ります。 ステップ 5: インデックス 9 から線形検索を実行して要素 55 を取得します。

スキップする最適なブロック サイズはどれくらいですか? 最悪の場合、最後にチェックされた値が検索対象の要素より大きい場合、n/m ジャンプを実行し、線形検索で m-1 比較を実行する必要があります。したがって、最悪の場合の合計比較数は ((n/m)m-1) になります。 m=√nのとき、関数((n/m)m-1)の値が最小値となります。したがって、最適なステップ サイズは m = √n です。
リーリー

出力:

番号 55 はインデックス 10 にあります

時間計算量: O(√n)

補助スペース: O(1)
＃＃＃＃＃＃知らせ：＃＃＃＃＃＃

この検索は、ソートされた配列に対してのみ機能します。

スキップするチャンクの最適なサイズは O(√n) です。これにより、ジャンプ検索の時間計算量は O(√n) になります。 スキップ検索の時間計算量は、線形検索 ((O(n))) と二分検索 (O(Log n)) の間です。 バイナリ検索はジャンプ検索より優れていますが、ジャンプ検索には 1 回だけトラバースできるという利点があります (バイナリ検索では、検索対象の要素が最小要素または最小要素未満であることを考慮すると、最大 0 (Log n) 回のジャンプが必要になる場合があります)。したがって、ジャンプバックにコストがかかるシステムでは、ジャンプ検索を使用します。

以上がアルゴリズム - 検索をスキップの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。