探索アルゴリズム
探索ってなに？
データの並びから目的のものを見つけ出すこと。
例えば [3,5,7,1,4,9,6,2,8] この中から4を見つける方法について考えてみましょう。
1. 線形探索
至ってシンプルな方法で、データの先頭から4かどうか一つずつ確認していく。
この場合は先頭から5番目に4があったので、5回の計算を行ったことになります。
n個のデータで線形探索を行うとき、最小で1回、最大でn回の探索が必要になります。
平均の探索回数はn/2回で、これはデータの個数nに比例しています。
よって計算量はO(n)となります。
2. 2分探索
2分探索は、ソートされたデータにしか使えません。今回のケースでは、あらかじめデータを[1,2,3,4,5,6,7,8,9]という風に並び替えておく必要があります。
まず、探しているデータと真ん中のデータを比較します。
真ん中の5は4より大きいので、4は真ん中より左の[1,2,3,4]にあることがわかります。
再び同じ様に、[1,2,3,4]の真ん中の2(または3)と4を比較します。
今度は真ん中の値より大きいので、2より右にあることがわかります。
この様に、「真ん中の値を比較→探しているデータが含まれない半分を捨てる」を探しているデータに辿り着くまで繰り返すのが2分探索です。
n回探索を行うと、データを二分する作業をn回行ったことになるので、$2^n$個までのデータを探索することができます。よって計算量はO($log_2{n}$)になります。(底2は省略して良い)
3. ハッシュ表探索
こちらも下処理が必要で、ハッシュ関数を用いて、予めデータをハッシュ値に基づいて格納しておきます。
例えば、ハッシュ関数が $h(x)=x \% 9$ (xを9で割った余り)だとします。
このとき、4のデータは4を9で割った余りが4なので、「4」の場所に格納されています。
すでにこの処理がされているので、探索の時にやることは再度4を9で割った余りを計算し、「4」の場所を探すだけです。
この方法では、データの大きさnにかかわらず、ハッシュ関数の計算を1度行うだけなので、計算量はO(1)となります。
ただし、例えば今回の場合では4と13ではハッシュ値が共に4で衝突する様に、違うデータでハッシュ値が重なるシノニムと呼ばれる問題が発生することがあります。