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