[理工] [算法] 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))

继续阅读