楼主:
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)
楼主:
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了解了！谢谢