作者ken90242 (juicebombom)
看板Grad-ProbAsk
標題[理工] Kruskal&Prim改用matrix的時間複雜度
時間Sat Feb 13 01:38:56 2016
想請問各位
kruskal跟prime的資料結構若是改用adjacency matrix的話
他們各自的時間複雜度會跟使用list的時候有差嗎？
我有自己大概先想了一下 能幫我看一下哪邊有誤嗎
Kruskal
每個頂點都做make-set：Ｏ(V)
bottom up建heap：Ｏ(V^2) //邊總數E改為V^2
由小到大取出每個邊+調整：Ｏ(V^2*logV^2) = Ｏ(V^2*logV) //邊總數E改為V^2
total time：Ｏ(V^2*logV)
Prim
每個頂點的距離初始化：Ｏ(V)
建fibonacci heap：Ｏ(V)
由小到大取出每個頂點v：Ｏ(V*logV)
比較每個相鄰於v的頂點距離並調整(=比較每個邊)：Ｏ(V^2)
total time：Ｏ(V^2)
想請問大家這樣子想是正確的嗎？先謝謝大家了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.130.134
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455298741.A.D8D.html
→ yaxauw: 是Prim吧.. Prime是質數 02/13 09:14
→ yaxauw: 為啥bottom up建heap是v^2啊? 02/13 09:16
→ ken90242: 喔喔sor打太快沒注意 02/13 10:46
→ ken90242: 因為原本應該是O(E) 02/13 10:46
→ ken90242: 但是資料結構是陣列，要找到每個邊要花O(V^2) 02/13 10:46
→ ken90242: 不確定是不是這樣 02/13 10:46
※ 編輯: ken90242 (180.176.130.134), 02/13/2016 11:42:38
推 iam30719: 用matrix好像都是V^2 但太曖昧應該 02/13 11:54
→ iam30719: 比較不會特別出題吧 目前還沒看過出題 02/13 11:55