理解大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),空间复杂度为O(n)

代码2是O(N)

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

Answer 1

好吧，这是一个错误，因为第一个片段在 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 2

首先,了解两种情况下的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通常表示输入的大小,而输入的大小取决于您的问题.它可以只是一个数字(比如你​​的第一个问题),一维数组,二叉树(比如你的第二个问题),甚至是一个矩阵(尽管在后一种情况下你可能会看到像"一个大小为M*N"的矩阵.

所以你的困惑可能来自于这两个问题之间"N的定义"不同的事实.换句话说,我可以这么说n2 = 2^n1.