異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
イ. m/2＋n/2m
2段階の線形探索の平均比較回数を求める問題。線形探索の平均比較回数は「対象件数の約半分」になることがポイント。第1段階では n 個を m 個ずつに分けた n/m 個のブロックの最後尾だけを線形探索するので、平均比較回数は (n/m)÷2 ＝ n/2m 回。第2段階では目的のブロック内の m 個を線形探索するので、平均比較回数は m÷2 ＝ m/2 回。両者を合計すると m/2 ＋ n/2m となり、イが正解。「探索対象の数の半分」という線形探索の平均回数を2回の探索それぞれに当てはめるのがコツ。
応用情報技術者試験 平成30年度春期 午前 の過去問一覧へ戻る・問6