作者ching4562 (monster710623)
看板Grad-ProbAsk
标题[理工] 资演 清大108 第8、9题
时间Fri Jan 17 12:28:03 2020
https://i.imgur.com/BM6o7ZU.jpg
https://i.imgur.com/Ad2rCg8.jpg
8.
答案不确定
Hash的insert是O(1)吗？
9.
不知道怎麽算 我乱算的
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.167.53.96 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579235285.A.B6E.html
1F：→ cossetannie: log2 7=log 4 49 所以答案应该是48?01/17 13:35
有看过这答案 不知怎麽来的
※ 编辑: ching4562 (1.167.53.96 台湾), 01/17/2020 13:50:08
2F：→ zuchang: 就master theory 而已 01/17 14:08
喔喔了解 那第8呢
※ 编辑: ching4562 (1.167.53.96 台湾), 01/17/2020 14:16:17
3F：推 MASAGA: 8(a) 是O(n)吧 insert跟search在没overflow都是O(1) 01/17 14:44
4F：→ MASAGA: 8(b)有可能会skew 这样search变O(n) 我会写O(n^2) 01/17 14:46
5F：→ MASAGA: 8(c)应该没错 然後以上不保证正确XD 01/17 14:47
6F：→ zuchang: 应该是没collision 才O1 不是overflow 01/17 15:28
7F：→ MASAGA: 喔对搞错了 01/17 15:57