令和7年度 高度共通 午前I（PM試験） 問3
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、mは十分に大きく、nはmの倍数とし、目的のデータは必ず表の中に存在するものとする。
- ア m + n/m
- イ m/2 + n/(2m)
- ウ n/m
- エ n/(2m)
解答・解説を見る
正解：イ
AI解説
これはブロック探索（とび越し探索）の平均比較回数を求める問題である。ブロック数はn/m個なので、目的ブロックを見つける線形探索の平均比較回数は(n/m)/2＝n/(2m)回。次に、m個のデータをもつブロック内の線形探索の平均比較回数はm/2回。両者の和 m/2＋n/(2m) が全体の平均比較回数となる（線形探索の平均は「要素数/2」で近似できることを使う）。 ア: m＋n/mは、各段階で最悪（全件比較）した場合に近い回数であり、平均比較回数ではない。 イ: 正解。ブロック探索の平均n/(2m)回とブロック内探索の平均m/2回の合計がm/2＋n/(2m)である。 ウ: n/mはブロック数そのもの（＝ブロック探索の最悪回数）であり、ブロック内の探索が含まれていない。 エ: n/(2m)はブロック探索の平均回数だけで、ブロック内の線形探索m/2回が抜けている。 💡 「線形探索の平均比較回数≒要素数の半分」が基本。2段階探索は各段階の平均を足すだけでよい。なおm/2+n/(2m)はm=√nのとき最小になる（相加相乗平均）ことも知っておくと発展問題に対応できる。
出典：令和7年度 秋期 プロジェクトマネージャ試験 午前I 問3 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。