Re: [理工] 105 交大資結 Hash

看板Grad-ProbAsk作者kyuudonut (善良老百姓)時間8年前 (2017/02/01 20:13)推噓7(7推 0噓 1→)

留言8則, 5人參與討論串2/2 (看更多)

: : 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, , 1^F

02/01 21:54, 1^F

推

hut326521

02/01 21:58, , 2^F

02/01 21:58, 2^F