初学算法——第二天：斐波那契数列

14天阅读挑战赛

1 定义

斐波那契数列的定义者，是意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的莱昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。

斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89…
这个数列从第3项开始，每一项都等于前两项之和。

递归表达式如下：

2 算法设计

1.递归算法

int Fib1(int n){
    if(n==1||n==2)   
    return 1;
    return Fib1(n-1)+Fib1(n-2);
}
1
2
3
4
5

该算法的时间复杂度计算：
假设T(n)表示Fib1(n)所需的基本操作次数，那么：

n=1时，T(n)=1；
n=2时，T(n)=1；
n=3时，T(n)=3；//调用Fib1(2)和Fib1(1)并执行一次加法运算（Fib1(2)+Fib1(1)）
即：
n>2时，T(n)=T(n-1)+T(n-2)+1；
1
2
3
4
5

斐波那契数列的通项公式：
由于T(n)>=F(n)，因此这是一个指数阶的算法！ 该算法的时间复杂度属于爆炸增量函数。
2.算法改进：采用迭代法进行算法设计

int Fib3(int n){
    if(n==1||n==2)   
         return 1;
    int s1=1; //用s1和s2记录前面的两项
    int s2=1;
    for(int i=3;i<=n;i++){
         int tmp=s1+s2;
         s1=s2;
         s2=tmp;
    }
    return s2;
}
1
2
3
4
5
6
7
8
9
10
11
12

此时时间复杂度为O(n),空间复杂度为O(1)。
实质上，斐波那契数列的时间复杂度还可以降到对数阶，本文不做过多讲解。

2 什么是爆炸级增量

在上篇文章中讲到，在设计算法时，我们要注意算法复杂度增量的问题，尽量避免爆炸级增量。那么什么样的是爆炸级增量呢？
一个小故事：《一棋盘的麦子》
有一个古老的传说，一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令：“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来，国王一看是个穷小子，想要反悔，说：“除了女儿，你要什么都可以。”小伙子说：“好吧，我只要一棋盘的麦子。您在第1个格子里放1粒麦子，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，以此类推，每一个格子里麦子的粒数都是前一格子里麦子粒数的两倍。把这64个格子放满了就行，我就要这么多。”国王听后哈哈大笑，觉得小伙子的要求很容易满足，满口答应。结果发现，把全国的麦子都拿来，也填不完这64个格子………国王无奈，只好把女儿嫁给了这个小伙子。
解析：通过这个故事，算出64格可放的麦子，总和为S
S=1+2一次方＋2的二次方+2的三次方…+2的63次方①
对式①等号的两边乘以2，等式仍然成立
2S=2的一次方+2的二次方+2的三次方+…+2的64次方
用式②减去①得
S=2的64次方-1= 18 446 744 073 709 551615
总重量约为7729000（亿千克）

我们称这样的函数为爆炸增量函数。

如果算法的时间复杂度是O(2^n)，随着n的增长，算法就会“爆掉”。例如：我们经常见到有些算法调试没问题，运行一段时间也没问题，但在关键的时候宕机（shutdown）。例如在线考试系统，50人考试没问题，100人考试也没问题，但如果全校10 000人考试就可能宕机。