拓扑排序时间复杂度o(n+e)怎么算的？
拓扑排序时间复杂度o(n+e)怎么算的？
展开
收起
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
3
条回答
写回答
-
TA有点害羞，没有介绍自己...
你看一下求入度那个算法是不是有两个for循环，一个遍历顶点，一个遍历与这个顶点有关的边，注意这里不是e，两个for的最终结果才是遍历所有的边，才是e，所以算法复杂度是O(e)hiahia.
2019-07-17 22:50:29赞同 展开评论 -
-
胜天半子对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。2019-07-17 22:50:29赞同 展开评论
相关问答