はじめに
探索アルゴリズムとは、大量にあるデータの中から特定のデータを探し出す方法のことです。
今回は代表的なアルゴリズムである線形探索法、二分探索法、ハッシュ法について解説します。
【YouTube動画】 線形探索法、二分探索法、ハッシュ法について 基本情報技術者試験
オーダー (計算量, O)
ここでいうオーダーは、処理する数が多くなるに従い、どの程度計算量が多くなるのかという目安のことです。
記号 Oで表記します。
要素の数が増えるにしたがって、一次関数的に増加する場合O(n)、二次関数的ならO(n^2)と表記します。
また、どんなに要素が増えても、定数回で処理が終わる場合はO(1)になります。
線形探索法 O(n)
線形探索法は順々に要素を確認していく方法です。
要素数がnならば、最悪全部確認すれば、目的の要素が見つかるので、O(n)になります。
例えば、以下の7つの数値から特定の数値を探すとします。
左から1を見つけるまでには3回確認作業が必要です。
8 4 1 3 5 9 6
二分探索法 O(log n)
二分探索法は要素が最後の1つになるまで、要素を半分にしていく確認方法です。
ソートと組み合わせて使うと、威力を発揮します (ソートは別記事で解説します！)。
例えば、以下のソートされた7つの数値から11を探すとします。
まず、真ん中の数値をみます。
7は11より小さいので、7より左側の数値は無視します。
2 4 5 7 8 10 11
次の真ん中の数値は10です。
10は11より小さいので、さらに左側の数値を無視します。
8 10 11
数値が1つだけになり、11を見つけることができました。
11
この二分探索法の計算量は log nになります。
計算量の計算
計算量は1個の要素を何回2倍にすると、全要素数と一致するかと考えます。
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> ...
全要素数が8であれば、3回2倍すれば一致します (2^3 = 8)。
一般化すると、全要素数nに対して、m回2倍すれば一致します。
n = 2 ^m
対数を取ると、計算量が求まります (底2)。
m = log n
ハッシュ法 O(1)
ハッシュ法はハッシュ関数を使って探索していく方法です。
データを保存する前に、数値化し、数値化した場所にデータを保存します。
調べたい値 -> 対応表を確認 -> データにアクセス と進むので、データ量に関わらず計算量は増えません。
まとめ
今回は代表的な探索アルゴリズムを紹介しました。
二分探索の方で出てきたソートについては、別記事で紹介します！