問題
異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、m は十分に大きく、n は m の倍数とし、目的のデータは必ず表の中に存在するものとする。
選択肢
- 1m ＋ n／m
- 2m／2 ＋ n／（2m）
- 3n／m
- 4n／（2m）
正解
2. m／2 ＋ n／（2m）
詳しい解説を見る解説を閉じる
解説
まずブロック数は n／m 個で、各ブロック末尾のデータを線形探索すると平均比較回数は約 (n／m)／2＝n／(2m) 回です。次に該当ブロック（m 個のデータ）内を線形探索すると平均約 m／2 回かかります。両者を合計すると m／2 ＋ n／(2m) となり、イが正解です。これは線形探索を 2 段階に分けることで、単純な線形探索の平均 n／2 回より効率を高める手法です。（出典: 令和7年度 秋期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習