[理工] [演算法] Kurskal's Algo

[beargg0305 (bear)]

http://i.imgur.com/TaRmqSW.jpg
請問一下第12題
假設使用adj list + min heap + disjoint set
複雜度會是O(ElogE)
但是因為E<V^2
所以又可以寫成O(ElogV)
那像這種填充題應該寫哪種答案@@
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.14.224
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1481702697.A.0A7.html
※ 編輯: beargg0305 (223.137.14.224), 12/14/2016 16:06:10
→ ken52011219: 我是寫最原始答案 O((V+E)a(V))
→ ken52011219: 又因E=V-1  ,a(V)=O(lgV)=O(lgE) ,t =O (E+1+E)lg E)
→ ken52011219: =O(ElgE)
→ ken52011219: 寫完可以跟我一起對答案0.0/
推 FRAXIS: 為什麼 E = V - 1?
→ darren0831: 非常需要對答案啊
→ aa06697: E = V-1 ~ C(V取2） 大約是O(V^2) 所以logE =  O(logV)
→ ken52011219: 抱歉QQ 是 E≧V-1
→ ken52011219: 只不過再看了一下 它並沒有說 KURSLAL'S ALGO 是要
→ ken52011219: 用adj-link 還是 adj-matrix 所以應該是 O(E*α(V))