Kruskal 算法复杂度分析问题

Question

Hi bobo 老师，

本节最后说 “Kruskal 算法的总体复杂度是 O(ElogE)，其中对边进行排序的复杂度是 O(ElogE)，从堆中取出边判断是否成环的复杂度是 O(ElogV)”。

不太明白“从堆中取出边判断是否成环”这个过程为什么是 O(ElogV) 的？这部分代码如下：

// 创建一个并查集, 来查看已经访问的节点的联通情况
UnionFind uf = new UnionFind(graph.V());
while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){

    // 从最小堆中依次从小到大取出所有的边
    Edge<Weight> e = pq.extractMin();
    // 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
    if( uf.isConnected( e.v() , e.w() ) )
        continue;

    // 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
    mst.add( e );
    uf.unionElements( e.v() , e.w() );
}

我的理解是：

• extractMin 本身的复杂度应该是 O(logE)，因为 while 循环执行了 graph.V() - 1 次，因此 graph.V() - 1 次 extractMin 就是 O(VlogE) 的复杂度。
• 带有路径压缩优化的并查集的复杂度接近 O(1)，那么 graph.V() - 1 次 isConnected 和 unionElements 就是 O(V) 的复杂度。
• 因此这部分代码总体复杂度应该是 O(VlogE) 。

不知道哪里分析的有问题？

Answer 1

liuyubobobo 2019-03-13 13:17:02

因为这个while循环最多会循环E次，即把pq从满，到取空。

这里要注意，我们初始化pq，是将所有的边都放在了pq中，所以pq中的元素个数是E，而不是V：）

你的其他分析都是对的：）

继续加油！：）

• 提问者 Poplar_hills #1

  多谢老师！

• tobeabee #2

  老师，这句”从堆中取出边判断是否成环的复杂度是 O(ElogV)“我还是不理解。。。如果说构造函数中的while循环最多会循环E次，那O(ElogV)里面剩下的logV是怎么算出来的呢？

• liuyubobobo 回复 tobeabee #3

  你是正确的。在这个课程的实现中，这个 while 循环也是 O(ElogE) 的。其实我不很确定我在课程哪里说过这一部分的复杂度是 O(ElogV)，如果说过应该是口误。上面的回答主要是在说，这个循环的运行次数最大是 E，而非 V。
  
  实际上，这一部分的实现完全可以是 O(E) 的（如果将 uf 的操作近似看做是 O(1)）。因为我们可以把所有的边放在一个数组中（而非堆中），对这个数组根据权值做原地排序，这是 O(ElogE) 的。之后只要从头到尾遍历这个数组，对每个边处理（放到 mst 中或者扔掉）就好。（此时我们不需要从堆中取边，就在这里避免了 log 的操作。）
  
  继续加油！：）

点开查看后面1条评论