応用情報技術者 2012年 春期 午前2 問09

相異なる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}{m}$であるため、全体の平均比較回数は$\frac{n}{2m}$となります。
• したがって、合計の平均比較回数は $\frac{m}{2}+\frac{n}{2m}$ となり、選択肢の中ではイが正解です。

よくある誤解

• ブロックの最後尾探索を二分探索と混同し、$\log$計算をしてしまう。
• ブロック内の探索回数を全体の$n$で割らず、単純に$m$の半分と考えてしまう。

解法ステップ

1. データを$m$個ずつのブロックに分割し、ブロック数を$\frac{n}{m}$とする。
2. 目的のデータが存在するブロックを探すため、各ブロックの最後尾のデータを線形探索する。平均比較回数は$\frac{m}{2}$。
3. 目的のブロック内で目的のデータを線形探索する。平均比較回数はブロックサイズ$m$の半分、すなわち$\frac{m}{2}$。
4. しかし、問題文の条件から、全体の平均比較回数は$\frac{m}{2}+\frac{n}{2m}$となる。
5. 選択肢の中からこの式に合致するものを選ぶ。

選択肢別の誤答解説

• ア: $m+\frac{n}{m}$
  → 線形探索の平均回数を考慮せず、最大回数をそのまま足している。平均値ではない。
• イ: $\frac{m}{2}+\frac{n}{2m}$
  → 正解。ブロック探索とブロック内探索の平均比較回数の和。
• ウ: $\frac{n}{m}$
  → ブロック数のみを考慮し、ブロック内探索を無視している。
• エ: $\frac{n}{2m}$
  → ブロック内探索の平均回数のみを考慮し、ブロック探索を無視している。

補足コラム

FAQ