探索法

探索法

探索とはｎ個の入力データから値ｘと一致するデータを見つける操作のこと

線形探索

データの先頭から一つずつチェックしていく探索方法

最短で探索が完了するのはデータの先頭に探索する値が格納されている場合で時間計算量はO(1)

最長で探索が完了するのはデータに探索する値が含まれていない場合で時間計算量はO(ｎ)

データが大きくなればなるほど実行時間も長くなる

2分探索法

データがなんらかの順で並んでいるときに利用される

例えばデータが昇順で配列されているとき、探索したいデータと配列の真ん中のデータを比較する

データが等しければそこで探索は終了

データが探索したいデータより大きければ真ん中より前半を、小さければ真ん中より後半を同様に探索する

このように配列の半分にして、その前半か後半をまた半分に、そのまた前回か後半を半分にしていき探索を行う

平均時間計算量はO(logn)（説明は省略）

ハッシュ法

ハッシュ法はハッシュ関数によってデータが格納された配列に適用できる

ハッシュ関数とはhash(x)と表され、例えばhash(x)=(xをデータ数×1.5で割った余り)のような形で定義される

格納の例としては

ハッシュ関数で求めた値が3だったとき、添え字が3の配列をチェックする

この配列が空なら格納し、空でないなら次の配列(3＋1)をチェックする

これを繰り返し格納場所を見つける

ただし、配列のデータ数(入力データ×1.5)が決まっているので配列の最後まで行って格納場所がない場合は先頭に戻る

探索では格納と同様にハッシュ関数を用いて得られた値の添え字の配列をチェックする

探索する値と配列に格納されているデータが異なる場合は次の配列をチェックする

時間計算量はハッシュ関数によって変化する

ハッシュ関数で得られる値が重ならないような関数であれば時間計算量はO(1)

最後に

この3つの探索法では線形探索＞2分探索法＞ハッシュ法の順で実行時間が短い

しかし、データ数によっては2分探索法もハッシュ法もそんなにかわらず高速