[理工] 資演 清大108 第8、9題

[ching4562 (monster710623)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1579235285.A.B6E.html
→ cossetannie: log2 7=log 4 49 所以答案應該是48?
有看過這答案 不知怎麼來的
※ 編輯: ching4562 (1.167.53.96 臺灣), 01/17/2020 13:50:08
→ zuchang: 就master theory 而已
喔喔了解 那第8呢
※ 編輯: ching4562 (1.167.53.96 臺灣), 01/17/2020 14:16:17
推 MASAGA: 8(a) 是O(n)吧 insert跟search在沒overflow都是O(1)
→ MASAGA: 8(b)有可能會skew  這樣search變O(n) 我會寫O(n^2)
→ MASAGA: 8(c)應該沒錯  然後以上不保證正確XD
→ zuchang: 應該是沒collision 才O1 不是overflow
→ MASAGA: 喔對搞錯了