OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

内部ハッシュ法

  • すぐに回答を!
  • 質問No.176259
  • 閲覧数348
  • ありがとう数3
  • 気になる数1
  • 回答数2
  • コメント数0

お礼率 100% (14/14)

m(m-1)・・・(m-i+1)/B(B-1)・・・(B-i+1)≒(m/B)^i
となぜ書けるのですか?
だんだん値がだんだん小さくなっていくから
こうなる では、あんまり良くなくて、もう少し
ちゃんとしたものを・・・ということなんです・・・。
わかる方がいらっしゃったら教えてください。
通報する
  • 回答数2
  • 気になる1
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル13

ベストアンサー率 64% (700/1089)

内部ハッシュ法はよく知りませんが,
式の方だけ分析してみましょう.

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
で,近似が正確な値を与えますから.
お礼コメント
kakera

お礼率 100% (14/14)

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

その他の回答 (全1件)

  • 回答No.1
レベル14

ベストアンサー率 57% (1014/1775)

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 とやっただけのことです。 ...続きを読む
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
とやっただけのことです。
お礼コメント
kakera

お礼率 100% (14/14)

なるほど!!
わかりやすく教えていただき、ありがとうございましたm(_ _)m
これでレポートもなんとかできそうです。
投稿日時 - 2001-11-29 16:07:18
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ