2008-8 第1問 (2)

(a)
m = 1のとき、C = 1, C_max = 1 は明らか

m = 2のとき、
v = p₂ ならば比較は1回
そうでなければ比較は2回
よって、
C = (1 + 2 * 3) / 2² = 7/4
C_max = 2

m = 3のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が2²通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * (2² + 1)) / 2³ = 5/2
C_max = 3

m = 4のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が2²通り
比較が4回の場合が2³通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * 2² + 4 * (2³ + 1)) / 2⁴ = 53/16
C_max = 4


(b)
比較回数iで探索が成功する場合が2^i-1通り存在し、また探索が失敗する場合の比較回数はm回なので、
C = ( Σ_{k∈[1, m]} ( k * 2^k-1 ) + m ) / 2^m

ここで、S = Σ_{k∈[1, m]} ( k * 2^k-1 ) とすると、
S = 1 * 1 + 2 * 2 + 3 * 2² + ・・・ + m * 2^m-1
2S =           1 * 2 + 2 * 2² + ・・・ + (m-1) * 2^m-1 + m * 2^m

よって、
-S = 1 + 2 + 2² + ・・・ + 2^m-1 - m * 2^m
S = (m - 1) * 2^m + 1

以上より、
C = ((m - 1) * 2^m + 1 + m) / 2^m
　= m - 1 + (m + 1) / 2^m
C_max = m