作者alanqq0624 (我沒有朋友嗚嗚嗚嗚嗚)
看板Grad-ProbAsk
標題[理工] 台大資工105資演 3.a.ii
時間Mon Dec 23 21:26:35 2019
http://i.imgur.com/co4OIps.jpg
關於這一題
網路上的答案是寫O(n/(m)^2)
但是我算出來的是O(n/m)
我對題意的理解是
假如collision的話就會開新的table H'去存
所以平均上會有n/m個table
所以在每個table找到的機率是1/(n/m)
再假設在第k個table找到element的時間是k
算式如下
http://i.imgur.com/qOQWubO.jpg
-----
Sent from JPTT on my OnePlus GM1900.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.233.229 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1577107597.A.6B6.html
2F：→ qwer87511: 個人淺見...我的想法算出來是o(long)，不知道這樣有錯 12/24 00:05
3F：→ qwer87511: 的話錯在哪 12/24 00:05
4F：→ qwer87511: 個人淺見...我的想法算出來是o(long)，不知道這樣有錯 12/24 00:06
5F：→ qwer87511: 的話錯在哪 12/24 00:06
6F：推 tl32brian: 我認為 誠如樓主所說 總共會有n/m個table 而每個H中的s 12/24 10:00
7F：→ tl32brian: lot 平均會有(n/m)/m個table 所以在找的時候只要考慮 12/24 10:00
8F：→ tl32brian: 該slot跟以後的table 即(n/m)/m個table即可 12/24 10:00
10F：→ b10007034: 這才是對的吧，裡面有小證明 12/24 10:56
11F：→ qwer87511: 但樓主問的是第一題的第二小題QQ 12/24 13:23
12F：→ alanqq0624: 為什麼每個H的slot中還會有table 如果碰撞時不是應該 12/25 13:03
13F：→ alanqq0624: 會去找下一個H'嗎？ 12/25 13:03
14F：→ alanqq0624: 至於一樓的問題大概是出在結構上 12/25 13:10
15F：→ alanqq0624: 因為我理解的結構是平行生長而不是樹狀生長的 12/25 13:10
16F：→ alanqq0624: 例如假如有一個element塞在第5個slot 12/25 13:10
17F：→ alanqq0624: 假如H的slot5 collision 12/25 13:10
18F：→ alanqq0624: 就會直接去塞在H'的slot5 12/25 13:10
19F：→ alanqq0624: 假如H'還是collision 12/25 13:10
20F：→ alanqq0624: 會塞到H''的slot5 12/25 13:10
21F：→ alanqq0624: 而且因為element是通過hash function決定要塞在那個sl 12/25 13:10
22F：→ alanqq0624: ot 12/25 13:11
23F：→ alanqq0624: 所以在每一個hash table search的時間會是O(1) (我的 12/25 13:11
24F：→ alanqq0624: 算法是直接假設為1) 12/25 13:11