斐波那契数列问题是算法学习者必然接触到的问题，作为经典问题，首次接触时一般是作为递归算法的案例教程。
然而递归解决斐波那契，其效率低的令人发指，有人算出其时间复杂度为O(2^n)。指数级时间复杂度。
如果面试的时候面试官问你斐波那契的求解方法，你来一个递归求解，基本上可以说，你已经game over了。
那么有没有更高效的算法呢，本文将一一介绍。
下面是斐波那契的4种解法：
1.递归 时间复杂度O(2^n)
int f(int n){if(n == 1 || n == 2){return 1;}return f(n-1) + f(n-2);}2.循环 时间复杂度O(n) public int f(int n) {// write code hereint f0 = 1;int f1 = 1;int f2 = 0;for(int i = 2; i < n; i++){f2 = f0 + f1;f0 = f1;f1 = f2;}return f2;}
3.矩阵求解 时间复杂度O(logn)
斐波那契的递推公式可以表示成如下矩阵形式，，所以其
所以根据矩阵的分治算法，可以在O(logn)时间内算出结果。
笔试问题：
F(n)F(0) = 1。
long[][] f = new long[][]{{0,1},{1,1}};public int getNthNumber1(int n) {if(n == 0)return 1;if(n == 1)return 1;f = pow(n,f);return (int) f[1][1];}private long[][] pow(int n,long[][] f){if(n == 1)return f;if(n == 2){return fun(f,f);}if( n % 2 == 0){//偶数f = pow(n/2,f);return fun(f, f);}else{return fun(pow(n/2,f),pow(n/2 + 1,f));}}private long[][] fun(long[][] f,long[][] m){long[][] temp = new long[2][2];temp[0][0] = (f[0][0]*m[0][0] + f[0][1]*m[1][0])%1000000007;temp[0][1] = (f[0][0]*m[0][1] + f[0][1]*m[1][1])%1000000007;temp[1][0] = (f[1][0]*m[0][0] + f[1][1]*m[1][0])%1000000007;temp[1][1] = (f[1][0]*m[0][1] + f[1][1]*m[1][1])%1000000007;return temp;}
4.公式求解 时间复杂度O(1)
对，你没看错，斐波那契数列是有求解公式的。其通项公式如下：
所以，任何斐波那契数都可以在O(1)时间内计算出来，但是有一点，因为牵涉到无理数，所以无法保证精度。
具体代码略。
综上，目前代码效率最高也最准确的，是第3种矩阵求解方法，笔试面试时务必掌握。
【完】
版权声明：本文为博主原创文章，未经博主允许不得转载。
经历一种身体下了地狱，眼睛进入天堂，灵魂归入故里。
