Big O 练习
例一
题目来自《程序员面试金典》第六章例9
这段代码将平衡二叉搜索树的所有节点值相加。
1
2
3
4
5
6
| int sum(Node node){
if(node == null){
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
|
方法一：
由之前的基础介绍可知，通常情况下递归的时间复杂度为O(分支数^递归深度)。
二叉搜索树的高度约等于log2(N), N为节点数，分支为2，因此可得时间复杂度约为O(2^log2(N)）。
由2^P = Q 可得，P = log2(Q)。令P = 2^log2(N)，可得log2(P) = log2(N)，所以P = N，因此时间复杂度简化为O(N)
方法二：
因为需要所有节点值相加，所以需要遍历N个节点，因此式O(N)
例二
斐波那契数列的优化，取自《程序员面试金典》例14，例15
以下代码打印从0到n的斐波那契数列。
1
2
3
4
5
6
7
8
9
10
11
| void allFib(int n){
for(int i = 0;i<n;i++){
System.out.println(i + ": " + fib(i));
}
}
int fib(int n){
if (n <= 0) return 0;
else if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
|
这里有一个陷阱，在看到fib有两支递归调用的时候，能够想到时间复杂度约等于O(2^N)，在外层使用N次循环，那么时间复杂度是O(N * 2^N)，其实并不。
在每一次调用fib的时候，都是2^N的形式
那么从1到N，fib函数的运行应该时间是2^1 + 2^2 + ··· + 2^N，这个式子约等于2^(N+1)，也就是说时间复杂度仍然为O(2^N)
以下通过在allFib函数添加一个数组来保存被计算过的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void allFib(int n){
int[] memo = new int[n+1];
for (int i = 0; i < n; i++){
System.out.println(i + ": " +fib(i, memo));
}
}
int fib(int n, int[] memo){
if (n <= 0) return 0;
else if (n == 1) return 1;
else if (memo[n] > 0) return memo[n];
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
|
算法的运行将会如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| fib(0) ->return 0
fib(1)->return 1
fib(2)
fib(1)->return 1
fib(0)->return 0
store 1at memo[2]
fib(3)
fib(2)->lookup memo[2]->return 1
fib(1)->return 1
store 2at memo[3]
fib(4)
fib(3)->lookup memo[3]->return 2
fib(2)->lookup memo[2]->return 1
store 3at memo[4]
fib(5)
fib(4)->lookup memo[4]->return 3
fib(3)->lookup memo[3]->return 2
store 5at memo[5]
...
|
可以看到，每次递归其实是直接从数组中取出之前的值，将不会进行更深层次的调用，也就是说这个过程只是进行了N次常数时间的操作，因此时间复杂度是O(N)。
例三
取自《程序员面试金典》第六章附加题(11)
该段代码打印所有长度为K的字符串，字符串要求有序。代码先生成长度为K的字符串，再检测是否有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| int numChars = 26;
void printSortedStrings(int remaining) {
printSortedStrings(remaining, "");
}
void printSortedStrings(int remaining, String prefix) {
if (remaining == 0) {
if (isInOrder(prefix)) {
System.out.println(prefix);
}
} else {
for (int i = 0; i < numChars; i++) {
char c = ithLetter(i);
printSortedStrings(remaining - 1, prefix + c);
}
}
}
boolean isInOrder(String s) {
for (int i = 1; i < s.length(); i++) {
int prev = ithLetter(s.charAt(i - 1));
int curr = ithLetter(s.charAt(i));
if (prev > curr) {
return false;
}
}
return true;
}
char ithLetter(int i) {
return (char) (((int) 'a') + i);
}
|
程序的主要时间增加来自以下两段代码：
第一段是printSortedStrings中的循环
1
2
3
4
| for (int i = 0; i < numChars; i++) {
char c = ithLetter(i);
printSortedStrings(remaining - 1, prefix + c);
}
|
是一个单只的递归调用，在长度为k的情形下，每一位都有26 (numChars = 26, 在开头有定义)中可能，因此是c^k的全排列，时间复杂度为O(c^k)
第二段是isInOrder中的循环用于检测字符串是否有序
1
2
3
4
5
6
7
8
9
10
| boolean isInOrder(String s) {
for (int i = 1; i < s.length(); i++) {
int prev = ithLetter(s.charAt(i - 1));
int curr = ithLetter(s.charAt(i));
if (prev > curr) {
return false;
}
}
return true;
}
|
字符串长度为k，因此每一次检测都需要O(k)的时间
因此总时间为每一次检测字符串有序的时间乘以生成的总字符串个数，时间复杂度为O(k*c^k)。
