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