文章来自：http://blog.csdn.net/mshantingting/article/details/22689573
斐波那契数列（又名黄金分割数列）在数学上的定义如下：
许多人包括作者自己在看到这道题的时候，第一个想法就是使用函数递归来实现程序。
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 long long Fibonacci(int n) 5 { 6 long long f; 7 if(n==1||n==2) 8 f=1; 9 else 10 f=Fibonacci(n-1)+Fibonacci(n-2); 11 return f; 12 } 13 14 int main() 15 { 16 int n; 17 long long f; 18 scanf("%d",&n); 19 f=Fibonacci(n); 20 printf("%lld",f); 21 return 0; 22 }
这种方法虽然便于理解，但是我们考虑一下，它的时间复杂度可是以n的指数形式增长 的。当n=10，n=20或者n=30时，程序能够在我们可以接受的运行时间内反馈给我们运行结果。但是，我们如果试一下n=50的情况，运行时间已经远 远超过了我们能够等待的时间（大概一分半钟）。原因很简单，例如我们要求f(8)，就要知道f(7)和f(6)，而求f(7)我们要求得f(6)和 f(5)，因此我们重复求了很多项，浪费很多时间。
改进的做法也是很简单的，我们可以从小往大算，循环n-1次，根据f(0)和f(1)求出f(2)，再根据f(1)和f(2)求出f(3)，以此类推。代码实现如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 long long Fibonacci(int n) 5 { 6 int result[2]={0,1},i; 7 if(n<2) 8 return result[n]; 9 long long One = 1,Two = 0,Current_N = 0; 10 for(i=2;i<=n;i++) 11 { 12 Current_N = One + Two; 13 Two = One; 14 One = Current_N; 15 } 16 return Current_N; 17 } 18 19 int main() 20 { 21 long long n,f; 22 scanf("%d",&n); 23 f=Fibonacci(n); 24 printf("%lld",f); 25 return 0; 26 }
此方法时间复杂度是O(n)。这种方法提高了时间效率，被很多人采用。那还有没有更快的方法呢？根据《剑指offer》一书中作者提到的方法，书中介绍了一个数学公式如下：
我进行了如下验算：
因此f(n)就等于等式右边的二阶方阵的(n-1)次方所求得方阵的第一行第一列个数的值。代码实现如下：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstdlib> 4 5 using namespace std; 6 7 //求矩阵a的n次幂的函数 8 long long * Matrix(long long *a,int n) 9 { 10 long long *result = (long long *)malloc(sizeof(long long)*4); 11 long long *finnal = (long long *)malloc(sizeof(long long)*4); 12 //如果n等于1的话，则直接返回矩阵a，毕竟，一次幂就不必求了。 13 if(n==1) 14 return a; 15 //先求出矩阵的n/2次幂 16 long long *CurMatrix = Matrix(a,n/2); 17 //两个矩阵的n/2次幂相乘得到矩阵的n次幂 18 result[0] = CurMatrix[0]*CurMatrix[0]+CurMatrix[1]*CurMatrix[2]; 19 result[1] = CurMatrix[0]*CurMatrix[1]+CurMatrix[1]*CurMatrix[3]; 20 result[2] = CurMatrix[2]*CurMatrix[0]+CurMatrix[3]*CurMatrix[2]; 21 result[3] = CurMatrix[2]*CurMatrix[1]+CurMatrix[3]*CurMatrix[3]; 22 //如果n为奇数的话，则(n/2)会少一位，补回来。a = a^(n/2)*a^(n/2) * a; 23 if(n%2==1) 24 { 25 finnal[0] = result[0]*a[0]+result[1]*a[2]; 26 finnal[1] = result[0]*a[1]+result[1]*a[3]; 27 finnal[2] = result[2]*a[0]+result[3]*a[2]; 28 finnal[3] = result[2]*a[1]+result[3]*a[3]; 29 } 30 //如果n为偶数的话，n/2还是n/2 31 else 32 finnal = result; 33 return finnal; 34 } 35 36 int main(void) 37 { 38 long long a[4]; 39 int n; 40 cin>>n; 41 //矩阵按一位数组设置,t[0]即为febonacci(n) 42 a[0] = 1; 43 a[1] = 1; 44 a[2] = 1; 45 a[3] = 0; 46 long long *t = Matrix(a,n-1); 47 cout<<t[0]<<endl; 48 return 0; 49 }
显而易见，该算法的复杂度为O(logn)。
以上三种方法的时间效率一次增高，虽然人们普遍对第三种算法中的公式比较陌生，但经过一番细细地琢磨以后，便能体会到它的独到之处。
（声明：文章版权归原作者所有，转载请注明出处：http://blog.csdn.net/mshantingting/article/details/22689573）
![[最全算法总结]我是如何将递归算法的复杂度优化到O(1)的](https://ucc.alicdn.com/pic/developer-ecology/djggblw76kgva_b042975a18ee4c269c783f8d41cf957f.png?x-oss-process=image/resize,h_160,m_lfit)
