平成21年度 春期 午前 問8

✓ これが正解イm／2＋n／(2m)

解説

外側と内側の平均比較回数を足し合わせた形です。

この方法は探索を二段構えにしています。まずブロックの最後尾だけを順に線形探索し、目当てが入っているブロックを特定します。次に、そのブロックの中を線形探索して目当てを探し当てます。線形探索の平均比較回数は、探す対象が範囲の中にあるとき、範囲の要素数の半分になります。ブロックの数はデータ数を 1 ブロックの大きさで割った値なので、最後尾を探すときの平均比較回数はその半分、すなわち n を 2m で割った値です。目当てのブロックが見つかった後の探索は、1 ブロックに含まれる要素数を半分にした値、すなわち m を 2 で割った値で表せます。二つは順番に行う独立の作業なので、平均比較回数はそのまま足し合わせる形になります。したがって、m の半分と、n を 2m で割った値の和が、全体の平均比較回数を表す式です。

ほかの選択肢はなぜ違うのか

• アm＋n／m：m と n÷m の和で表しています。線形探索の平均比較回数は範囲の要素数の半分になる関係を使っておらず、範囲そのものを足したときに現れる最悪値に近い姿になっています。
• ウn／m：n÷m だけを式に置いています。これはブロックの数を表す値であり、二段の探索のうち片方の平均比較回数にすら達していません。
• エn／(2m)：n÷(2m) だけを式に置いています。ブロックを見つけるまでの平均比較回数だけを取り出した式で、ブロックの中で目当てを探し当てる分の平均比較回数が抜けています。