平成30年度春期 応用情報技術者試験 午前 問6
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
- ア m＋n/m
- イ m/2＋n/2m
- ウ n/m
- エ n/2m
解答・解説を見る
正解：イ
AI解説
IPA公式解答例による正解は「イ」。ブロック探索(とび越し探索)の平均比較回数を求める問題である。ブロック数はn/m個なので、目的ブロックを線形探索で見つける平均比較回数は(n/m)/2=n/2m回。次にブロック内のm個のデータを線形探索する平均比較回数はm/2回。両者の和でm/2+n/2m回となる(mが十分大きいので端数の+1/2などは無視できる)。 ア: 誤り。m+n/mは平均ではなく、ブロック内探索とブロック探索をそれぞれ最悪(全件)まで行う場合に近い回数である。 イ: 正しい。ブロック探索の平均n/2mとブロック内探索の平均m/2の合計である。 ウ: 誤り。n/mはブロック数そのものであり、比較回数の平均ではない。 エ: 誤り。n/2mはブロックを特定するまでの平均比較回数だけを表し、ブロック内の線形探索分m/2が抜けている。 💡 線形探索の平均比較回数は(要素数)/2、これを「ブロックの探索」と「ブロック内の探索」の2段階に適用して足すだけ。なおm/2+n/2mはm=√nのとき最小になる、という発展知識も出題例がある。
出典：平成30年度 春期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。