[理工] 资演清大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

喔对搞错了

继续阅读