理解大 O 符号 - 破解编码面试示例 9

Question

我被这两个代码卡住了。

代码 1

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

代码2（平衡二叉查找树）

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

作者说代码1的运行时间是O(2^n)，space复杂度是O(n)

而代码 2 是 O(N)

我不知道这两个代码有什么不同。看起来两者都是相同的二叉树

Answer 1

代码 1：

根据传入参数的内容，if() 语句运行 n 次，但函数调用自身 n-1 次。简化：

n * (n-1) = n^2 - n = O(n^2 - n) = O(n^2)

代码 2：

搜索只遍历树的每个元素一次，函数本身没有任何for()。由于有 n 项并且只访问了一次，因此是 O(n).

Answer 2

嗯，这是一个错误，因为第一个片段的运行时间复杂度为 O(2^n) 而不是 O(n^2)。

解释是：在每一步中，我们减少 n 但创建两倍的调用次数，因此对于 n 我们将使用 f(n-1) 调用两次，对于 n-1 的每个调用，我们将调用两次f(n-2) - 这是 4 次调用，如果我们再往下一层，我们将使用 f(n-3) 调用 8 次：所以调用次数是：2^1，然后是 2^2 , 然后 2^3, 2^4, ..., 2^n.

第二个代码片段在二叉树上执行一次传递并恰好到达每个节点一次，所以它是 O(n)。

Answer 3

第一个密码确实是O(2^n).

但是第二个代码不能是O(n)，因为那里没有n。这是许多人忘记的事情，通常他们假设什么是 n 而没有澄清它。

事实上，你可以根据任何事物来估计任何事物的增长速度。有时它是输入的大小（在第一个代码中是 O(1) 或 O(log n) 取决于大数字的使用），有时只是在参数上，如果它是数字。

所以当我们开始思考第二个代码中时间和内存依赖什么时，我们可以得到这些东西：

time=O(number_of_nodes_in_tree)
time=O(2^height_of_tree)
additional_space=O(height_of_tree)
additional_space=O(log(number_of_nodes))（如果树是平衡的）

所有这些同时都是正确的 - 它们只是将某些事物与不同事物联系起来。

Answer 4

首先，了解两种情况下的 N 是什么很重要。在第一个示例中，它非常明显，因为您可以直接在代码中看到它。对于第一种情况，如果构建 f(i) 调用树，您将看到它包含 O(2^N) 元素。的确，

            f(N)             // 1 node
        /          \ 
   f(N-1)         f(N-1)     // 2 nodes
  /      \      /      \
f(N-2) f(N-2)  f(N-2) f(N-2) // 2^2 nodes
...
f(1) ........ f(1)           // 2^(N-1) nodes

在第二种情况下，N（很可能）是树中的一些元素。正如您从代码中看到的那样，我们只遍历每个元素一次 - 您可能会意识到 node.value 为每个树节点调用一次。因此 O(N).

请注意，在此类任务中，N 通常表示 输入的大小 ，而 input 取决于你的问题。它可以只是一个数字（就像你的第一个问题）、一维数组、二叉树（就像你的第二个问题），甚至是一个矩阵（尽管在后一种情况下你可能希望看到像 "a matrix with a size M*N").

所以您的困惑可能来自于 "definition of N" 这两个问题之间的不同这一事实。换句话说，我可能会说 n2 = 2^n1.

Answer 5

对于代码2，判断一个函数的大O，不是要考虑递归的代价和递归的次数吗运行？

如果我们使用两种方法使用递归树和主定理来估计大 O:

递归树：每个级别的总成本将为每个级别的 cn，因为递归调用的次数和输入的分数相等，树的级别为 lg(n)，因为它是一个平衡的二叉搜索树。所以运行时间应该是 nlg(n)?

主定理：这应该是情况 2，因为 f(n) = n^logbase a (b)。那么根据高手定理，应该是nlg(n)运行ning次?

Answer 6

你对这两种情况的“N”感到困惑。在第一种情况下，N 指的是给定的输入。例如，如果 N=4，则调用的函数数为 2^4=16。你可以画出递归图来说明。因此 O(2^N)。

在第二种情况下，N是指二叉树中的节点数。所以这个 N 与输入无关，而是与二叉树中已经存在的节点数量有关。因此，当用户调用该函数时，它只访问每个节点一次。因此 O(N)。

Answer 7

我们可以认为是O(2^Depth)。

第一个例子中：深度为N，正好是书上提到的问题的输入

在第二个例子中：它是一棵平衡的二叉搜索树，因此，它有Log(N)层（深度）。注：N是树中的元素个数。

=> 让我们应用 O(2^Depth).. O(2^(Log(N)) = O(N) 留下 O(N) 复杂性。

提醒：

在计算机科学中，我们通常将 Log2(n) 称为 Log(n)。
以 b 为底的 x 的对数是你对 b 求得 x 结果的指数。

在上述复杂性中：O(2^(Log(N)，我们将基数 2 提高到 Log2(N)，这给了我们 N。（检查两个提醒）

这个link可能会有用。

理解大 O 符号 - 破解编码面试示例 9

Understanding Big O notation - Cracking the coding interview example 9

algorithm

tree

big-o

notation