介紹

　　 斐波那契數列(Fibonacci sequence)，又稱黃金分割數列，因數學家萊昂納多·斐波那契(Leonardo Fibonacci)以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：*F*(0)=0，*F*(1)=1, *F*(n)=*F*(n - 1)+*F*(n - 2)(*n* ≥ 2，*n* ∈ N*)在現代物理、晶體結構、化學等領域，斐波納契數列都有直接的應用，為此，美國數學會從 1963 年起出版了以《斐波納契數列季刊》為名的一份數學雜志，用于專門刊載這方面的研究成果。

　　java中如何編碼實現斐波那契數列

　　方案1：遞歸

　　 根據斐波那契數列的數學表示方式：*F*(1)=1，*F*(2)=1, *F*(n)=*F*(n - 1)+*F*(n - 2)(*n* ≥ 2，*n* ∈ N*)

　　 很容易就可以得出：

public int fib(int n) {
    if(n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

　　問題：使用以上代碼完成斐波那契數列，時間復雜度是0(n^2),空間復雜度是0(n);

　　 我們以fib(6)為例： 時間復雜度很明顯是0(n^2)

　　空間復雜度是0(n)

　　方案2： 基于數組進行優化

　　 方案1中很多的代碼，存在重復調用.可以考慮使用一個數組存放，之前調用得到的結果;

  public int fib(int n) {
        if(n <= 2) return 1;
        int[] array = new int[n + 1]; //定義數組，存放已經得到結果的數據
        array[1] = array[2] = 1;
        return fib(n,array);
    }

    public int fib(int n,int[] array) {
        if(array[n] == 0) { //判斷數組中是否有元素，如果有，直接返回，沒有，遞歸。
            array[n] = fib(n -1 ,array) + fib(n - 2,array);
        }
        return array[n];
    }

　　問題：使用以上代碼完成斐波那契數列，時間復雜度是0(n),空間復雜度是0(n);

　　 空間復雜度：額外定義了一個數組;空間復雜度依然是0(n)。

　　 時間復雜度：由于沒有了重復的調用，時間復雜度是0(n)。

　　方案3： 將遞歸轉化為非遞歸優化

　　 定義一個數組存放，存放斐波拉契數列每一項數據;免去遞歸調用;

  public int fib(int n) {
        if(n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        for (int i = 3; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
 }

　　空間復雜度：額外定義了一個數組;空間復雜度依然是0(n)，但是沒有遞歸產生的空間。

　　 時間復雜度：時間復雜度是0(n)

　　方案4： 滾動數組降低空間復雜度;

　　 對于斐波拉契數列，只需要2個數組空間即可;

 public int fib(int n) {
        if(n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n ; i++) {
            array[(i - 1) & 1] = array[(i - 1)  & 1] + array[(i - 2) & 1];
        }
        return array[( n - 1)  & 1];
    }

　　空間復雜度：額外定義了一個數組;但是長度只有2，所以空間復雜度0(1);

　　 時間復雜度：時間復雜度是0(n)

　　方案5：定義2個變量代替數組

 public int fab5(int n) {
        if(n <= 2) return 1;
        int n1 = 1;
        int n2 = 1;
        for (int i=3;i<=n;i++) {
            n2 = n1 + n2;
            n1 = n2 - n1;
        }
        return n2;
 }

　　空間復雜度：不需要額外定義數組，只定義2個變量即可，所以空間復雜度0(1);

　　時間復雜度：時間復雜度是0(n)

　　方案6：使用線性方程;

　　方案7:利用尾遞歸實現，java可以對尾遞歸的棧空間優化

    public int fab7(int n) {
       return fab7(n,1,1);
    }

    public int fab7(int n, int n1,int n2) {
        if(n <= 2) {
            return n2;
        }
        return fab7(n - 1,n2,n1+n2);
    }

　　空間復雜度：遞歸的深度為0(n)，但是由于是尾遞歸，優化后的空間復雜度是0(1)

　　時間復雜度：時間復雜度是0(n)