作者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/cn.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