lazy prim的时间复杂度疑问
来源：8-4 Prim算法的优化
new_chapter
2019-02-16
在算法与数据结构课程中，您在讲解lazy prim算法（存边，未优化）时间复杂度时，外层循环 while(!pq.isEmpty()) ，循环次数为边数E。内层包括两个部分：
-
从堆中取出最小的边 pq.extractMin(), 时间复杂度为logE
-
visit 函数，把所有的visit对邻边的遍历合在一起，也是E次（邻接矩阵V^2次），每次执行pq.insert()函数，复杂度为logE。
综合起来是 O(ElogE + ElogE ), 也就是 O(ElogE)。
在您的另外一个回复中，告诉我lazy prim的复杂度（E+V）logE是如何得出的呢？我是在哪里理解的不到位？
写回答
1回答
-
简单的说，在图论算法中，只要图要遍历一遍，复杂度都应该是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定义的）。不过，如果是面试（或者笔试或者考试）的话，可能有的面试官较真，最好补充说明一下：）
加油！：）
542019-04-29
相似问题