Question

n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为？查了好几个地方的答案，答案大部分

n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为？查了好几个地方的答案，答案大部分给的是O(n+e),也有O(n*n)？我觉得是O(n*e)。到底是啥呢？

Answer 1

O(n+e)是对的，O(n*n)是用邻接矩阵存储时的时间复杂度。
算法就是遍历每一条边，然后把每条边的终点的入度+1.
在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O(n+e)。
在邻接矩阵中，算法需要遍历邻接矩阵的每一个点，而邻接矩阵有n*n个点，所以时间复杂度是O(n*n)。
有什么不懂的可以追问。

追问

题中说求每个顶点就是一个顶点的意思吗？若求所有顶点是不是就是n*(n+e)，然后时间复杂度就是O(n*n)?

追答

如果我理解的没错，你的算法是，选择一个顶点，然后找所有进入这个顶点的边，来计算入度。这种算法的时间复杂度的确是O(n*e)。
而比较高效的算法是，遍历所有的边，然后把每一条边进入的顶点的入度+1，这样遍历全部的边后，所有顶点的入度也就计算好了。这种算法的时间复杂度就是我上面说的。

追问

嗯，谢谢啦！

Answer 2