問題8
相異なるn 個のデータが昇順に整列された表がある。 この表をm 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。 次に、当該ブロック内を線形探索して目的のデータを探し出す。 このときの平均比較回数を表す式はどれか。 ここで、m は十分大きく、n はm の倍数とし、目的のデータは必ず表の中に存在するものとする。
解答・解説を見る
解答：イ
- ブロックは全部で、
個ある。n m - 線形探索の比較回数は、最小で1回，最大でデータの総和である。したがって、データの総数÷2で目的のデータを見つけることができる。したがって、平均比較回数は、
となる。n 2m - ブロックの中身の検索を行う。個々のブロックはm個なので、
となる。n 2 - したがって、
となる。n ＋ n 2m 2