m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1)≒(m/B)^i
となぜ書けるのですか?
だんだん値がだんだん小さくなっていくから
こうなる では、あんまり良くなくて、もう少し
ちゃんとしたものを・・・ということなんです・・・。
わかる方がいらっしゃったら教えてください。

A 回答 (2件)

内部ハッシュ法はよく知りませんが,


式の方だけ分析してみましょう.

stomachman さんのおっしゃるとおりなのですが,
もう少し突っ込んでみましょう.
問題の式をから (m/B)^i という因子を引っ張り出すと
(1)  m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1) = (m/B)^i {f(m,i)/f(B,i)}
の形になります.
(2)  f(n,i) = 1 (1-1/n) (1-2/n) ・・・ {1-(i-1)/n}
問題の近似式は {f(m,i)/f(B,i)}≒1 としているわけです.
B,m >> i なら近似がよいのは直感的に明らかですが,
近似の程度を見てみましょう.
(2)を展開して,最低次の項までとると
(3)  f(n,i) ≒ 1 - Σ(j=1~i-1) (j/n) ≒ 1 - i(i-1)/ 2n
ですから
(4)  f(m,i)/f(B,i) ≒ 1 + i(i-1)/2 {1/B - 1/m}
で近似の程度が明確になりました.
ん,B=m だと最低次の補正項が消えるのか?
そりゃそうです.
B=m なら
(5)  m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1) = 1 = (m/B)^i
で,近似が正確な値を与えますから.
    • good
    • 0
この回答へのお礼

詳しく教えていただき、ありがとうございましたm(_ _)m
順序があって、大変わかりやすかったです。
「なるほど・・・」と感動しました。
これからちゃんと理解しているか確認のためも含めて、
レポートを書いてみようと思います。

お礼日時:2001/11/29 16:10

m=8, i=8, B=9としてみれば左辺=0.11, 右辺=0.39。

あんまり似てませんねえ。

この近似は、
m, Bがiに比べてうんと大きいときだけ有効なんですよ。

m/B≒(m-1)/(B-1)≒…(m-i+1)/(B-i+1)
と近似して、
だから左辺≒(m/B)^i
とやっただけのことです。
    • good
    • 0
この回答へのお礼

なるほど!!
わかりやすく教えていただき、ありがとうございましたm(_ _)m
これでレポートもなんとかできそうです。

お礼日時:2001/11/29 16:07

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報