时间戳

首页 > 解决方案 > 为什么平衡 BST 中节点值之和的时间复杂度为 O(n)？

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

问题描述

我正在尝试学习 Big 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);
}

标签： javaalgorithmrecursionbig-obinary-search-tree

解决方案

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

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

推荐阅读