作者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/m.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