前回のEの計算は、
これを使えば簡単なことに昨日の夜気がついた。
(n - k)nCk = nn-1Ck
まず、
N = 2l + 1
と表せる場合を考える。
I = NNC0 + ... + (N - l)NCl + (N - l)NCl+1 + ... + NNCN
とおくと、
I / 2 = 2N-1E = NNC0 + ... + (N - l)NCl
= NN-1C0 + ... + NN-1Cl
= N2N-2 + NN-1Cl / 2
平均時間は、
E = N / 2 + NN-1Cl / 2N
効率は、
となる。
Nが偶数の場合も同様に求められて、
l = [ N / 2 ]
とすれば、奇数の場合と同様になる。