算法题目
分析
斐波那契数列满足公式f(n) = f(n-1) + f(n-2)，n > 0。这里我们的第一想法是使用递归，可是直接翻译公式出来的递归调用是这样的：
int fib(int n) {
if (n == 1) {
return 0;
}
if (n == 2){
return 1;
}
return fib(n - 1) + fib(n - 2);
}可是这个函数的事件复杂度恰好是最糟糕的指数级。怎么来证明它是指数级呢？
下面来推导它的时间复杂度。
对于斐波那契数，有定理 ：当n >= 0时，F < (5/3)。
首先使用归纳法来证明。对于基准情形，F1 = 0 < 5/3，F2 = 1 < 5/3。
然后假设i = 1，2，3，…，n 成立；这就是归纳假设。那么我们只需要证明出F < (5/3) 即可。
根据公式我们可以得出F = F + F。
推到过程如下：
F < (5/3) + (5/3)
F < (3/5)(5/3) + (3/5)(5/3)
F < (24/25)(5/3) < (5/3)
得证 F < (5/3)。
同样的证明过程，可以证明出当n > 4时， F > (3/2)。
而T(n) = T(n-1) + T(n-2) + 3。
T(n) >= fib(n) >= (3/2)。
因此这个函数的运行时间是以指数的速度增长。
更优解法
其实上面的递归违反了递归的合成效益法则，才导致了运行时间的指数级增长。
递归的四条基本准则：
1、基准情形。必须有总有某些基准情形，它无须递归就能解出。
2、不断推进。对于那些需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
3、设计法则。假设所有的递归调用都能运行。
4、合成效益法则。在求解一个问题的同一示例时，切勿在不同的递归调用中做重复性的工作。
我们可以利用一个简单的for 循环来求解第N个斐波那契数。
int fibonacci(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
int a = 0;
int b = 1;
int c = 0;
for (int i = 3; i < n + 1; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}使用两个变量分别保存f(n-1) 和f (n-2)，然后从基准情况开始往第 n 个数推进。
改进后的函数时间复杂度是O(n)，运行时间大概是 （3n - 1）大大减少了运行时间。