応用情報技術者 2018年 春期 午前2 問06

ブロック線形探索平均比較数【午前2解説】

正解の理由

解法ステップ

1. ブロック数を $B=n/m$ と置く（問題の条件で整数）。
2. ブロック選定の期待比較回数を求める。各ブロックに目的値が存在する確率は均等で $1/B$、ブロック番号が $j$ のとき最後尾の比較は $j$ 回目で止まるため期待値は $\frac{1}{B}{\sum }_{j=1}^{B}j=\frac{B+1}{2}.$
3. そのブロック内の探索期待回数を求める。ブロック内の位置を $r=1,\dots ,m$ とすると、$r=m$（最後尾）のときは既に比較済みで追加探索は不要、その他のときは $r$ 回の比較が必要。従って期待値は $\frac{1}{m}{\sum }_{r=1}^{m-1}r=\frac{m-1}{2}.$
4. 和を取ると合計期待比較回数は $\frac{B+1}{2}+\frac{m-1}{2}=\frac{B+m}{2}=\frac{m}{2}+\frac{n}{2m}.$

選択肢別の誤答解説

• ア: $m+\frac{n}{m}$
  この式はブロック内探索を最悪で $m$ 回と仮定したうえでブロック選定のコストを $n/m$ と見なした形です。問題は「平均比較回数」を問うており、ブロック内探索は平均で $(m-1)/2$ 回であり $m$ を使うのは過大評価です。
• イ: $\frac{m}{2}+\frac{n}{2m}$
  正解です。上で示した通り、ブロック選定期待値 $\frac{B+1}{2}$ とブロック内期待値 $\frac{m-1}{2}$ の和に対応します（$B=n/m$ を代入）。
• ウ: $\frac{n}{m}$
  これはブロック選定の回数だけ、つまりブロック数 $B$ をそのまま期待値と誤認している式です。実際のブロック選定期待値は平均で $(B+1)/2$ ですし、ブロック内探索のコストを無視しています。
• エ: $\frac{n}{2m}$
  これはブロック内探索の期待値のみ（または $B/2$ と混同したもの）を表しており、ブロック選定に要する比較をまったく含んでいません。

よくある誤解

• ブロック内の平均比較回数を $(m+1)/2$ としてしまう誤り
  これは「1からmまでの平均」と見なしてしまう誤解ですが、ブロックの最後尾に目的値がある場合はブロック内探索を行わないため、最後尾の位置 $r=m$ に対する内部比較は $0$ 回です。正しくは $(m-1)/2$ です。
• ブロック選定期待値を $B$（最大値）とする誤り
  ブロックは均等確率で目的値を含むため、平均は $(B+1)/2$ であり最大値 $B$ を使うべきではありません。
• 「最後尾を比較したときの比較を二重に数える」ミス
  最後尾が目的値であれば内部探索は不要であり、その比較はブロック選定側の比較として既にカウントされています。内部探索側で再度カウントしてはいけません。

補足コラム

FAQ