F(n)=F(n-1)+F(n-2)

1.迭代实现,O(2的N次方)

1 /** 2      * 斐波那契 迭代实现 3      * @param n 4      * @return 5      */ 6     public int Fabonacci_1(int n){ 7         if(n<0)return 0; 8         if(n==1||n==2) return 1; 9         return Fabonacci_1(n-1)+Fabonacci_1(n-2);10     }

 

2.递归实现,O(N)

1 /** 2      * 斐波那契 递归实现 3      * @param n 4      * @return 5      */ 6     public int Fabonacci_2(int n){ 7         if(n<0)return 0; 8         if(n==1||n==2) return 1; 9         int res = 1,pre=1,temp=0;10         for(int i=3;i<=n;i++){11             temp = res;12             res = res+pre;13             pre = temp;14         }15         return res;16     }

3.使用二阶矩阵实现,O(logN)

1 /** 2      * 斐波那契 二阶矩阵实现 3      * @param n 4      * @return 5      */ 6     public int Fabonacci_3(int n){ 7         if(n<0)return 0; 8         if(n==1||n==2) return 1; 9         int[][] base={
   {1,1},{1,0}};10         int[][] res = matrixPower(base, n-2);11         return res[0][0]+res[1][0];12     }13     14     //使用二阶矩阵求 斐波那契15     16     public int[][] matrixPower(int[][] m,int p){17         int[][] res = new int[m.length][m[0].length];18         //设置res为单位矩阵19         for(int i=0;i
     
      >=1){25             if((p&1)!=0){26                 muliMatrix(res, temp);27             }28             muliMatrix(temp, temp);29             30         }31         return res;32     }33     34     35     //2个矩阵相乘36     public int[][] muliMatrix(int[][] m1,int[][] m2){37         int[][] res = new int[m1.length][m2[0].length];38         for(int i=0;i