平成30年度 春期 午前 問6

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

解説

2段の探索それぞれの平均を足すと m／2 ＋ n／(2m) です。

設問は、昇順に整列された n 個のデータを m 個ずつのブロックに区切り、まず各ブロックの最後尾だけを線形探索して目的のブロックを見つけ、次にその中を線形探索する方式の、平均比較回数を尋ねています。探索が2段になっているので、段ごとに平均を出して足せば済みます。まず数を押さえます。全体が n 個で1ブロックが m 個ですから、ブロックの数は n／m 個です。線形探索の平均比較回数は、目的のものが必ず表の中にあるとき、調べる件数のちょうど半分になります。したがって第1段は n／m 個を線形探索するので平均 n／(2m) 回、第2段はブロック内の m 個を線形探索するので平均 m／2 回です。足すと m／2 ＋ n／(2m) となります。n が 100 で m が 20 のときで確かめると、第1段は 5 個なので 2.5 回、第2段は 20 個なので 10 回、合計 12.5 回となり、この式に入れた値と一致します。

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

• アm ＋ n／m：段ごとの回数を半分にしないまま足した形です。どちらの段も最後まで調べ切ったときの回数になっており、平均ではなく最悪の場合を表す式になっています。
• ウn／m：ブロックの個数そのものです。第1段を最後まで調べ切ったときの回数に当たり、半分にする操作も、選んだブロックの中を探す第2段も抜け落ちています。
• エn／(2m)：第1段の平均回数だけを書いた形です。目的のブロックを見つけたところで話が終わっており、そのブロックの中身を探すための回数が加えられていません。