为什么平衡 BST 中节点值之和的时间复杂度为 O(n)？

Question

我正在尝试学习大 O 表示法，但遇到了一个问题。在这段代码中，我们试图找到节点值的总和。由于有 2 次调用 sum 函数，所以每次调用的调用次数都是以前的两倍。那么为什么运行时间是 O(n) 而不是 O(2^n)。

int sum(Node node) {
   if(node==null)
      return 0;
   return sum(node.left) + node.value + sum(node.right);
}

Answer 1

看这些时你的推理是部分正确的，这确实是指数级的 - 但在 h 中 - 而不是在 n 中（其中 h 是高度的树）- 因为每次迭代调用，你还有 h-1 个节点要走，最后产生 O(2^h)。

然而，在这里，n 是树中节点的数量。这在 O(n) 中运行，因为每个节点只被遍历一次 - 并且有 n 个节点，总共有 O(n).

Answer 2

如果我理解你说的是对的，你的论点基本上就是

每次调用递归分支两次，
所以每一层的递归调用次数是上一层的两倍，
所以运行时间为 Θ(2ⁿ).

@amit 的回答指出，在从步骤 (2) 到步骤 (3) 的过程中，存在一个小而关键的错误，即从 n（节点数）切换到 h（树的高度）。

推理过程中其实还有一个小问题，那就是从第（1）步到第（2）步。例如，想象一下，您正在使用的树是一棵退化树，其中每个节点只有左 child 而没有右 child。如果你跟踪这里的递归，你会发现每个级别的调用数量不会呈指数增长，因为一半的调用离开树并立即终止。你是对的，每个级别最多 2^k 次递归调用，但这会多算完成的工作量。

为了更直接地获得 O(n) 界限，而不是计算递归分支的次数并将其与高度相关联，而是考虑总共进行了多少次递归调用。在根节点有一个，每个节点从那里产生两个新的递归调用。这使得递归调用的总数最多为 2n + 1，并且由于每次调用的工作时间为 O(1)，因此完成的总工作量为 O(n)。无论树形如何，这个论点都有效，在其他递归上下文中使用它是一个很好的选择。

为什么平衡 BST 中节点值之和的时间复杂度为 O(n)？

Why is the time complexity of the sum of the values of nodes in a balanced BST O(n)?

java

algorithm

recursion

big-o

binary-search-tree