我如何找到下面的递归算法的时间复杂度？
我如何找到下面的递归算法的时间复杂度？
提问于 2018-10-23 00:12:02
假设r是树的根(可以是非二进制的)，c是r的子节点，并且每个节点都包含一个整数。
Algorithm findMax(r)
if r = null return null
int maxValue = r.value
if r.isLeaf return maxValue;
for each child c of r do{
if findMax(c) > maxValue
maxValue = findMax(c)
}
return maxValue回答 1
Stack Overflow用户
回答已采纳
发布于 2018-10-23 01:12:54
目前，当考虑n为树中的节点数时，其复杂度为O(n)。
对于根的每个子节点，您可以对c中的所有子树根调用递归函数。所以基本上，你在这个图上执行DFS，在你的例子中，它使得O(V+E) ->，当这个图是一棵树时，它等于O(V)。
注意，您在if语句中调用了findMax的递归函数-如果为真，则重新计算它-这会将复杂度增加到O(2*n)。计算一次findMax函数，将其结果赋给本地变量，并用它检查和更新maxValue，将复杂度降低到O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52933573
复制相关文章
相似问题