例1
下面算法的时间复杂度是____
int foo(int n) {
if (n <= 1) {
return 1；
}
return n * foo(n - 1);
}
我们要做的第一步便是确定关键操作，这里的关键操作显然是if语句，那么我们只需要判断if语句执行的次数即可。首先我们看到这是一个递归过程：foo会不断的调用自身，直到foo的实参小于等于1，foo就会返回1，之后便不会再执行if语句了。由此我们可以知道，if语句调用的次数为n次，所以时间复杂度为O(n)。
例2
以下函数的时间复杂度为____
void recursive(int n, int m, int o) {
if (n <= 0) {
printf("%d, %d\n", m, o);
} else {
recursive(n - 1, m + 1, o);
recursive(n - 1, m, o + 1);
}
}
首先，它的关键操作时if语句，因此我们只需判断出if语句的执行次数即可。以上函数会在n > 0的时候不断递归调用自身，我们要做的是判断在到达递归的base case（即n <= 0）前，共执行了多少次if语句。我们假设if语句的执行次数为T(n, m, o)，那么我们可以进一步得到：T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) （当n > 0时）。我们可以看到base case与参数m, o无关，因此我们可以把以上表达式进一步简化为T(n) = 2T(n-1)。
由此我们可得:
T(n) = 2T(n-1)
= (2^2) * T(n-2)
= (2^3) * T(n-3)
= ...
而很明显T(1) = 2
所以:
T(1) = 2
T(2) = 2T(n-1) = 2 * T(1) = 2 * 2 = 2^2
T(3) = (2^2) * T(n-2) = (2^2) * T(1) = 2^3
T(4) = (2^3) * T(n-3) = (2^3) * T(1) = 2^4
...
T(n) = 2^n
所以我们可以得到以上算法的时间复杂度为O(2^n)。
例3
如下程序的时间复杂度为____（其中m > 1，e > 0）
x = m;
y = 1;
while (x - y > e) {
x = (x + y) / 2;
y = m / x;
}
print(x);
以上算法的关键操作即while语句中的两条赋值语句，我们只需要计算这两条语句的执行次数即可。我们可以看到，当x - y > e时，while语句体内的语句就会执行，x = (x + y) / 2使得x不断变小（当y«x时，执行一次这个语句会使x变为约原来的一半），假定y的值固定在1，那么循环体的执行次数即为~logm，而实际情况是y在每次循环体最后都会被赋值为m / x，这个值总是比y在上一轮循环中的值大，这样一来x-y的值就会更小，所以以上算法的时间复杂度为O(logm)。
假设y一直为1，那么:
| 执行的次数 | x的大小 |
| 0 | m |
| 1 | m/2 |
| 2 | m/(2^2) |
| 3 | m/(2^3) |
| n | m/(2^n) |
m/(2^n) > 1
令 m/(2^n) = 1
则 n = log(m) 以2为基
例4
假设某算法的计算时间可用递推关系式T(n) = 2T(n/2) + n，T(1) = 1表示，则该算法的时间复杂度为____
T(1) = 1
T(n) = 2T(n/2) + n
T(n/2) = 2T(n/4) + n/2
T(n/4) = 2T(n/8) + n/4
...
所以:
T(n) = 2T(n/2) + n
= (2^2) * T(n/(2^2)) + 2*n
= (2^3) * T(n/(2^3)) + 3*n
= ...
T(1) = 1
T(2) = 2T(n/2) + n = 2T(1) + 2 = 4
T(4) = (2^2) * T(n/(2^2)) + 2*n = (2^2) * T(1) + 2*4 = 12
T(8) = (2^3) * T(n/(2^3)) + 3*n = (2^3) * T(1) + 3*8 = 32
...
T(n) = (2^k) + k*n (k = logn)
= n + nlogn
所以时间复杂度为 O(nlogn)
总结
T(1) = 1
T(n) = T(n-1)
时间复杂度: O(1)
T(1) = 1
T(n) = T(n-1) + 1
时间复杂度: O(n)
T(1) = 1
T(n) = 2T(n-1)
时间复杂度: O(2^n)
T(1) = m
T(n) = T(n-1) / 2
时间复杂度: O(logm)
T(1) = 1
T(n) = 2*T(n/2) + n
时间复杂度: O(n + nlogn) = O(nlogn)
