アルゴリズムは、やさしい図やアニメーションで「わかった気にさせる」ことは簡単だが、実際に理解しようとするとどうしても数式なしでは乗り切れない。というより、数式が一番正確にかつ最短に表現できるから数式が使われているのであって、それ以外のアプローチは子供騙し.... になることが多い。
ボールとビン問題は、アルゴリズムの一つである。
Bernoulli trialsという法則があり、間の証明とかはすっとばして結論だけ言うと、
binomial 分布
E[X] = np (b(k;n, p)n = nCk * p^k * q^n-k)
geometric 分布
E[X] = 1/p
という2つの公式がある。
まず、1..b 個のコーンがあったとする。
で、この箱たちに輪っかをなげまくって、輪っかは1..bいずれかのコーンにはいるとする（スカはなし）。
ちな、輪っかを投げた回数をnとすると、
(1) 特定のコーンに輪っかはいくつ入る？
という命題については、まず1回の輪投げにつきそれが所定のコーンにはまる確率は 1/b なので、binomial 分布より、
n/b個 が、正解である。つまりコーンが10個あって100回なげれば、特定のコーンには10個入る、と考えるのが妥当、ということ。
(2) 特定のコーンに輪っかがはいるまでに、だいたい何回輪っかを投げればいい？
まあだいたい、というのは平均ということなんだけど、この命題は、
geometric分布を用いる。つまり、1/p = 1/(1/b) なので、つまり b回投げれば、まあ1回ははいるっしょ、ということである。
(3) b個の全部の輪っかに対して、それぞれ最低１個ずつはまるためには、何回投げればいい？という命題については、
まずnという輪っかを投げた回数の他に、まだ輪っかが入ってないコーンに輪っかがささった時の回数をiとする（この場合の回数をステージ、と呼ぶこととする）。
すると、i ステージ目には、i-1個のコーンに輪っかが入っていることになるから、 b-(i-1) = b-i+1 個のコーンがまだまっさら、ということになる。
つまり、iステージ目でまっさらな（１個も輪っかが入っていない）コーンに輪っかがはいる確率は
(b-i+1) ÷b
ってことになる。
ni を、iステージに達するまでに投げた輪っかの回数とする。すると、b個全部のコーンにいれるために必要な必要な投げた回数は、
b
n = Σ ni
i=1
となる。（つまりそれぞれのステージに達するまでになげた回数の和）
niに達するまでの確率は、さっき証明された通り、(b-i+1)/b だから、niに達するまでに投げなきゃいけない回数は、geometric分布をもちいて、
E[ni] = b/(b-i+1)
で、これを i=1 から b のパターンまで全部足すから、
b
n = Σ E[ni]
i=1
b
= Σ b/(b-i+1)
i=1
b
= bΣ 1/i
i=1
これ、上記なんで 1/iに変換できるかっていうと、具体数をあてはめるとわかる。
b-1+1 > b-2+1 > b-3+1 > ... > b-b+1 ってなるのが上で、これってつまり
b > b-1 > b-2 > ....> 1 なわけだから、あ、じゃあ i=1 から bを順番に足した整数の順列じゃね？となりこの言い換えができる。
そして、
= b(lnb + O(1))
でフィニッシュ。
この変換は、harmonic seriesという数式を用いていて、
1+1/2+1/3...1/n って足される和は、 lnn+O(1) とされる。lnnってのは logn っていうことです（対数は省略）
ちなみに、多分前の記事で触れたと思うけど Oはビッグオーノーテーションといって、雑に言うと「この関数遅くてこの値ね」、ということが言いたい。
fn = O(n) だったら
関数fnは遅くて（最悪のケース）an+b ね！あ、でもbとかaとか nがめっちゃでかかったら存在価値ないんだわ、影薄いんだわ、インパクトないんだわ、だから O(n)
みたいな感じである。
現実のプログラミングでは、ハッシュ関連で使うらしい。
まあそんなかんじで。
No comments:
Post a Comment