该Karger算法实现的时间复杂度为何为~O(E)？性能疑问解析

你提到的Karger算法实现代码 #

//Find, and Union are the use of Disjoint set union on the nodes.
MinCut(edges, V, E):
    vertices=V
    While(vertices > 2):
        i=Random integer in the range [0,E-1]
        set_1=find(edges[i].u)
        set_2=find(edges[i].v)
        if(set_1 != set_2):
            vertices = vertices-1
            Union(u, v)
    ans=0
    For(i in the range 0 to E-1):
        set_1=find(edges[i].u)
        set_2=find(edges[i].v)
        if(set_1 != set_2):
            ans = ans + 1
    Return ans

1. 未移除边是否会导致大幅性能下降？ #

确实，这个实现每次随机选边时可能抽到已属于同一连通分量的边，这类操作属于无效操作，不会推进算法进程，但实际开销并没有想象中那么大：

• 有效操作的总次数是固定的：必须执行V-2次合并操作（从V个顶点合并到2个），这是所有Karger实现的核心步骤。
• 带路径压缩和按秩合并的并查集（DSU），其find和Union操作均摊时间复杂度为O(α(V))（α是阿克曼函数的反函数，增长极慢，几乎可视为常数），所以即使存在无效操作，单次无效操作的开销也极低。
• 如果要优化，可以维护动态边列表，合并后移除无效边，但这会引入额外的维护成本（比如删除、随机访问的开销）。对于大多数场景，原始实现的简单性带来的收益超过了无效操作的开销，尤其是当图的边数E不是极端庞大时。

2. 为什么时间复杂度是~O(E)？ #

要理解这个结论，需分析while循环的总迭代次数（含有效和无效操作）：

• 整个算法的期望总迭代次数是O(E)，核心推导如下：
  1. 当图中有k个连通分量时，随机选中有效边（连接不同分量的边）的概率为p_k，根据几何分布，该阶段需要的期望尝试次数为1/p_k。
  2. 对所有阶段（从k=V到k=3）的期望尝试次数求和，结合连通图的性质（k个分量时至少有k-1条有效边），可以证明总期望迭代次数为O(E)——本质上每条边被选中的期望次数是常数级，总共有E条边，因此总迭代次数期望为O(E)。
  3. 再结合并查集的均摊常数时间操作，while循环的期望时间为O(E α(V)) ≈ O(E)。
• 最后的for循环遍历E条边，每次执行O(α(V))的find操作，时间复杂度也是O(E)。
• 综合来看，整个算法的期望时间复杂度约为O(E)。

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