[理工] 106 台大電機丙資結 joywilliamjo PTT批踢踢實業坊

[理工] 106 台大電機丙資結

作者: joywilliamjo (joywilliamjoy) 2020-12-07 18:58:30

第9題
https://i.imgur.com/1ArbQc2.jpg
如果是min heap的話找min在O(1)但找max不是O(logn)嗎？
然後是第12題
搜過版上的答案似乎有點多元...
https://i.imgur.com/Vy2CuCr.jpg
https://i.imgur.com/3PKwaf8.jpg
想問一下C錯的地方以及這題的答案
C錯是因為應該是（k+1)嗎？

作者: mathtsai (mathtsai) 2020-12-07 19:41:00

找max要遍歷整個heap才能找到

作者: hero97212 (mojo) 2020-12-07 23:21:00

12答案應該是D EB 用 aggregate method 結果會是O(N)C的話舉個反例就好

作者: aa871220 (TMVP_Yueko) 2020-12-08 10:29:00

Heap 一定是complete tree而最大值一定在最底層一定要traverse過整個leaf node其最多會有n/2個node 故為O(N)

繼續閱讀

[理工] 離散成大108數學try66889 [理工] 108 交大資演 reductionaa871220 [理工] 104 台大電機丙 DS 資結 11題joywilliamjo 斜對稱矩陣cardsfan [商管] 數學模型求最佳解TravelingBao [理工] 內部路徑長style78432 [理工] 演算法 106 清大計科try66889 Re: [理工] [計科]-清大108-資工對答案joywilliamjo [理工] 107交大計系 assembly languagezyxl3102 [心得] 國家聖誕月settima

[理工] 106 台大電機丙 資結

[理工] 106 台大電機丙資結