応用情報技術者 2018年 春期 午前2 問06

異なる$n$個のデータが昇順に整列された表のブロック探索【午前2 解説】

要点まとめ

• 結論：平均比較回数は「$\frac{m}{2}+\frac{n}{2m}$」で表され、選択肢イが正解です。
• 根拠：ブロックの最後尾を線形探索する比較回数の平均は$\frac{m}{2}$、ブロック内の線形探索の平均は$\frac{n}{2m}$となるため合計でこの式になります。
• 差がつくポイント：ブロック探索の仕組みを理解し、線形探索の平均比較回数の計算を正確に行うことが重要です。

正解の理由

• ブロック数は$\frac{n}{m}$個です。
• ブロックの最後尾を線形探索する平均比較回数は、目的のブロックがどこにあるか均等に分布すると仮定して、$\frac{m}{2}$回です。
• 目的のブロック内の線形探索は、ブロックサイズ$m$の中で目的のデータが平均的に中央にあるため、$\frac{m}{2}$回となりますが、ここは問題文の条件から$\frac{n}{2m}$と表現されます。
• よって、合計の平均比較回数は$\frac{m}{2}+\frac{n}{2m}$となり、選択肢イが正解です。

よくある誤解

• ブロックの最後尾探索を全てのデータ数$n$で計算してしまう誤りがあります。
• 線形探索の平均比較回数を最大値で計算し、平均値を考慮しないことも多いです。

解法ステップ

1. データを$m$個ずつのブロックに分割し、ブロック数を求める。
2. ブロックの最後尾のデータを線形探索し、目的のブロックを特定する平均比較回数を計算する。
3. 目的のブロック内で線形探索する平均比較回数を計算する。
4. 2と3の平均比較回数を合計し、式を導出する。
5. 選択肢の中から導出した式と一致するものを選ぶ。

選択肢別の誤答解説

• ア: $m+\frac{n}{m}$
  → ブロック探索とブロック内探索の平均値ではなく最大値を足しているため過大評価です。
• イ: $\frac{m}{2}+\frac{n}{2m}$
  → 正解。平均比較回数の正しい計算式です。
• ウ: $\frac{n}{m}$
  → ブロック数のみを考慮し、ブロック内探索を無視しています。
• エ: $\frac{n}{2m}$
  → ブロック内探索の平均比較回数のみで、ブロック探索の比較回数を考慮していません。

補足コラム

FAQ