問題
異なる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が平均比較回数となる。（出典: 平成30年度 春期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習