我如何找到以下递归算法的时间复杂度？

Question

假设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

Answer 1

当前，当 n 被视为 树 中的节点数时，它确实具有 O(n) 复杂度。

对于根的每个子节点，您对 c 中的所有子树根调用递归函数。所以基本上，你在 O(V+E) 中对这个图进行 DFS -> 在你的情况下，当图是一棵树时，它等于 O(V)。

注意，您在 if 语句中调用了 findMax 的递归函数——如果它为真，则再次计算它——这增加了 O(2*n) 的复杂度。计算 findMax 函数一次，将其结果分配给局部变量并用它检查和更新 maxValue 将复杂度降低到 O(n)。