big O

看板Grad-ProbAsk作者 (pass)時間3年前 (2022/02/14 15:02), 編輯推噓5(5推 0噓 6→)
留言11則, 3人參與, 3年前最新討論串1/1
第五題為什麼要改成n^3? https://i.imgur.com/EqtOrMQ.jpg
https://i.imgur.com/S7KctlK.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.68.70 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1644822152.A.E6B.html
推
02/14 23:30, 3年前 , 1F
是不是做Floyd-Worshall O(n^3)
02/14 23:30, 1F
推
02/14 23:33, 3年前 , 2F
喔不對 是不是對每個點都做一次dijkstra 每一次的dijks
02/14 23:33, 2F
→
02/14 23:33, 3年前 , 3F
tra都紀錄最長距離 所以複雜度才是O(n^3)
02/14 23:33, 3F
推
02/15 09:57, 3年前 , 4F
難保沒有比 n^2 更快的演算法？
02/15 09:57, 4F
→
02/15 14:31, 3年前 , 5F
所以說是因為花費的時間比較長所以選擇最高時間複雜度？
02/15 14:31, 5F
推
02/15 14:42, 3年前 , 6F
這題是因為題目已經說資料結構是使用array來maintain
02/15 14:42, 6F
→
02/15 14:42, 3年前 , 7F
所以時間複雜度才是O(n^3)
02/15 14:42, 7F
→
02/15 16:45, 3年前 , 8F
為什麼是陣列就是O(n^3)？
02/15 16:45, 8F
推
02/16 10:22, 3年前 , 9F
因為用陣列來作為資料結構會使得dijkstra執行的時間為O
02/16 10:22, 9F
→
02/16 10:22, 3年前 , 10F
(n^2) 又執行dijkstran次所以為n*O(n^2) = O(n^3)
02/16 10:22, 10F
→
02/16 11:22, 3年前 , 11F
了解了！謝謝
02/16 11:22, 11F
‣ 更多 starQJ 的文章
文章代碼(AID): #1Y2Vw8vh (Grad-ProbAsk)