作者kyuudonut (善良老百姓)
看板Grad-ProbAsk
標題Re: [理工] 105 交大 資結 Hash
時間Wed Feb 1 20:13:29 2017
:
: http://imgur.com/a/rsJdm
:
: 推 Transfat: 32題，在Uniform hashing假設下，Expected hashing of 12/23 18:21
: → Transfat: probs 的cost等於是找到空位的cost, 因為有n/m被佔滿了 12/23 18:21
: → Transfat: 所以空位比例是1/(1-n/m) // 我是這樣想啦 12/23 18:22
空位比例應該是 1 - n/m ，取倒數就不太知道幾何意義是什麼
花的 cost 應該是從滿的位置比例下去思考？
我有一些不同的想法 不知道有沒有謬誤
令 n/m 為發生 collision 的機率，故 (1 - n/m) 為找到空位的機率
故期望值應為
(n/m)*(1-n/m)*2 + (n/m)^2*(1-n/m)*3 + ...
比較次數之所以從2開始，是因爲失敗次數加上一次成功找到空位的比較次數
附上計算過程：
http://imgur.com/a/0VWt4
由於題目問可能發生的最多比較次數，故可以合理假設 n 趨近於 m
計算過程的最後一項，左邊因為有平方項加上n趨近於m，會趨近於1
大guy4這樣 @@
--
▲ ◢◤▅▄▃▁All you have to do is ●嚐嚐老納▍
▲ ____ ◣Put Your banana in my candy cave▅▅▅▅▄ 的香蕉吧 -■ ▎
▲ ⊙ ▲◆幹妳媽的 我不哈洋鯰◆ ╰ ◢ 〃〃 〃〃▼ ╰│╯ <
▲ ◣ ╯ ▄▂ ▄▂▼ ╰╮|▆◤
、 ＣＨＡＲＬＩＥ ～ ╯ ～ ▲●◣ ╰ ▇▂▃
\ 皿 The Unicorn ψjeans1020 ●───● ◣◥◣◢◤ ◢◣
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.166.121.179
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485951215.A.6CF.html
推 hut326521: 我覺得你想法是對的 但前面要加上第一次沒碰撞的成本 02/01 21:54
→ hut326521: 下面是生成函數的推導..字醜傷眼抱歉QQ 02/01 21:59
啊啊，謝謝是我漏算了，謝謝
因為我第一次寫的時候並沒有加上成功的比較次數，只有算失敗的比較次數
原來式子可以這麼漂亮啊 QAQ (第一次自己推成功好港動R)
※ 編輯: kyuudonut (220.132.251.85), 02/01/2017 22:03:29
推 yupog2003: 感謝兩位，原來這題可以這樣推 02/01 22:07
推 bernie0507: 感謝 02/01 23:33
推 Transfat: 了解，謝謝 02/02 10:42
推 k1992313: 換個方向，其實可以想成第一次搜尋+第二次搜尋...之成 02/02 15:10
推 k1992313: 本，式子的意義會明朗很多 02/02 15:11