Kruskal 算法的时间复杂度? [英] Time Complexity of the Kruskal Algorithm?

问题描述

我正在计算这样的 kruskal 算法的时间复杂度(请参阅附图中的算法)

I am calculating time complexity for kruskal algorithm like this (Please see the algorithm in the Image Attached)

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

CLRS 算法:

这是正确的还是我做错了什么，请告诉.

Is it correct or I'm doing something wrong please tell.

推荐答案

Kruskal is O(E log E);你的推导是对的.你也可以说 O(E log V) 因为 E <= V * V，所以 log(E) <= 2 log(V)(我不知道为什么我记得那个，除此之外我认为一个教授一次把它放在考试中......)

Kruskal is O(E log E); your derivation is right. You could also say O(E log V) because E <= V * V, so log(E) <= 2 log(V) (I don't know why I remember that, other than that I think a prof put that on an exam at one point...)

这篇关于Kruskal 算法的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！