[理工] 資演清大108 第8、9題 ching4562 PTT批踢踢實業坊

作者: ching4562 (monster710623) 2020-01-17 12:28:03

https://i.imgur.com/BM6o7ZU.jpg
https://i.imgur.com/Ad2rCg8.jpg
8.
答案不確定
Hash的insert是O(1)嗎？
9.
不知道怎麼算我亂算的

作者: cossetannie (paa) 2020-01-17 13:35:00

log2 7=log 4 49 所以答案應該是48?

作者: zuchang (chang) 2020-01-17 14:08:00

就master theory 而已

作者: MASAGA (和泉千晶我老婆) 2020-01-17 14:44:00

8(a) 是O(n)吧 insert跟search在沒overflow都是O(1)8(b)有可能會skew 這樣search變O(n) 我會寫O(n^2)8(c)應該沒錯然後以上不保證正確XD

作者: zuchang (chang) 2020-01-17 15:28:00

應該是沒collision 才O1 不是overflow

作者: MASAGA (和泉千晶我老婆) 2020-01-17 15:57:00

喔對搞錯了

繼續閱讀