全國(guó)咨詢(xún)/投訴熱線:400-618-4000

首頁(yè)技術(shù)文章正文

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

更新時(shí)間:2022-11-16 來(lái)源:黑馬程序員 瀏覽量:

  介紹

   斐波那契數(shù)列(Fibonacci sequence),又稱(chēng)黃金分割數(shù)列,因數(shù)學(xué)家萊昂納多·斐波那契(Leonardo Fibonacci)以兔子繁殖為例子而引入,故又稱(chēng)為“兔子數(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é)雜志,用于專(zhuān)門(mén)刊載這方面的研究成果。

  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)

1668571139691_2.jpg

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

1668571153953_3.jpg

  方案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:使用線性方程;

1668570998095_1.jpg

  方案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)

分享到:
在線咨詢(xún) 我要報(bào)名
和我們?cè)诰€交談!