斐波拉契数列相信大家都不陌生，是这样一个数列：0,1,1,2,3,5,7......其递推公式为f(n)=f(n-1)+f(n-2),(n>=2)。由于递推公式的存在，于是大家就立即想到使用递归来写，一股脑码下如下代码：
int fi(int n){ if(n==0){ return 0; }else if(n==1){ return 1; }else{ return fi(n-1)+f(n-2); } }这段代码一看还是非常简洁易懂的，但是这样的代码只有在当n值比较小的时候才是可行的，当n比较大的时候，由于时间复杂度太大，这个算法是不可行的，递归式的算法时间复杂度为O(2^n)。例如当n达到50的时候运行时间就已经达到了秒数级了。那么有没有什么高效一点的算法呢。
1、使用循环代替递归
int fi(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { int f0 = 0; int f1 = 1; int f2 = 0; for (int i = 2; i <= n; i++) { f2 = f0 + f1; f0 = f1; f1 = f2; } return f2; } }循环算法的时间复杂度为O(n)。
2、使用动态规划求解
int fi(int n){ int *a=new int[n]; for(int i=0) a[i]=0; a[1]=0; for(int i=2;i<n;i++){ a[i]=a[i-1]+a[i-2]; } return a[n-1]; }动态规划算法的时间复杂度也是O(n)。
3、可以使用矩阵相乘法，此时时间复杂度可以降为O(lgn)
首先根据斐波拉契数列的递推公式f(n)=f(n-1)+f(n-2)，可得矩阵
因此转化为求矩阵的n次幂。
//使用矩阵计算斐波拉契数列 //首先定义两个矩阵相乘函数 vector<vector<double>> martix(vector<vector<double>> a, vector<vector<double>>b) { vector<vector<double>> c = { {0,0},{0,0} }; for (int i = 0; i < 2;i++) { for (int j = 0; j < 2;j++) { c[i][j]= a[i][0] * b[0][j] + a[i][1] * b[1][j]; } } return c; } //使用矩阵相乘来算斐波拉契数列,从0开始，输入n,输出第n项 double fi(int n) { if (n == 0) return 0; if (n == 1) return 1; vector<vector<double>> base = { {1,1},{1,0} }; vector<vector<double>> ans = { {1,0},{0,1} }; n--; while (n) { if (n & 1) ans = martix(ans, base);//n为奇数时进入，用于计算奇数次幂和最后的结果 base = martix(base, base); n=(n >> 1); } return ans[0][0]; }
