了解Big O表示法-破解编码面试示例9 [英] Understanding Big O notation - Cracking the coding interview example 9

问题描述

我被这两个代码困住了。

I got stuck with this two codes.

代码1

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

代码2 （平衡二进制搜索树）

Code 2 (Balanced binary search tree)

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

作者说代码1的运行时为O（2 ^ n），空间复杂度是O（n）

the author says the runtime of Code 1 is O(2^n) and space complexity is O(n)

代码2是O（N）

我不知道这是什么这两个代码之间存在差异。看来它们都是相同的二叉树

I have no idea what's different between those two codes. it looks like both are the same binary trees

推荐答案

好吧，因为第一个代码段在O（2 ^ n）中运行，所以出现了一个错误不是O（n ^ 2）。

Well there's a mistake because the first snippet runs in O(2^n) not 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。

The explanation is: In every step we decrement n but create twice the number of calls, so for n we'll call twice with f(n-1) and for each one of the calls of n-1 we'll call twice with f(n-2) - which is 4 calls, and if we'll go another level down we'll call 8 times with f(n-3): so the number of calls is: 2^1, then 2^2, then 2^3, 2^4, ..., 2^n.

第二个片段对一棵二叉树进行一次遍历，并且恰好到达每个节点一次，所以它是O（n）。

The second snippet is doing one pass on a binary tree and reaches every node exactly once, so it's O(n).

这篇关于了解Big O表示法-破解编码面试示例9的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！