指数探索
ソートされた無限リストを検索するためのアルゴリズム
指数探索
クラス検索アルゴリズム
データ構造配列
最悪の パフォーマンスO (log i )
最高の パフォーマンスO (1)
平均的な パフォーマンスO (log i )
最悪の場合の 空間複雑度O (1)
最適はい

コンピュータサイエンスにおいて、指数探索（倍増探索、ギャロッピング探索、ストルジック探索とも呼ばれる）[1]は、ジョン・ベントレーとアンドリュー・チチー・ヤオが1976年に考案した、ソートされた無限リスト[2]を探索するアルゴリズムである。これを実装する方法は数多くあるが、最も一般的なのは、検索キーが存在する範囲を決定し、その範囲内で二分探索を実行することである。この方法は、検索キーがリスト内に存在する場合、リスト内の位置がどこであるか、検索キーがリスト内に存在しない場合、検索キーが存在するべき位置がどこであるかを判断するのに時間がかかる。 お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} 私 {\displaystyle i}

指数探索は、境界付きリスト内の検索にも使用できます。検索対象の要素が配列の先頭近くにある場合、指数探索は、境界付きリストに対する従来の探索（例えば二分探索）よりも優れたパフォーマンスを発揮します。これは、指数探索はリスト内の検索対象要素のインデックスで実行されるのに対し、二分探索はリスト内の要素数 で実行されるためです。 お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} 私 {\displaystyle i} お （ ログ ⁡ n ） {\displaystyle O(\log n)} n {\displaystyle n}

アルゴリズム

指数探索は、ソートされた無制限のリストの中から、指定された入力値（検索「キー」）を検索することを可能にする。このアルゴリズムは2つの段階から構成される。第1段階では、リスト内に検索キーが存在する場合の範囲を決定する。第2段階では、この範囲に対して二分探索が実行される。第1段階では、リストが昇順でソートされていると仮定し、アルゴリズムは最初の指数j（値 2 jが検索キーより大きい）を探す。この値 2 jは二分探索の上限となり、前の2の累乗である 2 j - 1は二分探索の下限となる。[3] 

// 長さsizeの配列arr内のkeyの位置を返します。
template < typename T > int exponential_search ( T arr [], int size , T key ) { if ( size == 0 ) { return NOT_FOUND ; }  
      

        
         
    

    int bound = 1 ; while ( bound < size && arr [ bound ] < key ) { bound *= 2 ; }   
            
          
    

    戻り値binary_search ( arr , key , bound / 2 , min ( bound , size )); }

各ステップにおいて、アルゴリズムは検索キーの値と現在の検索インデックスのキーの値を比較します。現在のインデックスの要素が検索キーよりも小さい場合、アルゴリズムはこれを繰り返し、次の検索インデックスにスキップして、そのインデックスを2倍にして次の2の累乗を計算します。[3]現在のインデックスの要素が検索キーよりも大きい場合、アルゴリズムは、検索キーがリストに含まれている場合、前の検索インデックス2 j - 1と現在の検索インデックス2 jによって形成される間隔内にあることを認識します。その後、バイナリ検索が実行され、検索キーがリストにない場合は失敗、検索キーがリスト内の位置の場合は検索キーがリスト内に存在するかどうかが示されます。

パフォーマンス

アルゴリズムの最初の段階は時間がかかります。ここで はリスト内で検索キーが位置するインデックスです。これは、二分探索の上限を決定する際に、whileループがちょうど回実行されるためです。リストはソートされているため、検索インデックスを 回倍にした後、アルゴリズムはi以上の検索インデックスに到達します。そのため、アルゴリズムの最初の段階は時間がかかります。 お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} 私 {\displaystyle i} ⌈ ログ ⁡ （ 私 ） ⌉ {\displaystyle \lceil \log(i)\rceil } ⌈ ログ ⁡ （ 私 ） ⌉ {\displaystyle \lceil \log(i)\rceil } 2 ⌈ ログ ⁡ （ 私 ） ⌉ ≥ 私 {\displaystyle 2^{\lceil \log(i)\rceil }\geq i} お （ ログ ⁡ 私 ） {\displaystyle O(\log i)}

アルゴリズムの2番目の部分も時間がかかります。2番目の段階は単純な二分探索なので、 かかります。ここで は探索対象の区間のサイズです。この区間のサイズは 2 j - 2 j - 1となります。 ここで、前述のようにj = です。つまり、探索対象の区間のサイズは 2 log i - 2 log i - 1 = 2 log i - 1です。したがって、実行時間は log (2 log i - 1 ) = log ( i ) - 1 =となります。 お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} お （ ログ ⁡ n ） {\displaystyle O(\log n)} n {\displaystyle n} ログ ⁡ 私 {\displaystyle \log i} お （ ログ ⁡ 私 ） {\displaystyle O(\log i)}

これにより、2 つのステージの実行時間を合計して計算されたアルゴリズムの合計実行時間は、+ = 2 =になります。 お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} お （ ログ ⁡ 私 ） {\displaystyle O(\log i)} お （ ログ ⁡ 私 ） {\displaystyle O(\log i)}

代替案

Bentley と Yao は、指数探索のいくつかのバリエーションを提案しました。[2]これらのバリエーションは、アルゴリズムの第 2 段階で二分探索の上限を決定するときに、単項探索ではなく二分探索を実行します。これにより、アルゴリズムの第 1 段階が 2 つの部分に分割され、アルゴリズムは全体として 3 段階アルゴリズムになります。新しい第 1 段階では、以前と同様に、検索キーよりも大きく、検索キーよりも小さい値 を決定します。以前は、 は、次の 2 の累乗を計算することによって単項形式で決定されました (つまり、jに 1 を加算)。バリエーションでは、代わりに を 2 倍にすることが提案されています (たとえば、 2 3ではなく、 2 2から2 4にジャンプします)。 が検索キーよりも大きい最初のは、以前よりもはるかに大まかな上限を形成します。これが見つかると、アルゴリズムは第 2 段階に進み、とによって形成される区間で二分探索が実行され、より正確な上限指数jが得られます。ここから、アルゴリズムの第3段階では、前述と同様に区間2 j - 1と2 jについて二分探索を実行します。このバリエーションの性能は です。 j ′ {\displaystyle j'} 2 j ′ {\displaystyle 2^{j'}} 2 j ′ / 2 {\displaystyle 2^{j'/2}} j ′ {\displaystyle j'} j ′ {\displaystyle j'} j ′ {\displaystyle j'} 2 j ′ {\displaystyle 2^{j'}} j ′ {\displaystyle j'} j ′ / 2 {\displaystyle j'/2} j ′ {\displaystyle j'} ⌊ ログ ⁡ 私 ⌋ + 2 ⌊ ログ ⁡ （ ⌊ ログ ⁡ 私 ⌋ + 1 ） ⌋ + 1 ＝ お （ ログ ⁡ 私 ） {\displaystyle \lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1=O(\log i)}

BentleyとYaoはこのバリエーションを一般化し、アルゴリズムの最初の段階で任意の回数kの二分探索を実行するkネスト二分探索バリエーションを与えます。漸近的実行時間はバリエーションによって変化せず、元の指数探索アルゴリズムと同様に時間とともに変化します。 お （ ログ ⁡ 私 ） {\displaystyle O(\log i)}

また、上記のkネスト二分探索の結果をソートされた配列に適用すると、動的フィンガー特性のタイトバージョンを持つデータ構造を実現できる。 [4]これを用いると、探索中に行われる比較回数はlog( d )+loglog( d )+...+ O (log  * d )となる。ここでdは最後にアクセスした要素と現在アクセスしている要素のランクの差である。

アプリケーション

検索帯域を指数関数的に増加させるアルゴリズムは、 のグローバルペアワイズアライメントを解きます。ここでは配列の長さ、はそれらの間の編集距離です。[5] [6] お （ n s ） {\displaystyle O(ns)} n {\displaystyle n} s {\displaystyle s}

参照

参考文献

  1. ^ Baeza-Yates, Ricardo ; Salinger, Alejandro (2010)、「Fast intersection algorithms for sorted sequences」、Elomaa, Tapio、Mannila, Heikki、Orponen, Pekka (編)、『Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday』、Lecture Notes in Computer Science、vol. 6060、Springer、pp.  45– 61、Bibcode :2010LNCS.6060...45B、doi :10.1007/978-3-642-12476-1_3、ISBN 9783642124754。
  2. ^ ab Bentley, Jon L. ; Yao, Andrew C. (1976). 「無限探索のためのほぼ最適なアルゴリズム」. Information Processing Letters . 5 (3): 82– 87. doi :10.1016/0020-0190(76)90071-5. ISSN  0020-0190.
  3. ^ ab Jonsson, Håkan (2011-04-19). 「指数二分探索」. 2020年6月1日時点のオリジナルよりアーカイブ。2014年3月24日閲覧。
  4. ^ Andersson, Arne; Thorup, Mikkel (2007). 「指数探索木を用いた動的順序集合」. Journal of the ACM . 54 (3): 13. arXiv : cs/0210006 . doi :10.1145/1236457.1236460. ISSN  0004-5411. S2CID  8175703.
  5. ^ Ukkonen, Esko (1985年3月). 「文字列内の近似パターンの検出」 . Journal of Algorithms . 6 (1): 132– 137. doi :10.1016/0196-6774(85)90023-9. ISSN  0196-6774.
  6. ^ Šošić, Martin; Šikić, Mile (2016-08-23). 「Edlib: 編集距離を用いた高速かつ正確な配列アライメントのためのC/C++ライブラリ」. doi :10.1101/070649. S2CID  3818517.
「https://en.wikipedia.org/w/index.php?title=Exponential_search&oldid=1296434805」より取得