我意识到 BFS 和 DFS 在通用图上的运行时间是 O(n+m),其中 n 是节点数,m 是边数,这是因为对于每个节点,必须考虑其邻接列表。但是,BFS和DFS在二叉树上执行时的运行时间是多少呢?我认为它应该是 O(n),因为可以从节点出去的边的可能数量是恒定的(即 2)。请确认这是否是正确的理解。如果不是,那么请解释一下二叉树上的 BFS 和 DFS 的正确时间复杂度是多少?
时间复杂度为BFS http://en.wikipedia.org/wiki/Breadth_first_search and DFS http://en.wikipedia.org/wiki/Depth_first_search只是O(|E|)
,或者就你而言,O(m)
.
在二叉树中,m
等于n-1
所以时间复杂度等于O(|V|)
. m
指边的总数,而不是每个顶点的相邻边的平均数。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)