平成21年度春期 応用情報技術者試験 午前 問8

正解：イ

AI解説

ブロック分割探索では、まず各ブロックの最後尾をm個おきに線形探索してブロックを特定し（平均m/2回）、次にブロック内をさらに線形探索する（平均m/2回）。ブロック数はn/mなので、ブロック特定側の平均比較回数はn/2mとなり、合計するとm/2+n/2mとなる。 ア: m+n/mは各段階の探索回数を平均せずに単純加算した式に近く、平均比較回数の式としては適切でない。 イ: m/2+n/2mが正しい。ブロック内探索の平均m/2回と、ブロック特定探索の平均n/2m回を合計した式である。これが正解。 ウ: n/mはブロック数そのものであり、比較回数を表す式ではない。 エ: n/2mはブロック特定探索の平均回数に相当する部分のみであり、ブロック内探索の分が抜けている。 💡 ブロック探索の平均比較回数は「ブロック特定の探索」と「ブロック内探索」の2段階をそれぞれ平均（回数の半分）してから足し合わせる、という2段階平均の考え方がポイント。