令和7年度 秋期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
出典：令和7年度 秋期 応用情報技術者試験 午前 問6
- アm＋n/m
- イm/2＋n/(2m)
- ウn/m
- エn/(2m)
正解：イ
解説
n 個のデータを m 個ずつのブロックに分けるとブロック数は n/m 個です。まず各ブロックの最後尾だけを線形探索するので，この段階の平均比較回数は (n/m)÷2＝n/(2m) 回です。次に該当ブロック内の m 個を線形探索するので平均 m/2 回です。両者を合計して m/2＋n/(2m) 回となります。
選択肢ごとの解説
- ア誤り。m＋n/m は，ブロック間・ブロック内のいずれも全件を比較した最悪の場合の回数であり，平均比較回数ではありません。
- イ正しい。ブロック内の平均 m/2 回と，ブロックを探す段階の平均 n/(2m) 回の合計です。
- ウ誤り。n/m はブロック数そのもの，すなわちブロックを探す段階の最悪比較回数であり，ブロック内の探索が考慮されていません。
- エ誤り。n/(2m) はブロックを探す段階の平均比較回数だけで，ブロック内の線形探索の平均 m/2 回が抜けています。