[理工] 資料結構 Dijkstra algo時間複雜度 AAQ8 PTT批踢踢實業坊

[理工] 資料結構 Dijkstra algo時間複雜度

作者: AAQ8 (不要就是要) 2018-10-17 20:26:11

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)
不知道是哪裡想錯了
麻煩各位一下
感謝

作者: wilson50101 (我覺得我還不錯啊) 2018-10-17 20:36:00

不一定每次都到最大邊數吧如果邊少這樣估會太鬆？

作者: BroccolYee (花椰菜) 2018-10-17 20:48:00

V-1 <= E <= V*(V-1)/2只寫O(E)會不夠嚴謹

作者: AAQ8 (不要就是要) 2018-10-17 21:59:00

好奇問一下，法一的時間複雜度可以寫O((E+V)logv)嗎，如果要夠緊的話

作者: wilson50101 (我覺得我還不錯啊) 2018-10-18 00:03:00

可以吧法一本來就O(ElogV+VlogV)

繼續閱讀

[理工] 演算法 convex hull 極點wilson50101 [理工] 線代古典伴隨矩陣AAQ8 [理工] 線代第二章AAQ8 [理工] 計組下冊 P.307 Utilizationjojoboy0115 [理工] 計組下p.298 Disk average timeghost1025 [理工] 離散2-33 （c)!Aa841018 [商管] 誰能存取台灣經濟新報光碟資料? 優厚報酬yuwenche [理工] 演算法DAG求最短路徑wilson50101 [理工] 演算法遞迴hl654ck6 [理工] 演算法MST第35題wilson50101