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

Question

我正试图学习大O符号，我遇到了一个问题。在这段代码中，我们试图找到节点值的总和。并且由于有2个求和函数的调用，所以每个调用的调用次数将是以前的两倍。所以为什么运行时是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)的总数。