big O starQJ PTT批踢踢实业坊

楼主: starQJ (pass) 2022-02-14 15:02:30

第五题为什么要改成n^3?
https://i.imgur.com/EqtOrMQ.jpg
https://i.imgur.com/S7KctlK.jpg

作者: chiuchang (precious simple) 2022-02-14 23:30:00

是不是做Floyd-Worshall O(n^3)喔不对是不是对每个点都做一次dijkstra 每一次的dijkstra都纪录最长距离所以复杂度才是O(n^3)

作者: alan23273850 2022-02-15 09:57:00

难保没有比 n^2 更快的算法？

楼主: starQJ (pass) 2022-02-15 14:31:00

所以说是因为花费的时间比较长所以选择最高时间复杂度？

作者: chiuchang (precious simple) 2022-02-15 14:42:00

这题是因为题目已经说资料结构是使用array来maintain所以时间复杂度才是O(n^3)

楼主: starQJ (pass) 2022-02-15 16:45:00

为什么是阵列就是O(n^3)？

作者: chiuchang (precious simple) 2022-02-16 10:22:00

因为用阵列来作为资料结构会使得dijkstra执行的时间为O(n^2) 又执行dijkstran次所以为n*O(n^2) = O(n^3)

楼主: starQJ (pass) 2022-02-16 11:22:00

了解了！谢谢

继续阅读