斐波那契数列

题目 一：求斐波那契数列的第n项。
写一个函数， 输入n, 求斐波那契 (Fibonacci) 数列的第n项。 斐波那契数列的定义如下：

解法一：递归 O(2^N)

public static long fibonacci(int n){
    if (n<=0){
        return 0;
    }
    if (n==1){
        return 1;
    }
    return fibonacci(n-1)+fibonacci(n-2);
}

这个很好理解，看上去也很清晰，直接套公式即可，但是效率上存在大量重复劳动。见图：

在这棵树中有很多节点是重复的， 而且重复的节点数会随着n的增大而急剧增加， 这意味着计算晕会随着n的增大而急剧增大。

解法二：使用循环 O(n)

public static long fibonacci(int n) {
    int[] result = {0, 1};
    if (n > 0 && n < 2) {
        return result[n];
    }
    long pre = 0;
    long next = 1;
    long cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = pre + next;

        pre = next;
        next = cur;
    }
    return cur;
}

这个代码看起来也很容易理解，这个版本相比较递归版本的优化在于：

把已经得到的数列中间项保存起来，在下次需要计算的时候我们先杳找一下，如果前面已经计算过就不用再重复计算了。

解法三：时间复杂度为 O(logn) 该解法涉及到数学知识：

代码如下：

int[][] matrix=new int[2][2];

 private int[][] muliMatrix(int[][] m1, int[][] m2){
     int[][] res0=new int[2][2];
     for(int i=0; i<2; i++){
         for(int j=0; j<2; j++){
             res0[i][j]=0;
             for(int k=0; k<2; k++){
                 res0[i][j] += m1[i][k]*m2[k][j];
             }
         }
     }
     return res0;
 }

 private int[][] matrixPower(int[][] mat, int p){
     int[][] tmp=mat;
     int[][] res1=new int[2][2];
     for(int i=0; i<2; i++){
         res1[i][i]=1;
     }
     res1[0][1]=0;
     res1[1][0]=0;
     for( ; p != 0; p >>= 1){
         if((p&1)!=0){
             res1 = muliMatrix(res1,tmp);
         }
         tmp = muliMatrix(tmp,tmp);
     }
     return res1;
 }

private int fibonacci(int n) {
     if(n<1) {
         return 0;
     }
     if(n==1 || n==2) {
         return 1;
     }
     int[][] base = {{1,1},{1,0}};

     int[][] res= matrixPower(base, n-2);

     int result= res[0][0] + res[1][0];
     return result;
 }

其实我也还没搞明白，后面再回过头来看看。这里推荐一个辅助文章：点我跳转CSDN