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

2008-8 第1問 (1)

(a)
v = k_j のとき比較回数は j回
探索失敗の場合、比較回数は n回

よって、
C = Σ_j∈[1,n] ( j / 2n ) + n / 2 = (3n + 1) / 4
C_max = n

(b)
C = Σ_j∈[1,n] ( j / 2^j ) + n / 2ⁿ

まず、C = 1 + Σ_j∈[1,n-1] (1 / 2ⁿ) を示す。

n = 1のとき、C = 1

Σ_j∈[1,k] ( j / 2^j ) + k / 2^k = 1 + Σ_j∈[1,k-1] (1 / 2^k) とすると、
Σ_j∈[1,k+1] ( j / 2^j ) + (k + 1) / 2^k+1
= Σ_j∈[1,k] ( j / 2^j ) + (k + 1) / 2^k
= 1 + Σ_j∈[1,k-1] (1 / 2^k) + 1 / 2^k
= 1 + Σ_j∈[1,k] (1 / 2^k)

よって、数学的帰納法より、
C = 1 + Σ_j∈[1,n-1] (1 / 2ⁿ)

Σ_j∈[1,n-1] (1 / 2ⁿ) < 1 なので、C < 2