algorithm - 递归模式的大 O 时间复杂度

Question

我对递归模式的运行时有疑问。

示例 1

int f(int n) {
  if(n <= 1) {
    return 1;
  }

  return f(n - 1) + f(n - 1);
}

我可以理解上面代码的运行时间是 O(2^N) 因为如果我传递 5，它会调用 4 两次然后每个 4 调用 3 两次并跟随直到它达到 1 即，像 O(branches^深度)。

示例 2 平衡二叉树

int sum(Node node) {
  if(node == null) {
    return 0;
  }

  return sum(node.left) + node.value + sum(node.right);
}

我读到上面代码的运行时间是 O(2^log N)，因为它是平衡的，但我仍然认为它是 O(2^N)。谁能解释一下？

1. 当元素数量每次减半时，运行时间为 log N。但是二叉树如何在这里工作？
2. 2^log N 只是因为它是平衡的吗？
3. 如果不平衡怎么办？

编辑: 我们可以解决 O(2^log N) = O(N) 但我认为它是 O(2^N)。

谢谢!

Answer 1

• 二叉树与此处的任何其他树一样具有 O(n) 的复杂性，因为您最终要遍历树的所有元素。通过减半，除了分别计算相应 child 的总和外，我们没有做任何特别的事情。

• 术语是这样来的，因为如果它是平衡的，那么 2^(log_2(n)) 是树中元素的数量(叶子+非叶子)。(log2(n) 级别)

• 同样，如果它不平衡也没关系。我们正在执行一个操作，其中每个元素都需要考虑，使运行时间为 O(n)。

它在哪里可能很重要？如果它正在搜索一个元素，那么它就很重要(无论它是否平衡)。