[理工] 106政大資演 dijkstra pipiLUANAIAI PTT批踢踢實業坊

作者: pipiLUANAIAI (狗貓咪) 2021-12-26 16:45:12

https://i.imgur.com/0sMLRyg.jpg
想請問這題的時間複雜度是自動被假設使用array嗎

作者: VF84 (Jolly Roger) 2021-12-26 17:53:00

不管是 array 還是 fib heap，時間複雜度都是 O(V^2)所以其實可以不用糾結在這裡說明一下，O(VlgV + E) 也是 O(V^2) 的子集合，怕你搞混

作者: mathtsai (mathtsai) 2021-12-26 18:54:00

時間複雜度取決於你使用的資料結構

作者: joywilliamjo (joywilliamjoy) 2021-12-26 21:34:00

我比較好奇遇到這種題目，如果沒有說單選的話，這種上限開到很大的選項要不要選，比如說worst case是O(n^2) ,但選項說選對的，然後選項中有個O(n^3)這樣台大109第一題我到現在還是不知道DE那兩個選項要不要選= =

作者: VF84 (Jolly Roger) 2021-12-26 21:45:00

我覺得要

作者: pipiLUANAIAI (狗貓咪) 2021-12-26 22:17:00

謝謝各位

作者: alan23273850 2021-12-28 19:14:00

回 joy，看是單選還是多選

作者: joywilliamjo (joywilliamjoy) 2021-12-29 00:33:00

樓上，台大109就是啥都沒說啊...

作者: VF84 (Jolly Roger) 2021-12-29 07:22:00

他有說 Please select "all" correct answers

繼續閱讀