相違なるn 個のデータが昇順に整列された表がある。
この表をm 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。
次に、当該ブロック内を線形探索して目的のデータを探し出す。
このときの平均比較回数を表す式はどれか。
ここで、m は十分大きく、n はm の倍数とし、目的のデータは必ず表の中に存在するものとする。
| ア |  |
イ |  |
ウ |  |
エ |  |
答え イ
【解説】
n 個のデータをm 個ずつのブロックに分割したときのブロックの個数は個である。
最初の、目的データが存在するブロックを探すための線形探索のときの平均比較回数は回である。
次に、当該ブロックのm 個のデータから目的のデータを線形探索したときの平均比較回数は
回である。
したがって、問題文の方法でデータの探索を行って時の平均比較回数は
(イ)になる。
“探索”処理において最も時間のかかる処理が“比較”であるため、探索処理の処理時間は比較回数に比例する。
そのため、この問題ではこの処理方法の“平均比較回数”を求めることで、処置方法の能力を求めている。
【キーワード】
・線形探索
- 線形探索
線形探索とは目的とするデータを、1つ1つ順番に比較し探す方法である。
線形探索では探す元のデータが整列されてなくてもよい。
n 個のデータに対し、線形探索を行ったときの平均比較回数は“n /2”である。
もっと、「線形探索」について調べてみよう。
戻る
一覧へ
次へ