探秘斐波拉契數(shù)列!

　　介紹

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

　　java中如何編碼實(shí)現(xiàn)斐波那契數(shù)列

　　方案1：遞歸

　　 根據(jù)斐波那契數(shù)列的數(shù)學(xué)表示方式：*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);
}

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

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

　　空間復(fù)雜度是0(n)

　　方案2： 基于數(shù)組進(jìn)行優(yōu)化

　　 方案1中很多的代碼，存在重復(fù)調(diào)用.可以考慮使用一個(gè)數(shù)組存放，之前調(diào)用得到的結(jié)果;

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

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

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

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

　　 時(shí)間復(fù)雜度：由于沒(méi)有了重復(fù)的調(diào)用，時(shí)間復(fù)雜度是0(n)。

　　方案3： 將遞歸轉(zhuǎn)化為非遞歸優(yōu)化

　　 定義一個(gè)數(shù)組存放，存放斐波拉契數(shù)列每一項(xiàng)數(shù)據(jù);免去遞歸調(diào)用;

  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];
 }

　　空間復(fù)雜度：額外定義了一個(gè)數(shù)組;空間復(fù)雜度依然是0(n)，但是沒(méi)有遞歸產(chǎn)生的空間。

　　 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度是0(n)

　　方案4： 滾動(dòng)數(shù)組降低空間復(fù)雜度;

　　 對(duì)于斐波拉契數(shù)列，只需要2個(gè)數(shù)組空間即可;

 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];
    }

　　空間復(fù)雜度：額外定義了一個(gè)數(shù)組;但是長(zhǎng)度只有2，所以空間復(fù)雜度0(1);

　　 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度是0(n)

　　方案5：定義2個(gè)變量代替數(shù)組

 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;
 }

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

　　時(shí)間復(fù)雜度：時(shí)間復(fù)雜度是0(n)

　　方案6：使用線性方程;

　　方案7:利用尾遞歸實(shí)現(xiàn)，java可以對(duì)尾遞歸的棧空間優(yōu)化

    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);
    }

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

　　時(shí)間復(fù)雜度：時(shí)間復(fù)雜度是0(n)