マルチスレッドの効率(3)

前回の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

効率は、

 \frac{1}{1 + _{2l}C_l 2^{-2l}

となる。
Nが偶数の場合も同様に求められて、
l = [ N / 2 ]
とすれば、奇数の場合と同様になる。