剑指Offer:斐波纳契数列

题目

写一个函数,输入n,求斐波纳契(Fibonacci)数列的第n项(n<=39)。斐波纳契数列定义如下:
斐波那契.jpg

分析

acmer或者coder应该对斐波纳契数列会非常熟悉,作为一道经典的题目虽然比较简单,但是通过对它的深入分析我们还是能够学到不少东西的。
这道题一共有两种基本解法,下面我们来逐一分析:

递归法:

这道题比较常用的方法之一就是递归求解,而且代码也比较简洁

1
2
3
4
5
6
7
long long Fibonacci(unsigned int n){
if (n <= 0)
return 0;
if (n == 1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}

但是利用递归,效率会非常低(就这道题来说)。我们以求解f(10)为例,来分析它的求解过程。想求f(10),需要先求得f(9)和f(8)。同样,想求得f(9),需要先求的f(8)和f(7)….我们可以用树形结构来表示这种依赖关系,如下图所示:
斐波纳契数列.jpg

可以看出,这棵树中存在大量重复的节点。如果n的值比较大的话,重复节点的数量将会非常骇人。所以要想改进这种方法,我们只需要把已经计算得到的数列中间项保存起来,下次需要计算的时候先查询一下。
更简单的方法就是自下而上依次类推f(0)+f(1)=f(2)、f(1)+f(2)=f(3)…时间复杂度相比递归要更加可观。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int Fibonacci(int n) {
if(n == 0)
return 0;
if (n == 1)
return 1;
int a = 0;
int b = 1;
int c = 0;
for (int i = 2; i <= n; i ++){
c = a+b;
a = b;
b = c;
}
return c;
}
}

这道题还可以利用矩阵公式求解,时间复杂度可以达到O(log n),但是实现起来比较复杂,而且也不太实用(明明是自己太懒)这里不在介绍,想了解的可以参考《剑指Offer》P76