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

ブロック探索の平均比較回数【午前2解説】

正解の理由

解法ステップ

1. ブロック数を $B=\frac{n}{m}$ とおく。
2. ブロックの最後尾同士を線形に比較して目的ブロックを見つける際、目的ブロックが $1$〜$B$ のいずれかで均等に存在するので期待比較回数は $$E_{\text{block}}=\frac{1+2+\cdots +B}{B}=\frac{B+1}{2}.$$
3. 当該ブロック内での線形探索は末尾が既に比較されている点に注意。ブロック内の位置が末尾（確率 $1/m$）なら追加比較は $0$、それ以外なら位置 $k(1\le k\le m-1)$ の比較回数は $k$。よって期待値は $$E_{\text{in}}=\frac{1}{m}\sum _{k=1}^{m-1}k=\frac{m-1}{2}.$$
4. 合計期待比較回数は $E_{\text{block}}+E_{\text{in}}=\frac{B+1}{2}+\frac{m-1}{2}=\frac{B+m}{2}=\frac{m}{2}+\frac{n}{2m}$。

選択肢別の誤答解説

• ア: $m+\frac{n}{m}$
  誤り。ブロック探索とブロック内探索の「平均」を取っていない（最悪の場合の和に近い）。平均比較回数はそれぞれの期待値の和であり、$+1$ や係数の差が残るため異なる。
• イ: $\frac{m}{2}+\frac{n}{2m}$
  正解。上の導出どおり、ブロック探索 $\frac{B+1}{2}$ とブロック内 $\frac{m-1}{2}$ の和で $=\frac{B+m}{2}=\frac{m}{2}+\frac{n}{2m}$ になる。
• ウ: $\frac{n}{m}$
  誤り。これはブロック数 $B$ のみを数えた値で、ブロック内探索の平均が考慮されていない。
• エ: $\frac{n}{2m}$
  誤り。ブロック内探索のみ（平均的な位置 $\approx m/2$ を無視）またはブロック探索の一部しか反映しておらず、合計期待値としては不十分。

よくある誤解

1. ブロック内探索の期待値を $(m+1)/2$ とする誤り
   • 末尾要素は既にブロック探索で比較済みで、該当が末尾なら追加比較は不要になるため、内部探索の期待値は $(m-1)/2$ が正しい。
2. ブロック探索を最悪ケース $B$ として扱い平均化を忘れる
   • 各ブロックに目的データが均等に存在する仮定があるため期待は $(B+1)/2$ となる。
3. $B$ と $m$ の関係を混同する
   • $B=\frac{n}{m}$ であることを明確にして式変形する。

補足コラム

• 最適なブロックサイズを連続変数として求めると期待比較回数 $$E(m)=\frac{m}{2}+\frac{n}{2m}$$ の $m$ に関する最小化は微分で行えます。$E^{\prime }(m)=\frac{1}{2}-\frac{n}{2m^2}=0$ より $m=\sqrt{n}$ が最適（連続解）。このときの期待値は約 $\sqrt{n}$。つまり二段探索は適切に分割すると平方根オーダーの平均比較回数を達成します。
• 実装上の注意：ブロックを固定長配列で持つとメモリ局所性が良く高速になることが多い。二分探索とのトレードオフを考慮すること。

FAQ