递归模式的大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^depth)。

例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)。

谢谢！

- moustacheman

---

澄清一下：2^(log N) 在数学上和 N 是完全相同的。因此，O(2^log N) 可能和 O(N) 是相同的。无论这个函数是否平衡，它都是 O(N)，因为你必须访问所有 N 个节点才能读取所有 N 个值并加起来。 - Patrick87

在这个问题中，无论你是否使用二叉树，你都需要访问每个节点一次，因此你的复杂度是 O(n)。 - Wickoo

它的时间复杂度为O(2^N)，其中N是深度。它的时间复杂度为O(2^log N)，其中N是节点数。N是一个变量，问题中没有提到N，因此可以假设它是任何值 - 也许告诉你它是O(2^N)的人只是做了与你不同的假设（或者他们可能是错的）。 - Bernhard Barker

那个 sum 函数不是 O(2^log n)，而是 O(n)。 - Mulan

Answer 1

• 与其他树一样，二叉树的复杂度为O(n)，因为您最终要遍历树的所有元素。通过将其分成两半，我们并没有做任何特殊的事情，只是单独计算相应子节点的总和。

• 这个术语出现的原因是，如果平衡，则树中的元素数量（叶子节点+非叶子节点）为2^(log_2(n))。（log2(n)级别）

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

在哪里可能有影响？如果正在搜索一个元素，那么它会很重要（无论是否平衡）。

- user2736738

Answer 2

我会试着解释一下。

在一个平衡的二叉树中，每个父节点左边应该有一半的子节点，右边也是如此。第一层是根，有1个元素，下一层有2个元素，再下一层有4个元素，依此类推，直到8个元素等等。所以对于一棵有L层的树，你将会有2^L - 1个节点。

反过来看，如果你要插入N个元素到一棵树中，你最终得到的是一个深度为L = log_2(N)的平衡二叉树，因此你只需要调用递归算法log_2(N)次。每一层都要调用两次递归算法，所以在你的例子里，你最终会有2^log_2(N)次调用和O(2^log_2(N))的运行时间。注意到2^log_2(N) = N，所以无论如何它都是一样的，但我们马上就会谈到二叉树的优势。

如果这棵树不平衡，你最终得到的深度大于log_2(N)，因此你会有更多的递归调用。在极端情况下，当父节点的所有子节点都在左边（或右边）时，你将有N个递归调用，但每个调用将立即返回一个分支（一侧没有子节点）。这样你将会有O(N)的运行时间，与之前相同。每个节点只被访问一次。

平衡树的一个优点是在搜索等操作中。如果左子节点总是比父节点小，右子节点总是比父节点大，那么你可以在O(log_2(N))的时间内（而非2^log_2(N)！）在N个节点中查找元素n。然而，如果你的树严重不平衡，这个搜索就变成了对所有值的线性遍历，你的搜索时间变成了O(N)。如果N非常大，或者你需要经常执行此搜索，则可能会导致算法无法处理。

- Engineero