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

了解了！謝謝

繼續閱讀