拓扑排序时间复杂度one怎么算的

1楼：沈伟栋

对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为o(e)；建零入度顶点栈的时间复杂度为o(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为o(n+e)。

通常，这样的线性序列称为满足拓扑次序(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的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

2楼：星麓の守护

因为算法中要输出n个点（即入度为0的点输出），要删掉e条弧（即入度不为0的点入度减一），所以时间复杂度为o(n+e)

3楼：sun了个晒

你看一下求入度那个算法是不是有两个for循环，一个遍历顶点，一个遍历与这个顶点有关的边，注意这里不是e，两个for的最终结果才是遍历所有的边，才是e，所以算法复杂度是o(e)hiahia.

在用邻接表表示图时，拓扑排序算法时间复杂度为多少

4楼：匿名用户

设图中顶点n个，弧e条，则在邻接表上进行拓扑排序的时间复杂度为o(n + e)