[理工] 资结 Heap garyhsu1209 PTT批踢踢实业坊

楼主: garyhsu1209 (良师) 2016-12-03 22:12:47

第一题
为什么会有E选项呢？
http://i.imgur.com/Kjv0Hpu.jpg
http://i.imgur.com/xiTB5cp.jpg
第二题
http://i.imgur.com/5KLTBfb.jpg
C选项应该是O(1)吧？

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-12-03 22:57:00

theta(1) 也是 O(logn) 阿另外第一题的E没什么问题不过老师上课没讲就是了

作者: ken52011219 (呱) 2016-12-03 23:06:00

哪间学校这么阴险

楼主: garyhsu1209 (良师) 2016-12-03 23:40:00

第一题要选E不就应该同时选F了

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-12-03 23:42:00

这两个不是相反的选项?

楼主: garyhsu1209 (良师) 2016-12-03 23:43:00

第一题，不是Max-min heap跟deap 都O(logn)吗

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-12-03 23:45:00

对阿

楼主: garyhsu1209 (良师) 2016-12-03 23:46:00

喔我懂了，感谢不过考试遇到第二题这种明知道是O(1),题目写O(logn)选了还是怕怕的，虽然定义上是对的qq

作者: FRAXIS (喔喔) 2016-12-04 22:37:00

但是题目问的是插入和删除 min/max 不是找min/max

作者: pepro (peproisgood) 2016-12-04 16:39:00

deap 找最大值只要到右子树的root 但min max level要比较一次才知道最大值

作者: a19930301 (-手起刀落o`) 2016-12-04 08:38:00

第一题，题目就有迹可循，xxx"时间内"xxx，时间复杂度我是想成可上包含下，就像O(1)也是polymonial time可解的

继续阅读