問6応用情報技術者 平成30年度 春期

解説

正解は2。探索は2段階に分かれる。
1段目：ブロックはn/m個あり、その最後尾のデータだけを線形探索する。線形探索の平均比較回数は件数の半分なので、n/(2m)回。
2段目：見つけたブロック内のm個を線形探索するので、平均m/2回。
合計はm/2＋n/(2m)となる。mが十分に大きいという条件は、半分で近似してよいことを示している。

• 1のm＋n/mは、両段とも全件を比べる最悪の回数で、平均ではない。
• 3のn/mは、1段目の最悪の回数だけで、2段目を数えていない。
• 4のn/(2m)は、1段目の平均だけで、ブロック内の探索を落としている。

根拠：線形探索の平均比較回数は対象件数の約半分。