ブロック分割した表の探索回数
出典: 平成30年度 春期 応用情報技術者試験 午前 問6 (IPA)
異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
- ア m + n/m
- イ m/2 + n/(2m)
- ウ n/m
- エ n/(2m)
正解と解説を見る
正解: イ
- ア: 平均ではなく、最大の比較回数 (最後のブロックの最後のデータ) に当たります。
- イ: ブロックの探索に平均 n/(2m) 回、ブロック内の探索に平均 m/2 回掛かるので、正しい答えです。
- ウ: n/m はブロックの数そのもので、ブロックを全て調べたときの回数です。ブロック内の探索も入っていません。
- エ: n/(2m) はブロックを探す部分だけの平均回数です。ブロック内の探索 m/2 回も加えます。
ポイント
- ブロックの数は n/m 個 です。各ブロックの最後尾を線形探索して目的のブロックを見つけるのに、平均 n/(2m) 回 比較します。
- ブロック内には m 個のデータがあるので、その中の線形探索は平均 m/2 回 です。
- 合計で m/2 ＋ n/(2m) です。