[理工] 資結 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可解的

繼續閱讀