分野 ：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

線形探索法を2回組み合わせて目的データを探し出すときの平均比較回数を求める問題です。探索するデータ数に注目して考えていきましょう。

線形探索法は、探索対象データを先頭から順に1つずつ比較していくことで目的のデータを見つける方法です。線形探索法において、N個のデータの中から目的のデータを探すときの平均比較回数は N＋12 回です。

最初は、n個のデータをm個ごとのブロックに分割した最後尾のデータのみを探索します。表のデータは昇順に整列されているので、各ブロック最後尾の並びも昇順になっているはずです。この最後尾データの並びに対して「目的のデータ≦各ブロックの最後尾データ」を順次チェックし、目的のデータが存在するブロックを探します。

この1回目の探索では、データを1つずつチェックしていくので線形探索の考え方を準用できます。探索するデータ数は n／m 個なので、目的のデータが存在するブロックが決定するまでの平均比較回数は、

　n／m＋12 [回]

2回目は、1回目の探索によって見つけたブロック内を線形探索します。探索対象のデータ数は m 個なので、目的のデータを見つけるまでの平均比較回数は、

　m＋12 [回]

2つの比較回数の合計は、

　n／m＋12 ＋ m＋12 [回]

ここまでたどり着ければ、なんとなく「イ」が適切そうなことがわかります。

設問では m は十分に大きいという条件が与えられていますが、n／m が十分に大きいとは限らないため、定数項の"＋1"は無視できません。よって、以下のように式を変形します。

　n／m＋12 ＋ m＋12
＝n／m＋1 ＋ m＋12
＝n／m＋m＋22
＝n2m＋m2＋22
＝n2m＋m2＋1

n2mは n が m より十分大きい場合に十分大きくなるので無視できない、"＋1"は m2 が十分大きいので無視できると考えると、定数項の"＋1"を除いて n2m＋m2。つまり、1回目と2回目の平均比較回数の合計は m2＋n2m になります。

【補足】
上記の解説ではmが十分に大きいという理由で＋1を除外していますが、線形探索の特性上、目的のデータが必ず存在するならば、最後の1つ前（n－1番目）の要素までの比較で目的のデータが見つからなかった場合、最後の要素が目的のデータであることが確定します。このため最小比較回数を 1回、最大比較回数を n－1回、平均比較回数を n／2回 として考えることもできるでしょう。この考え方だと1回目の平均比較回数が n／2m回、2回目の平均比較回数が m／2回となり、正解の式と一致します。