1楼：匿名用户
设图中顶点n个，弧e条，则在邻接表上进行拓扑排序的时间复杂度为o(n + e)
拓扑排序时间复杂度o(n+e)怎么算的？
2楼：沈伟栋
对有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的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
3楼：星麓の守护
因为算法中要输出n个点（即入度为0的点输出），要删掉e条弧（即入度不为0的点入度减一），所以时间复杂度为o(n+e)
4楼：sun了个晒
你看一下求入度那个算法是不是有两个for循环，一个遍历顶点，一个遍历与这个顶点有关的边，注意这里不是e，两个for的最终结果才是遍历所有的边，才是e，所以算法复杂度是o(e)hiahia.
建立邻接表的时间复杂度为o(n+e)，是怎么得来的以及表示什么，请赐教，详细点
5楼：匿名用户
如果输入的顶点信息即为顶点编号［0-（n-1）］,比如输入0的时候，访问次数为1+e0（e0在无向图：编号为0结点的邻边数；在有向图：编号为0的出度），所以无向图总的次数为n+e0+e1+…+en-1=n+2e，有向图为n+e，时间复杂度为o（n+e）。
如果输入的顶点信息不为顶点编号，则要查找顶点编号，平均次数为（n+1）/2，总次数（n+1）*e/2（区分e的有向图跟无向图），时间复杂度为o（n*e）。
6楼：匿名用户
其实是o(n + e)，顶点加上边数
那个o(n*e)的意思是每次插入一条边，都需要重新查找边所包含两个顶点信息对应的下标，正常的算法没这么弱智吧，不需要顶点信息即为顶点的下标，用散列等方法可以不用这样的
n个顶点e条边的图g用邻接表存储，则求每个顶点入度的时间复杂度为？查了好几个地方的答案，答案大部分
7楼：琦洛
o(n+e)是对的，o(n*n)是用邻接
抄矩阵存储时的时bai间复杂度。
算法就du是遍历每一条边
zhi，然后把每条边的终点的入
dao度+1.
在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是o(n+e)。
在邻接矩阵中，算法需要遍历邻接矩阵的每一个点，而邻接矩阵有n*n个点，所以时间复杂度是o(n*n)。
有什么不懂的可以追问。
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为
8楼：乌石
答案是o（n+e） 但是邻接表里面不是每个边被储存两次吗，为什么不是n+2e呢？
在大o表示法中o（n+2e)通常应表示为o（n+e）
直接选择排序算法在最好情况下的时间复杂度为多少
1楼 q给你毛起 关键字比较次数永远是n n 1 2，记录移动次数最多为3 n 1 ，最少0次，前者起主导作用，因此实际上时间复杂度还是o n 2 。 在直接选择排序中，共需要进行n 1次选择和交换，每次选择需要进行 n i 次比较 1 i n 1 而每次交换最多需要3次移动，因此，总的比较次数c ...
各种排序法的时间复杂度到底多少,各种排序法的时间复杂度到底多少 10
1楼 世界文明导师 根据《算法导论 中文版 》p83 以及《算法 中文版 》部分章节版内容 算法 最坏情况运行时权间 平均情况 冒泡 插入 选择 排序 n 2 n 2 快速排序 n 2 n log n 希尔排序 希尔增量 n 2 n 1 3 2 堆排序 n log n n log n 注 希尔排序的...
归并排序的时间复杂度是多少,归并排序的时间复杂度O是怎么算出来的呢
1楼 二分归并排序是一种分治算法 主定理方法 符合主定理 case 2 动动你的小手点个赞。 2楼 伟大的小天同学 o nlogn 和o nlog2n 是一样的。。归并排序如果不借助辅助空间的话，复杂度为o n 2 ，借助的话就是o nlogn o nlog2n 3楼 o n 以2为底的n的对数 。...