lazy prim的时间复杂度疑问

Question

在算法与数据结构课程中，您在讲解lazy prim算法（存边，未优化）时间复杂度时，外层循环 while(!pq.isEmpty()) ，循环次数为边数E。内层包括两个部分：

1. 从堆中取出最小的边 pq.extractMin(), 时间复杂度为logE

2. visit 函数，把所有的visit对邻边的遍历合在一起，也是E次（邻接矩阵V^2次），每次执行pq.insert()函数，复杂度为logE。

综合起来是 O(ElogE + ElogE ), 也就是 O(ElogE)。

在您的另外一个回复中，告诉我lazy prim的复杂度（E+V）logE是如何得出的呢？我是在哪里理解的不到位？

Answer 1

liuyubobobo 2019-02-16 17:54:06

简单的说，在图论算法中，只要图要遍历一遍，复杂度都应该是O(V+E)的。这是因为我们不可能不顾点，只顾边。边的遍历一定伴随点的遍历。遍历边的过程一定是沿着边上的节点进行的。

具体到代码里，你可以理解成下面注释所示：

// 访问节点v    
void visit(int v){    

    assert( !marked[v] );    
  
    // 整体，这句话一定对每个点都执行过，加在一起是O(V)
    marked[v] = true;    

    // 整体下面的循环一定遍历了所有的边，加在一起是O(E) 
    typename Graph::adjIterator adj(G,v);    
    for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )    
        if( !marked[e->other(v)] )    
            pq.insert(*e);    
}

当然了，依然是，由于V一定是E的低阶项，所以，将O(V+E)的算法说成是O(E)没毛病（在数学上是满足大O定义的）。不过，如果是面试（或者笔试或者考试）的话，可能有的面试官较真，最好补充说明一下：）

加油！：）

• 提问者 new_chapter #1

  好的，明白了。忘了考虑mark 顶点这一步骤了

• 提问者 new_chapter #2

  感谢老师每次都这么认真回复！

• 血色星期二 #3

  老师，看着上面您的代码可以理解O(V + E)。但是再乘以log(E)是怎么理解呢？是 O(V) * O(logE) + O(E) * O(logE) 吗？这个 log(E) 是 extractMin 还是 insert ？

点开查看后面1条评论