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)(我不知道为什么我记得那个,除此之外我认为一个教授放了那个在一次考试...)

Elog(V) 在这里可以简化为 Elog(V^2) [ e = v^2 在最坏的情况下 // 完整图 ] 所以 Elog(V^2) <= 2Elog(V) 即 Elog(V)。通常在图中，我们同时使用 e 和 v 因为我们不能用 v 替换 e 原因，这会改变时间复杂度，但这里由于日志的存在我们可以。PS：我们不能将 O(E*E) 写为 O(V*E) 只是为了拥有这两个变量。 (2认同)

Answer 2

由于|V| > |E|+1，我们更喜欢使用 V 项而不是 E 项的紧上界。

    |E| <= |V|²   
.   log |E| < log |V|²   
.   log |E| < 2 log |V| 
.   running time of MST-KRUSKAL is: O(E log V)