[理工] 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

继续阅读