Fibonacci数列定义

Fibonacci数列的通常定义

定义一：

由这个定义，可以得到

即：fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2 …………

在另外一些书上，Fibonacci数列是这样定义的

定义二：

同样由这个定义，可以得到

定义二和定义一对 f(0)的初始值不一样，定义一中 f(0) = 0,定义二中f(0) = 1,所以定义一相比定义二要推迟1个单位。但是作为Fabonacci它们基本的核心定义是一样的也即 fib(n) = fib(n-1) + fib(n-2)

下面都是基于【 定义一】 来做的讨论，保持与邓俊辉版本的《数据结构》一致

二分递归

根据定义可以知道，Fibonacci数列实际上是一个递归定义，要计算f(n)就要知道f(n-1)和f(n-2)，要计算f(n-1),就要知道f(n-2)和f(n-3)，以此类推，而边界就是我们一开始给定的 fib(0) = 0, fib(1) = 1,

以fib(6)为例，下面是计算fib(6)展开的递归树

由此可以得到计算Fibonacci数的递归代码：

int fib(int n)
{
	if(2 > n)
       return n;   //递归基
     else
        return fib(n-1) + fib(n-2);    //递推公式
}

这是一个二分递归，从n开始，计算每一个fib(n)时都要分支为两个计算，故 时间复杂度为 O（2^n）。

空间复杂度线性正比于递归深度，故这里的空间复杂度为O（n）

二分递归在计算过程中所出现的递归实例的重复度极高，如上面计算fib6时，fib4重复出现了2次，fib3重复出现了3次，fib2重复出现了5次，这是致使二分递归时间复杂度达到指数级别的真正原因所在。

——更多优化

1.线性递归

线性递归版本一：

Fibonacci数在计算过程中每一步并不是相互独立的，可以用到上一次的计算结果。那么考虑把中间先计算出的结果保存下来，如果当再次需要这个结果的时候先检查是否已经得到了。

int dp[MAXN];   //dp[n] 表示 fib(n)的结果
fill(dp,dp+MAXN,-1); //初始化dp[]的每个值为-1，dp[n] = -1表示F(n)当前还没有被计算过
int fibL(int n)
{
   if(2 > n)
      return n;
      
   if(dp[n] != -1)
   {
   	   return dp[n];
   }
    else
    {
    	dp[n] = fibL(n-1) + fibL(n-2);
        return dp[n];
    }
}
//《算法笔记》上的版本

这个版本的fibonacci数计算也用到了动态规划思想的方法，也即是在计算过程中记录子问题的解，来避免下次遇到相同的子问题时重复计算。这也称之为记忆搜索时间复杂度和空间复杂度均为O(n)

与二分递归的递归计算图相比，下面是Fibonacci数列记忆搜索示意图

​ 图：Fibonacci数列记忆搜索示意图

线性递归版本二：

/*
函数说明：
prev作为辅助变量记录前一项，当前函数返回的是数列当前项
*/
int fibL(int n,int& prev)
{
	//递归基，直接取值
	if(0 == n)
	{
		prev = 1; //相当于初始 fib(-1) = 1 
		return 0;  // fib(0) = 1
	}
	else //深入递归计算
	{
		int prePrev;
		prev = fibL(n-1,prePrev);//递归计算前两项
		return prevPrev + prev;//其和即为正解
	}
}
//邓俊辉《数据结构》上的版本

/*
使用例子：
int prev;
fibL(6,prev);
结果：
fibL(6,prev) = 8;
prev = 5;
*/

这个版本稍微难理解点，主要是借助一个参数引用来一直记录前一项的值 。

和 fib(n) = fib(n-1) + fib(n-2) 相比，这里省略了 fib(n-2),而实际上 fib(n-2)的解答在这里借助了形式参数的机制，通过变量 prevPrev “调阅” 此前的记录直接获得。

时间复杂度和空间复杂度均为O(n)

2.迭代（动态规划的思想）

​ 如果从 1->n 计算 fib（n）

​ fib0 + fib1 = fib2 —> fib1 +fib2 = fib3 —> fib2 + fib3 = fib4 —> fib3 + fib4 = fib5 ………….

由此可以得到迭代版代码：

int fibI(n)
{
	int f = 1,g =0; //相当于fib(-1) = 1,fib(0) = 0;
	while(n--)
	{
		g = g + f;  //g 变为g与f的和,也即g往前进一步
		f = g - f;  // f变为g,也即f往前进一步
	}
	return g;
}

不难得出时间复杂度为O(n)，空间复杂度为 O(1)

3.快速幂矩阵求斐波那契数列

还有一种更快的方法求斐波那契数列的方法，时间复杂度仅为：O( logn )，就是马上要介绍的斐波那契数列的快速幂矩阵方法

首先，由矩阵乘法，我们知道下式成立

也即

由此，可以进一步推导如下通项公式：

由此可以得到 fib(n) = b, fib(n+1) = d,

其中

将普通数的两个数的乘法运算换成两个矩阵的乘法运算，即可实现 fib(n) 的计算。更重要的是。这里仅涉及

2 × 2 的矩阵的计算，每次同样只需要常数的时间，故整体的运行时间也是 O ( logn )

矩阵乘法

示例代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

//  2*2 的矩阵 
struct mat{
    int res[2][2];
    //构造函数 
    mat()
    {
        memset(res,0,sizeof(res));
    }
    //构造函数 
    mat(int a00,int a01,int a10,int a11)
    {
        res[0][0] = a00;
        res[0][1] = a01;
        res[1][0] = a10;
        res[1][1] = a11;
    }
    //深度拷贝方法 
    mat operator=(const mat& a)
    {
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                res[i][j] = a.res[i][j];
        return *this;
    }
};

/*
  矩阵乘法,n维矩阵的相乘 
*/ 
mat multi(mat a,mat b,int n)
{
    mat c;
    for(int i=0;i<n;i++)//行
    {
        for(int j=0;j<n;j++)//列
        {
            for(int k=0;k<n;k++)//枚举个数
            {
                c.res[i][j]=(c.res[i][j]+a.res[i][k]*b.res[k][j]);
            }
        }
    }
    return c;
}

/*
   矩阵乘法快速幂
  ( 0 1 ) ^n
  ( 1 1 )
*/
mat matirix_pow(mat a,int n)
{
    mat pow(1,0,0,1);//单位矩阵，相当于1
    mat p = a;
    while(0 < n)
    {
        if(n&1)
            pow = multi(pow,p,2);    // pow = pow*p
        p = multi(p,p,2);   // p = p*p
        n >>= 1;   //  n = n/2
    }
    return pow;
}

/*
	用快速矩阵乘法求fibonacci数列 
	  fib(n) =  fibMat.res[0][1];
	fib(n+1) =  fibMat.res[1][1];
*/ 
int fib_matrixPow(int n)
{
	mat a(0,1,1,1);
	mat fibMat = matirix_pow(a,n);
	return fibMat.res[0][1];
} 

int main()
{
	cout<<"fib(9) = "<<fib_matrixPow(9)<<endl;
    return 0;
}