平成24年度 春期 応用情報技術者試験 午前 問9

• ブロックの数は n/m 個です。各ブロックの最後尾を線形探索するので，目的のブロックを見つけるまでの平均比較回数は約 n/(2m) 回です。
• ブロック内には m 個のデータがあり，線形探索の平均比較回数は約 m/2 回です（m は十分大きいので近似できます）。

平均比較回数は m/2 ＋ n/(2m) です。

• ア: m ＋ n/m
  誤り。ブロック探索・ブロック内探索とも最悪の場合の比較回数の和であり，平均ではありません。

• イ: m/2 ＋ n/(2m)
  正しい。ブロックの探索で平均 n/(2m) 回，ブロック内の探索で平均 m/2 回なので，合計 m/2 ＋ n/(2m) 回です。

• ウ: n/m
  誤り。ブロック数そのもので，ブロック探索の最悪回数にすぎず，ブロック内の探索も含んでいません。

• エ: n/(2m)
  誤り。ブロックを探す平均回数だけで，ブロック内の探索回数 m/2 が含まれていません。

答え

イ: m/2 ＋ n/(2m)