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

看板Grad-ProbAsk作者 (我沒有朋友嗚嗚嗚嗚嗚)時間4年前 (2019/12/23 21:26), 編輯推噓3(3推 0噓 21→)
留言24則, 4人參與, 4年前最新討論串1/1
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
推
12/24 00:04, 4年前 , 1F
12/24 00:04, 1F
→
12/24 00:05, 4年前 , 2F
個人淺見...我的想法算出來是o(long)，不知道這樣有錯
12/24 00:05, 2F
→
12/24 00:05, 4年前 , 3F
的話錯在哪
12/24 00:05, 3F
→
12/24 00:06, 4年前 , 4F
個人淺見...我的想法算出來是o(long)，不知道這樣有錯
12/24 00:06, 4F
→
12/24 00:06, 4年前 , 5F
的話錯在哪
12/24 00:06, 5F
推
12/24 10:00, 4年前 , 6F
我認為 誠如樓主所說 總共會有n/m個table 而每個H中的s
12/24 10:00, 6F
→
12/24 10:00, 4年前 , 7F
lot 平均會有(n/m)/m個table 所以在找的時候只要考慮
12/24 10:00, 7F
→
12/24 10:00, 4年前 , 8F
該slot跟以後的table 即(n/m)/m個table即可
12/24 10:00, 8F
推
12/24 10:56, 4年前 , 9F
12/24 10:56, 9F
→
12/24 10:56, 4年前 , 10F
這才是對的吧，裡面有小證明
12/24 10:56, 10F
→
12/24 13:23, 4年前 , 11F
但樓主問的是第一題的第二小題QQ
12/24 13:23, 11F
→
12/25 13:03, 4年前 , 12F
為什麼每個H的slot中還會有table 如果碰撞時不是應該
12/25 13:03, 12F
→
12/25 13:03, 4年前 , 13F
會去找下一個H'嗎？
12/25 13:03, 13F
→
12/25 13:10, 4年前 , 14F
至於一樓的問題大概是出在結構上
12/25 13:10, 14F
→
12/25 13:10, 4年前 , 15F
因為我理解的結構是平行生長而不是樹狀生長的
12/25 13:10, 15F
→
12/25 13:10, 4年前 , 16F
例如假如有一個element塞在第5個slot
12/25 13:10, 16F
→
12/25 13:10, 4年前 , 17F
假如H的slot5 collision
12/25 13:10, 17F
→
12/25 13:10, 4年前 , 18F
就會直接去塞在H'的slot5
12/25 13:10, 18F
→
12/25 13:10, 4年前 , 19F
假如H'還是collision
12/25 13:10, 19F
→
12/25 13:10, 4年前 , 20F
會塞到H''的slot5
12/25 13:10, 20F
→
12/25 13:10, 4年前 , 21F
而且因為element是通過hash function決定要塞在那個sl
12/25 13:10, 21F
→
12/25 13:11, 4年前 , 22F
ot
12/25 13:11, 22F
→
12/25 13:11, 4年前 , 23F
所以在每一個hash table search的時間會是O(1) (我的
12/25 13:11, 23F
→
12/25 13:11, 4年前 , 24F
算法是直接假設為1)
12/25 13:11, 24F
‣ 更多 alanqq0624 的文章
文章代碼(AID): #1U0C2DQs (Grad-ProbAsk)