了解Big O表示法

本文介绍了了解Big O表示法-破解编码面试示例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).