[理工] 台大資工105資演 3.a.ii

[alanqq0624 (我沒有朋友嗚嗚嗚嗚嗚)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1577107597.A.6B6.html
推 qwer87511: https://i.imgur.com/4zH41be.jpg
→ qwer87511: 個人淺見...我的想法算出來是o(long)，不知道這樣有錯
→ qwer87511: 的話錯在哪
→ qwer87511: 個人淺見...我的想法算出來是o(long)，不知道這樣有錯
→ qwer87511: 的話錯在哪
推 tl32brian: 我認為 誠如樓主所說 總共會有n/m個table 而每個H中的s
→ tl32brian: lot 平均會有(n/m)/m個table 所以在找的時候只要考慮
→ tl32brian: 該slot跟以後的table 即(n/m)/m個table即可
推 b10007034: #1SNlwdIZ (Grad-ProbAsk)
→ b10007034: 這才是對的吧，裡面有小證明
→ qwer87511: 但樓主問的是第一題的第二小題QQ
→ alanqq0624: 為什麼每個H的slot中還會有table 如果碰撞時不是應該
→ alanqq0624: 會去找下一個H'嗎？
→ alanqq0624: 至於一樓的問題大概是出在結構上
→ alanqq0624: 因為我理解的結構是平行生長而不是樹狀生長的
→ alanqq0624: 例如假如有一個element塞在第5個slot
→ alanqq0624: 假如H的slot5 collision
→ alanqq0624: 就會直接去塞在H'的slot5
→ alanqq0624: 假如H'還是collision
→ alanqq0624: 會塞到H''的slot5
→ alanqq0624: 而且因為element是通過hash function決定要塞在那個sl
→ alanqq0624: ot
→ alanqq0624: 所以在每一個hash table search的時間會是O(1) (我的
→ alanqq0624: 算法是直接假設為1)