对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。
时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
扩展资料
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级，找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
参考资料来源：百度百科-拓扑排序
参考资料来源：百度百科-时间复杂度
能详细解释下这段吗，还是不明白，看了书不明白才问的，谢谢
追答书上如是说：拓扑排序的步骤：
（1）在有向图中选一个没有前驱的顶点输出
（2）删除该顶点和所有以它为尾的弧
程序中建立了入度的数组，没有前驱的顶点入度为0，输出即为（1），然后按邻接表找到以它为尾的节点，将这些节点入度减1，便是（2）。
拓扑排序初始参数只有邻接表，所以第一步建立入度数组，因为每1入度对应一条弧，总共e条弧，建立入度数组的复杂度为O(e)。每个节点输出一次，n个节点遍历一次，时间复杂度为O(n)。（使用零入度节点栈的原因是，如果不把零入度节点入栈，每次输出时都要遍历节点。建立此栈，只需遍历一次。）然后节点入度减1的操作，也是一条弧对应一次，e条弧总共O(e)。
以上总计O(n+2e)即O(n+e)。
O(n+2e)和O(n+e)是一个数量级？这是怎么回事呢？
追答O(n)和O(2n)是一个数量级，或者说没有后者，O(2n)是O(n)即线性阶。前面乘以常数，是同一个数量级。这个能理解吗？应该在数据结构/算法基础理论中讲到的。
n和e是两个不同的变量。
参考资料：严蔚敏.吴伟民《数据结构（C语言版）》
本回答被提问者采纳你看一下求入度那个算法是不是有两个for循环，一个遍历顶点，一个遍历与这个顶点有关的边，注意这里不是e，两个for的最终结果才是遍历所有的边，才是e，所以算法复杂度是O(e)hiahia.