これを踏まえて、例えば、要素数100の配列を使った場合にある値を探索する場合は、平均何回くらい比較するでしょうか。
平均･･･、どうやって求めたらいいんだろう。
平均は次のように考えます。
探索値が最初の要素にある場合、2番目の要素にある場合、3番目の要素にある場合、･･･と考えていくと比較回数は、
- 最初の要素にある場合：比較回数 1 回
- 2番目の要素にある場合：比較回数 2 回
- 3番目の要素にある場合：比較回数 3 回
- ･･･
- 100番目の要素にある場合：比較回数 100 回
になるので、比較回数の平均は「比較回数の和 ÷ 回数」で求められますが、次の計算式で求めることができます。
要素数nの線形探索の平均比較回数 = (1 + n) / 2
要素数が100の場合、上記計算式の n に100を当てはめて計算します。
これで、要素数が100のときに目的のデータを探索するときは、平均50.5回比較することがわかりました。
計算式は公式として覚えておきましょう。
例えば、要素数が50のときや200のときの線形探索をした場合の平均比較回数は次のように計算できます。
| 要素数 50 のとき | ： 平均比較回数 ＝ (1 + 50)/2 ＝ 25.5回 |
| 要素数 200 のとき | ： 平均比較回数 ＝ (1 + 200)/2 ＝ 100.5回 |
線形探索は探索対象の要素数が多くなればなるほど、それに比例して平均比較回数も多くなります。
要素数nのときの線形探索の比較回数をまとめると次のようになります。
| 最小比較回数 | 最大比較回数 | 平均比較回数 |
|---|---|---|
| 1 | n | (1 + n) / 2 |
