[理工] 資料結構 Dijkstra algo時間複雜度
洪逸筆記裡的這部分有點不能理解
法二用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
推
10/17 20:36,
7年前
, 1F
10/17 20:36, 1F
→
10/17 20:36,
7年前
, 2F
10/17 20:36, 2F
推
10/17 20:48,
7年前
, 3F
10/17 20:48, 3F
→
10/17 20:48,
7年前
, 4F
10/17 20:48, 4F
→
10/17 21:59,
7年前
, 5F
10/17 21:59, 5F
→
10/17 21:59,
7年前
, 6F
10/17 21:59, 6F
推
10/18 00:03,
7年前
, 7F
10/18 00:03, 7F