在循环中应用Kruskal算法的最坏情况下时间复杂度是多少?

Question

这是我的伪代码片段，用于查找给定图G的每个强连接组件(SCC)的MST:

Number of SCC, K <- apply Kosaraju's algorithm on Graph G O(V + E)
Loop through K components:
each K components <- apply Kruskal's algorithm

据我了解，Kruskal算法的运行时间为O(E log V)。

然而，我不确定循环的最坏情况的时间复杂度。我认为最坏的情况会发生在K = 1的时候。因此，大O时间复杂度将简单地等于O(E log V)。

我不知道我的想法是否正确，或者如果他们是正确的，它的理由是什么。

Answer 1

是的，直觉上你节省了比较边的成本具有另一个边的组件。形式上，f(V, E)∑E log V是一个凸功能,所以f (V<子>1,E<子>1 ) + f (2 V<子>,2 E<子>)≤f (V<子>1+ V<子>2子>+ 1E₂)，这意味着处理倍数的成本组件分开只不过是一起处理它们。的当然，正如你所看到的，可能只有一种成分，在这种情况下没有储蓄可存。