相異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、m は十分に大きく、n は m の倍数とし、目的のデータは必ず表の中に存在するものとする。
ア m ＋ n／m
イ m／2 ＋ n／2m
ウ n／m
エ n／2m
イ
N個のデータを線形検索した場合、平均比較回数は N／2である。
これを踏まえる。
ブロックの個数は n／m個であるから、目的のデータが存在するブロックを探し出すための平均比較回数は n／2m 回である。
さらに、当該ブロック内で目的のデータを探し出すための平均比較回数は m／2 回である。
従って、平均比較回数は m／2 ＋ n／2m である。
| 問７ | 目次 | 問９ |