作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 資料結構 Dijkstra algo時間複雜度
時間Wed Oct 17 20:26:11 2018
https://i.imgur.com/RCJbpwf.jpg
洪逸筆記裡的這部分有點不能理解
法二用fib.heap建的時間複雜度
為什麼是寫成O(vlogv+E)而不是寫O(E)就好
我的想法是
E的最大邊數是v(v-1)/2 也就是O(v^2)
如此一來O(v^2)比O(vlogv)來得大
所以時間複雜度是O(v^2)或是O(E)
不知道是哪裡想錯了
麻煩各位一下
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.233.117
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539779173.A.C85.html
推 wilson50101: 不一定每次都到最大邊數吧 10/17 20:36
→ wilson50101: 如果邊少這樣估會太鬆？ 10/17 20:36
推 BroccolYee: V-1 <= E <= V*(V-1)/2 10/17 20:48
→ BroccolYee: 只寫O(E)會不夠嚴謹 10/17 20:48
→ AAQ8: 好奇問一下，法一的時間複雜度可以寫O((E+V)logv)嗎，如果要 10/17 21:59
→ AAQ8: 夠緊的話 10/17 21:59
推 wilson50101: 可以吧 法一本來就O(ElogV+VlogV) 10/18 00:03