平成30年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
出典：平成30年度 春期 応用情報技術者試験 午前 問6
- アm ＋ n/m
- イm/2 ＋ n/(2m)
- ウn/m
- エn/(2m)
正解：イ
解説
ブロック単位の線形探索では平均してn/m個のブロックの末尾を比較し，目的のブロックが見つかった後にブロック内をさらに線形探索するため平均m/2回の比較が必要です。ブロック数の探索の平均比較回数はn/(2m)（n/m個の半分）となるため，全体の平均比較回数はm/2＋n/(2m)です。
選択肢ごとの解説
- ア誤り。m＋n/mは，各段の探索回数を平均ではなく最大値に近い形でそのまま加算した場合に得られる式で，平均比較回数を表していません。
- イ正しい。ブロック内探索の平均m/2回と，ブロック探索の平均n/(2m)回を合計するとm/2＋n/(2m)になります。
- ウ誤り。n/mは，ブロックの探索段階だけを考慮し，ブロック内の線形探索の比較回数を含めていない式です。
- エ誤り。n/(2m)は，ブロックを見つけるための探索段階の平均比較回数のみであり，ブロック内探索の平均m/2回を加え忘れています。