基于Union-Find结构的Boruvka算法时间复杂度疑问

实现代码 #

method boruvkas(GraphEdgeList, numOfNodes):
    compCount = numOfNodes
    cheapest = Array(numOfNodes), initialized with (0, 0, ∞)
    MSTEdgeList = []
    while compCount > 1:
        for (u, v, w) in GraphEdgeList:
            comp1 = find(u), comp2 = find(v)
            if comp1 != comp2:
                if w < cheapest[comp1]:
                    cheapest[comp1] = (u, v, w)
                if w < cheapest[comp2]:
                    cheapest[comp2] = (u, v, w)
        for i from 1 to numOfNodes:
            e = cheapest[i]
            if e.weight != ∞:
                comp1 = find(e.first), comp2 = find(e.second)
                if comp1 != comp2:
                    unite(comp1, comp2)
                    MSTEdgeList.add(e)
                    compCount--
        reset(cheapest, (0, 0, ∞))
    return MSTEdgeList

时间复杂度拆解 #

我们一步步拆解各部分的耗时，就能明白整体复杂度为何是O(E logV)：

• 外层循环次数：确实是O(logV)。因为每次循环至少将连通分量数减半（每次合并操作把两个分量合成一个），从初始的V个分量降到1个，需要log₂V次循环，即O(logV)次。

• 第一个内层循环（遍历所有边）：
  每次外层循环都会遍历全部E条边，每条边执行2次find操作。如果Union-Find实现了路径压缩和按秩合并，find的时间复杂度是近似常数的阿克曼反函数α(V)（远小于logV）；即使简化分析按O(logV)计算，每次外层循环这部分的时间是O(E logV)。叠加外层的O(logV)次循环，这部分总耗时为O(E α(V) logV)，而α(V)在实际场景中可视为常数，因此简化为O(E logV)。

• 第二个内层循环（处理连通分量）：
  这个循环看似遍历V个节点，但只有当前连通分量对应的cheapest条目是有效的（其他都是∞），实际处理的是当前的连通分量数C。每次处理执行2次find和1次union，单次耗时O(α(V))。
  把所有外层循环的C加起来：第一次是V，第二次最多V/2，第三次最多V/4……直到1，总和是V + V/2 + V/4 + ... +1 = 2V-1 = O(V)。这部分总耗时为O(V α(V))，对于连通图来说E≥V-1，O(V α(V))远小于O(E logV)，可以忽略不计。

• 整体复杂度：
  核心耗时来自第一个内层循环的总时间，最终整体时间复杂度简化为O(E logV)。

内容的提问来源于stack exchange，提问作者raf_135711