algorithm - 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。考虑到除根以外的每个节点都有一条从其父节点到自身的边，并且这些边覆盖了所有节点，这很容易看出树中存在的边。