木と検索

深さ優先探索
深さ優先探索(dfs)は木やグラフデータ構造を横断または探索するためのアルゴリズムである.つは、ルート(いくつかの任意のノードをグラフの場合のルートとして選択)で起動し、バックトラッキングの前に、各ブランチに沿って可能な限り探索します.

幅優先検索( BFS )
幅優先探索(bfs)は木やグラフデータ構造を横断または探索するためのアルゴリズムである.これはツリーのルート(またはグラフのいくつかの任意のノードで、時々、“検索キー”と呼ばれる)から始まり、隣のノードに最初に、次のレベルの隣人に移動する前に探索します.

線形探索
計算機科学において,線形探索または逐次探索はリスト内の目標値を求める方法である.マッチが見つかるまで、または、すべての要素が捜されるまで、それは目標値のためにリストの各々の要素を順番にチェックします.線形探索は最悪の線形時間で実行され、nが最も近いnの比較を行う.
複雑さ
時間の複雑さ:O(n)-最悪の場合には、各要素を一度だけチェックしているので.

ジャンプサーチ
バイナリ検索のように、ジャンプ検索(またはブロック検索)は、ソートされた配列の探索アルゴリズムです.基本的な考えは、固定されたステップによって前に飛び、すべての要素を探索する代わりにいくつかの要素をスキップすることによって、より少ない要素(線形検索より)をチェックすることです.
例えば、サイズNとブロック(ジャンピングされる)の配列arr []を配列mとすると、インデックスarr [ 0 ], arr [ m ], arr [ 2 * m ],…というインデックスを探します.ARR [ K * M ]など.区間ARR [ k * m ]< x + arr [( k + 1 )*] mを見つけたら、インデックスk * mから直線探索を行い、xを探します.
スキップする最適なブロックサイズは何ですか?最悪の場合、N/Mジャンプをしなければならず、最後にチェックされた値が検索対象の要素より大きい場合、線形探索のためにM - 1比較を行います.したがって、最悪の場合の比較回数は((n/m)＋m−1)となる.関数(値(n/m)+ m - 1)の値はm =√したがって、最良のステップサイズはM = = 1です√n
複雑さ
時間の複雑さ√n -サイズのブロックで検索するので√n

バイナリ検索
計算機科学では、二値探索(半間隔探索、対数探索、またはバイナリチョップとして知られている)は、ソートされた配列内の目標値の位置を求める探索アルゴリズムである.バイナリ検索は、配列の中央要素にターゲット値を比較しますそれらが不平等であるならば、目標がそうすることができない半分は削除されます、そして、検索はそれが成功するまで残りの半分に続きます.残りの半分が空で検索が終了した場合、ターゲットは配列にはありません.
複雑さ
時間の複雑さ:o(log(n))-我々は次の反復のために2で検索領域を分割したので.

補間探索
補間探索は、キー(キー値)に割り当てられた数値によって順序づけられた配列のキーを検索するためのアルゴリズムです.
例えば、n個の一様に分布した値arr []のソートされた配列を持ち、配列内の特定の要素Xを探索する関数を書く必要があります.
線形探索はo(n)時間で要素を見つけます√ n )時間とバイナリ探索はo ( log n )時間をとる.
補間探索は、ソートされた配列の値が一様に分布しているインスタンスに対するバイナリ探索の改善である.バイナリ検索は常にチェックするために中央の要素に行きます.一方、内挿探索は検索対象のキーの値に応じて異なる位置に移動してもよい.例えば、キーの値が最後の要素に近い場合、内挿検索は終了側への探索を開始する可能性が高い.
検索する位置を見つけるには、次の式を使用します.

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
arr[] - Array where elements need to be searched
x - Element to be searched
lo - Starting index in arr[]
hi - Ending index in arr[]

複雑さ
時間の複雑さ: O ( log ( log ) n )
参考文献
https://github.com/trekhleb/javascript-algorithms
https://www.bigocheatsheet.com/