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

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

したがって，平均比較回数は m/2 ＋ n/(2m) となります。

• ア: m ＋ n/m
  誤り。ブロックの探索とブロック内の探索の両方を，最悪の比較回数（全件比較）で数えた式です。平均ではありません。

• イ: m/2 ＋ n/(2m)
  正しい。ブロックの探索の平均 n/(2m) とブロック内の探索の平均 m/2 の和であり，平均比較回数を表します。

• ウ: n/m
  誤り。ブロックを探すときの最大比較回数だけで，ブロック内の探索が含まれていません。

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

答え

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