作者mingrong2 (mingrong)
看板Examination
標題[課業] 資料結構
時間Fri Mar 22 17:08:44 2013
問題一:
設一表格長度為n,表格內第i項目之取用機率為Pi，
查詢表內第i項目比較之次數為Ci，請寫出平均查詢長度之公式!
答案:ΣCiPi+1
這題我認為答案是ΣCiPi，不知道為什麼會多加1
問題二:
如果hash table有m個位置，現在有n個資料要 依序插入，
請計算整個插入過程中，平均會有幾次碰撞?
這題我的計算是:
(0+1+2+....+n-1)/n
但是答案卻是:
(0+1+2+....+n-1)/m
這是我搞錯還是答案錯了阿??
不是要除以資料數才對嗎?
麻煩知道的大大為我解答一下，感謝><
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.199.76.237
1F：推 leohi:問題2 我覺得塞入第一個的碰撞機率 是0/m 之後依序1/m 2/m 03/22 17:36
2F：→ leohi:所以應該是/m 不知道這個想法對不對~煩請版友指證 謝謝~ 03/22 17:37
3F：推 carterdunk:題目出得不好 題意不清 兩題都是... 03/22 17:44
4F：→ carterdunk:第二題 平均碰撞次數 第二個node插入的時候 03/22 17:44
5F：→ carterdunk:第一次碰撞機率為1/m*1 第二次? (1/m)^2*2? 03/22 17:45
6F：→ carterdunk:只算第一次碰撞的機率? 第二次怎麼算 演算法沒寫清楚 03/22 17:46
7F：推 leohi:我好像想錯了QAQ 請跳過我的想法orz 03/22 17:46
8F：→ kyc1023:第二題 應該跟L大講的一樣 就想成每一次插入時 m個位置都 03/22 17:54
9F：→ kyc1023:試一次 算碰撞次數在平均m 再全部加起來 03/22 17:56
10F：→ kyc1023:第一題不用考慮長度i嗎 不是算平均長度嗎 03/22 17:58
考慮長度i是什麼意思??它sigma是從i=1累加到i=n
11F：推 Mewra:因為每個slot都有機會填入資料跟碰撞 所以要用m 03/22 18:04
12F：推 asdd:平均長度怎沒考慮？ 03/22 18:23
13F：推 Mewra:我第一題答案是sigma pi(ci+1) 03/22 18:52
14F：推 Mewra:喔 我弄錯了 不過對一個點 查詢長度不是要較比較次數少1嗎? 03/22 18:56
15F：→ malowda:第一次碰撞表中只有1個有放資料所以是1/M 第二次碰撞表裡 03/23 10:33
→ malowda:有2個資料機率是2/M沒錯阿那來的(1/M)^2*
第二題了解了，但第一題還是沒有結論出來orz....有誰知道嗎???
※ 編輯: mingrong2 來自: 114.34.31.118 (03/23 19:16)
※ 編輯: mingrong2 來自: 114.34.31.118 (03/23 19:17)
16F：→ kyc1023:第一題題目 有點看不懂 是要算平均次數? 03/26 16:18