算法题目
查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
* 前2个数是 0 和 1 。
* 第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …
分析
斐波那契数列满足公式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 = 40时，大概就需要0.5秒才能计算出来;
当n 为50时，需要等很久才能计算出实际的值。
下面来推导它的时间复杂度。
对于斐波那契数，有定理 ：当n >= 0时，Fn < (5/3)n。
首先使用归纳法来证明。对于基准情形，F1 = 0 < 5/3，F2 = 1 < 5/3。
然后假设i = 1，2，3，…，n 成立；这就是归纳假设。那么我们只需要证明出Fn+1 < (5/3)n+1 即可。
根据公式我们可以得出Fn+1 = Fn + Fn-1。
推到过程如下：
Fn+1 < (5/3)n + (5/3)n-1
Fn+1 < (3/5)(5/3)n+1 + (3/5)2(5/3)n+1
Fn+1 < (24/25)(5/3)n+1 < (5/3)n+1
得证 Fn+1 < (5/3)n+1。
同样的证明过程，可以证明出当n > 4时， Fn > (3/2)n。
而T(n) = T(n-1) + T(n-2) + 3。
T(n) >= fib(n) >= (3/2)n。
因此这个函数的运行时间是以指数的速度增长。
可能有点不同的是，有的斐波那契数列是从1，1，2，3，…. 开始，所以有些微的差别。
这只是对级数做了一次平移。我们可以找一些方便证明的情况来证明。
更优解法
其实上面的递归违反了递归的合成效益法则，才导致了运行时间的指数级增长。
递归的四条基本准则：
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）大大减少了运行时间。
版权声明：本文为博主原创文章，转载请注明出处。 https://blog.csdn.net/u011619283/article/details/53006083
网友评论