algorithm - Kruskal 算法的时间复杂度？

Question

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

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 算法:

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

Answer 1

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