leetcode 210的时间复杂度

来源：13-7 拓扑排序算法的实现

讲武德的年轻人

2022-04-13

bobo老师，我用课上方法做了lc 210问题，方法跟您在github上main2方法差不多: https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0210-Course-Schedule-II/cpp-0210/main2.cpp

但是您写的时间复杂度为啥是O(E)呢？prerequisites的长度就是边的长度，numCourses的数目就是节点的数量。所以，第32-34行的for循环不是O(V)复杂度吗？还有后面的while循环，我的理解是，最差情况每个节点都要入队，而且while内部还有for循环遍历边的数量，所以整个while循环这里不是O(E + V)吗？谢谢您的解惑！

for(int i = 0; i < numCourses; i ++)    
    if(pre[i] == 0)    
        q.push(i);

写回答

1回答

liuyubobobo

2022-04-13

已采纳

应该是 O(V + E)。

继续加油！：）

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1599 学习 · 330 问题

查看课程

相似问题

Leetcode 490时间复杂度分析

回答 1

关于adj数组中存放哈希表的空间复杂度疑问

回答 1

leetcode 752的时间、空间复杂度

回答 1

LC 1102时间复杂度分析

回答 1

寻找桥

回答 1

打开慕课网App查看更多内容