如何计算这个函数的运行时间？

Question

我正在尝试计算我在 Javq 中编写的函数的运行时间，我编写了一个函数来计算 BT 中所有正确子项的总和。

我在函数中使用了递归，我不太明白如何在BT中计算递归的运行时间（刚开始研究这个问题）。

这是我写的代码：

public int sumOfRightChildren(){
    return sumOfRightChildren(this.root);
}

private int sumOfRightChildren(Node root){
    if(root == null) //O(1)
        return 0;//O(1)
    int sum = 0;//O(1)
    if(root.right != null)//O(1)
        sum+=root.right.data;//O(1)
    sum += sumOfRightChildren(root.right); //worst case O(n) ?
    if(root.left != null)
    {
       sum += sumOfRightChildren(root.left);//worst case O(n)?
    }
    return  sum;
}

我试着写下我认为需要的运行时间，但我认为我做的不对。如果有人可以帮助指导我，我将不胜感激。

我正在尝试计算 T(n)。

Answer 1

好的，我想我明白了，最坏的情况是必须检查树中的所有节点，所以答案是：O(n)

Answer 2

由于您只访问每个节点一次，因此很容易看出运行时成本是 T(n) = n * K 其中 n是二叉树中的节点数，K 是预期的函数成本。

如果您想明确地考虑某些操作的成本，您可能无法准确计算它（没有输入示例）。例如，计算执行次数 sum+=... 是不可能的，因为它取决于特定的树。

在这种情况下，最坏的情况是 full 二叉树，如果是 n=1,2,...他们的深度：

复杂度为 O(2^n)（无论操作如何，因为它们都需要 O(1)已发布）。
sum+=root.right.data; 的成本是 T(n) = 2^n - 1（所有内部节点）。
sum+=... 的成本是 T(n) = 3 * (2^n - 1)（每个内部节点两次，每个节点一次).
...

（注意：确切的最终表达式可能会有所不同，因为您的 if(root.left != null) 没有用且更可取，让该条件成为 if(root == null)）

如何计算这个函数的运行时间？

How to calculate the runtime of this function?

java

recursion

binary-tree

runtime