1. PTT
  2. Grad-ProbAsk

[理工] 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 清大计科try66889Re: [理工] [计科]-清大108-资工 对答案joywilliamjo[理工] 107交大计系 assembly languagezyxl3102[心得] 国家圣诞月settima

Links booklink

Contact Us: admin [ a t ] ucptt.com