[理工] [演算法] Kurskal's Algo beargg0305 PTT批踢踢實業坊

作者: beargg0305 (bear) 2016-12-14 16:04:54

http://i.imgur.com/TaRmqSW.jpg
請問一下第12題
假設使用adj list + min heap + disjoint set
複雜度會是O(ElogE)
但是因為E<V^2
所以又可以寫成O(ElogV)
那像這種填充題應該寫哪種答案@@

作者: ken52011219 (呱) 2016-12-14 16:08:00

我是寫最原始答案 O((V+E)a(V))又因E=V-1 ,a(V)=O(lgV)=O(lgE) ,t =O (E+1+E)lg E)=O(ElgE)寫完可以跟我一起對答案0.0/

作者: FRAXIS (喔喔) 2016-12-14 19:19:00

為什麼 E = V - 1?

作者: darren0831 (達) 2016-12-14 19:21:00

非常需要對答案啊

作者: aa06697 (todo se andarà) 2016-12-14 19:29:00

E = V-1 ~ C(V取2）大約是O(V^2) 所以logE = O(logV)

作者: ken52011219 (呱) 2016-12-14 20:27:00

抱歉QQ 是 E≧V-1只不過再看了一下它並沒有說 KURSLAL'S ALGO 是要用adj-link 還是 adj-matrix 所以應該是 O(E*α(V))

繼續閱讀