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

看板Grad-ProbAsk作者 (monster710623)時間6年前 (2020/01/17 12:28), 6年前編輯推噓1(106)
留言7則, 3人參與, 6年前最新討論串1/1
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

01/17 13:35, 6年前 , 1F
log2 7=log 4 49 所以答案應該是48?
01/17 13:35, 1F
有看過這答案 不知怎麼來的 ※ 編輯: ching4562 (1.167.53.96 臺灣), 01/17/2020 13:50:08

01/17 14:08, 6年前 , 2F
就master theory 而已
01/17 14:08, 2F
喔喔了解 那第8呢 ※ 編輯: ching4562 (1.167.53.96 臺灣), 01/17/2020 14:16:17

01/17 14:44, 6年前 , 3F
8(a) 是O(n)吧 insert跟search在沒overflow都是O(1)
01/17 14:44, 3F

01/17 14:46, 6年前 , 4F
8(b)有可能會skew 這樣search變O(n) 我會寫O(n^2)
01/17 14:46, 4F

01/17 14:47, 6年前 , 5F
8(c)應該沒錯 然後以上不保證正確XD
01/17 14:47, 5F

01/17 15:28, 6年前 , 6F
應該是沒collision 才O1 不是overflow
01/17 15:28, 6F

01/17 15:57, 6年前 , 7F
喔對搞錯了
01/17 15:57, 7F
文章代碼(AID): #1U8JVLjk (Grad-ProbAsk)