ブロック分割による探索の平均比較回数
出典: 令和7年度 秋期 応用情報技術者試験 午前 問6 (IPA)
異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
- ア m ＋ n / m
- イ m / 2 ＋ n / (2m)
- ウ n / m
- エ n / (2m)
正解と解説を見る
正解: イ
- ア: ブロック内も、ブロックの選択も、平均すると半分を調べれば見つかります。全部を調べる回数 (m と n / m) を足した式なので、2 倍になっています。
- イ: ブロックを探す平均 n / (2m) 回と、ブロック内を探す平均 m / 2 回の合計なので正しい式です。
- ウ: n / m はブロックの最後尾をすべて調べたときの回数で、平均ではありません。ブロック内の探索の回数も入っていません。
- エ: n / (2m) はブロックを探す平均回数だけです。ブロック内を探す m / 2 回が足りません。
ポイント
- ブロックの数は n / m 個。各ブロックの最後尾だけを線形探索するので、目的のブロックを見つけるまでの平均比較回数は約 n / (2m) 回です。
- 見つけたブロックの中 (m 個) を線形探索するので、平均比較回数は約 m / 2 回です。
- 合計で m / 2 ＋ n / (2m) になります。