BFS和DFS在二叉树上的运行时间是否为O（N）？ [英] Is the runtime of BFS and DFS on a binary tree O(N)?

问题描述

我意识到，一般图上BFS和DFS的运行时间为O（n + m），其中n是节点数，m是边数，这是因为对于每个节点，必须考虑其邻接表。但是，当在二进制树上执行BFS和DFS时，其运行时是什么？我认为应该是O（n），因为可以从一个节点移出的边缘的可能数量是恒定的（即2）。请确认这是否是正确的理解。如果不是，那么请解释二叉树上BFS和DFS的正确时间复杂度是什么？

I realize that runtime of BFS and DFS on a generic graph is O(n+m), where n is number of nodes and m is number of edges, and this is because for each node its adjacency list must be considered. However, what is the runtime of BFS and DFS when it is executed on a binary tree? I believe it should be O(n) because the possible number of edges that can go out of a node is constant (i.e., 2). Please confirm if this is the correct understanding. If not, then please explain what is the correct time complexity of BFS and DFS on a binary tree?

推荐答案

BFS 和 DFS 只是 O（| E |），或者您的情况是 O（m）。

The time complexities for BFS and DFS are just O(|E|), or in your case, O(m).

在二叉树中， m 等于 n -1 ，所以时间复杂度等效于 O（| V |）。 m 是指边的总数，而不是每个顶点相邻边的平均数目。

In a binary tree, m is equal to n-1 so the time complexity is equivalent to O(|V|). m refers to the total number of edges, not the average number of adjacent edges per vertex.

这篇关于BFS和DFS在二叉树上的运行时间是否为O（N）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！