算法之神奇的斐波那契数列(Fibonacci sequence)

14天阅读挑战赛
努力是为了不平庸~
数据结构+算法=程序。 数据结构是程序的骨架，算法是程序的灵魂。

斐波那契数列的定义

斐波那契数列可以用兔子数列来理解。
首先假设第一个月有一对初生兔子，第二个月进入成熟期，第三个月开始生育兔子，并兔子永不死去，它们按照下列的方式繁衍：

1. 第一个月，1号兔子没有繁殖能力，还是一对。
2. 第二个月，1号兔子进入成熟期，没有繁殖，还是一对。
3. 第三个月，1号兔子生一对兔子（2号），这个月有（1+1=）2对兔子。
4. 第四个月，1号兔子生一对兔子（3号），2号兔子进入成熟器，这个月有（1+2=）3对兔子。
5. 第五个月，1号兔子生一对兔子（4号），2号兔子生一对兔子（5号），3号兔子进入成熟器，这个月有（3+2=）5对兔子。
6. 第六个月，1号兔子生一对兔子（6号），2号兔子生一对兔子（7号），3号兔子进生一对兔子（8号），4号、5号 兔子进入成熟器，这个月有（3+5=）8对兔子。
   …

依此类推。
可以明显的看到：当月的兔子数=上个月兔子数+上上个月兔子数。

所以，不难看出，斐波那契数列是这样的：
$$1,1,2,3,5,8,13,21,34,55,...$$

递归表达就是：
F ( n ) = { 1 , n = 1 1 , n = 2 F ( n − 1 ) + F ( n − 2 ) , n > 2 F(n)=\left\{

\right. F(n)=⎩ ⎨ ⎧​1,n1,nF(n−1)+F(n−2),n​=1=2>2​

Fibonacci算法设计

递归算法

设计递归算法实现斐波那契数列。

int Fibonacci(int n)
{
	if (n <= 0)
		return 0;
	if (n == 1 || n == 2)
		return 1;

	return Fibonacci(n - 1) + Fibonacci(n - 2);
}
1
2
3
4
5
6
7
8
9

测试代码：

#include 
#include 

int Fibonacci(int n)
{
	if (n <= 0)
		return 0;
	if (n == 1 || n == 2)
		return 1;

	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main(int argc,char **argv)
{
	int n = 6;
	if (argc > 1)
		n = atoi(argv[1]);

	printf("n= %d, Fibonacci: %d\n", n, Fibonacci(n));

	return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

执行结果：

$ ./Fibonacci
n= 6, Fibonacci: 8

$ ./Fibonacci 10
n= 10, Fibonacci: 55
1
2
3
4
5

算法时间复杂度

用$T(n)$表示Fibonacci(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。它们的关系为：
F ( n ) = { 1 , n = 1        T ( n ) = 1 1 , n = 2        T ( n ) = 1 F ( n − 1 ) + F ( n − 2 ) , n > 2        T ( n ) = T ( n − 1 ) + T ( n − 2 ) + 1 F(n)=\left\{

\right. F(n)=⎩ ⎨ ⎧​1,n1,nF(n−1)+F(n−2),n​=1      T(n)=1=2      T(n)=1>2      T(n)=T(n−1)+T(n−2)+1​
由此可知：$T(n)\ge F(n)$。
斐波那契数列的通项公式：

这里可以看到，时间复杂度属于爆炸增量函数。

算法改进1

int Fibonacci_1(int n) {
	int *F = new int[n + 1];//定义一个长度为n+1的数组，空间尚未使用
	F[1] = 1;
	F[2] = 1;
	for (int i = 3; i <= n; i++)
		F[i] = F[i - 1] + F[i - 2];
	return F[n];
}
1
2
3
4
5
6
7
8

这时，时间复杂度$O(n)$，空间复杂度$O(n)$。时间复杂度降下来了，算法效率有了重大突破，但是空间复杂度上去了。

算法优化2

上述算法优化使用了一个辅助数组记录中间结果，空间复杂度$O(n)$；其实只需要第n个斐波那契数，中间结果只是为了下一次使用，不需要保存。所以，可以采用迭代法进行算法优化：

int Fibonacci_2(int n){
    if(n==1||n==2)   
         return 1;
    int f1=1; 
    int fs2=1;
    for(int i=3;i<=n;i++){
         int tmp=f1+f2;
         f1=f2;
         f2=tmp;
    }
    return f2;
}
1
2
3
4
5
6
7
8
9
10
11
12

使用三个辅助变量进行迭代，时间复杂度$O(n)$，但是空间复杂度降为$O(1)$。

斐波那契数列与黄金分割数

随着n趋向无穷大，斐波那契数列中前一项与后一项的比值越来越逼近黄金分割数0.618。

$\frac{1}{1}=1，\frac{1}{2}=0.5，\frac{2}{3}=0.666，\frac{3}{5}=0.625，......，\frac{463681}{75025}=0.6180339886$。

总结

1. 斐波那契数列起源于兔子数列，数学源于生活。斐波那契数列与黄金分割数有着千丝万缕的关系。
2. 算法难学的一个原因是算法本身具有一定的复杂性，需要持之以恒的学习和拓展自己的思维