BFS和DFS的运行时是否在二叉树O(N)上？

Question

我意识到泛型图上的BFS和DFS的运行时是O(n + m),其中n是节点数,m是边数,这是因为对于每个节点,必须考虑它的邻接列表.但是,当它在二叉树上执行时,BFS和DFS的运行时是什么？我认为它应该是O(n),因为可以离开节点的可能边数是恒定的(即2).请确认这是否正确理解.如果没有,那么请解释二叉树上BFS和DFS的正确时间复杂度是什么？

Answer 1

BFS和DFS的时间复杂性只是O(|E|)或者在您的情况下O(m).

在二叉树中,m等于n-1时间复杂度等于O(|V|).m指的是边的总数,而不是每个顶点的相邻边的平均数.

Answer 2

是的,O(n)是正确的.

还要注意,边数可以更精确地表示为节点数 - 1.通过考虑除了根之外的每个节点都有从其父节点到其自身的边缘,可以很容易地看出这一点.这些边缘覆盖所有节点树中存在的边.