線形探索とはデータがあってそれを順番に確認して目的の値を見つけ出す手法になります。探索のアルゴリズムとしては一番単純なものになります。
例えば以下のデータ（配列）があるとしましょう。
[a, b, c, d, e, f]
ここでdを探しているとして最初のaから順番にb,cと順番に調べていくのが線形探索となります。
平均比較回数
平均比較回数とは様々なデータがあるとして線形探索で探した時に何回探すかという回数を平均にしたものです。
前述の例ではdが四回目の比較で発見されました。ではデータが以下のような順番になっていたらどうでしょうか？
[d, a, b, c, e, f]
[a, b, c, e, f, d]
一回目の比較で見つかる場合もあれば五回目の比較で見つかる場合もあります。この比較回数を平均したものが平均比較回数となります。
平均比較回数の公式
まずN個のデータから線形探索で平均比較回数を導き出す式は以下になります。
(N+1)/2
この式を解説するとNはN個のデータがあるとしてその最後のN番目を表していて、1は1番目を表しています。
具体例
例えば以下のデータベースがあるとします。
[6,7,8]
式は以下になります。
(3+1)/2=2
3つのデータがあって3は3番目が最後（N番目）を表しています。
1は最初のデータを表しています。
もう一つ例を書いてみると
[a, b, c, d, e, f]の場合は
(6+1)/2=3.5
となります。
どうしてこの公式が成立するのか？
前述のデータを例にトレースしてみましょう。今回は8を探していると仮定します。
[6,7,8]
まず1番目の6を確認すると8とは違う値ということがわかります。
次に2番目の7を確認すると8とは違う値ということがわかります。
３回目の比較で8が見つかりました。
次は以下のようにデータがなっていた場合を考えてみます。
[6,8,7]
同じように先頭から比較していくので今度は2回の比較でデータが見つかります。
[8,6,7]
最後のパターンは1回目の比較で見つかります。
ここで比較した回数の平均を求めるとすると
3回（1回目の探索）＋2回（2回目の探索）＋1回（1回目の探索）＝6回
6回／3（合計3回探索しているため）＝2回
となり2回が平均探索回数となります。
これを簡略化して公式にしたものが
(N+1)/2
となり、データの個数が増えても簡単に計算ができるというわけですね。
コメントを残す