平成24年度 春期 応用情報技術者試験 午前 問9
テクノロジ／アルゴリズム相異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
出典：平成24年度 春期 応用情報技術者試験 午前 問9
- アm ＋ n/m
- イm/2 ＋ n/2m
- ウn/m
- エn/2m
正解：イ
解説
ブロック代表値の線形探索では平均してm/2回の比較（ブロックの発見まで）が必要で，見つかったブロック内をさらに線形探索するとブロックサイズmに対して平均m/2回の比較が必要ですが，これはブロック内探索の比較回数として1/m（ブロック数がn/mであることを考慮）の重みが付き，全体として m/2＋n/2m 回の平均比較回数になります。
選択肢ごとの解説
- ア誤り。mとn/mを足す形は，ブロック数分の探索を線形に行う場合の見積りに相当し，本手法の平均比較回数とは異なります。
- イ正しい。ブロック代表値の探索（平均m/2回）とブロック内探索（平均n/2m回）を合計した式です。
- ウ誤り。n/mはブロックの個数を表す式であり，比較回数の平均を表す式ではありません。
- エ誤り。n/2mはブロック内探索部分のみを表しており，ブロック代表値の探索の比較回数が含まれていません。