作者starQJ (pass)
看板Grad-ProbAsk
标题big O
时间Mon Feb 14 15:02:30 2022
第五题为什麽要改成n^3?
https://i.imgur.com/EqtOrMQ.jpg
https://i.imgur.com/S7KctlK.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.138.68.70 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1644822152.A.E6B.html
1F：推 chiuchang: 是不是做Floyd-Worshall O(n^3) 02/14 23:30
2F：推 chiuchang: 喔不对 是不是对每个点都做一次dijkstra 每一次的dijks 02/14 23:33
3F：→ chiuchang: tra都纪录最长距离 所以复杂度才是O(n^3) 02/14 23:33
4F：推 alan23273850: 难保没有比 n^2 更快的演算法？ 02/15 09:57
5F：→ starQJ: 所以说是因为花费的时间比较长所以选择最高时间复杂度？ 02/15 14:31
6F：推 chiuchang: 这题是因为题目已经说资料结构是使用array来maintain 02/15 14:42
7F：→ chiuchang: 所以时间复杂度才是O(n^3) 02/15 14:42
8F：→ starQJ: 为什麽是阵列就是O(n^3)？ 02/15 16:45
9F：推 chiuchang: 因为用阵列来作为资料结构会使得dijkstra执行的时间为O 02/16 10:22
10F：→ chiuchang: (n^2) 又执行dijkstran次所以为n*O(n^2) = O(n^3) 02/16 10:22
11F：→ starQJ: 了解了！谢谢 02/16 11:22