斐波那契數(shù)列：
f(n)=f(n-1)+f(n-2)(n>2) f(0)=1;f(1)=1;
即有名的兔子繁衍問題
在本篇文章我將會(huì)給出三種解法

方法一： 遞歸

static int f1(int i) {
        if (i == 1 || i == 2)
            return 1;
        else
            return f1(i - 1) + f1(i - 2);
    }

1.時(shí)間復(fù)雜度 O(2^n)
首先可以根據(jù)函數(shù)遞歸執(zhí)行順序畫出下圖的二叉樹結(jié)構(gòu)（假設(shè)求第五個(gè)斐波那契數(shù)）

image.png

2.空間復(fù)雜度 O(1)

image.png

①-③：調(diào)用Fib(5),首先需調(diào)用Fib(4),Fib(4)要先調(diào)用Fib(3)溯壶，逐步調(diào)用直至返回Fib(2)的值1，F(xiàn)ib執(zhí)行結(jié)束甫男，所創(chuàng)建空間銷毀且改。此時(shí)Fib(5)、Fib(4)板驳、Fib(3)均未調(diào)用結(jié)束钾虐，程序共占用4個(gè)函數(shù)棧幀空間。

④-⑨：Fib(2)執(zhí)行結(jié)束笋庄，接下來調(diào)用Fib(1)效扫，創(chuàng)建一個(gè)函數(shù)棧幀空間倔监，調(diào)用結(jié)束返回1后，該空間銷毀菌仁，此時(shí)可得到Fib(3)=2浩习，通過第⑦步返回Fib(3)的值，第⑧步同樣創(chuàng)建空間再次調(diào)用Fib(2)济丘，調(diào)用結(jié)束銷毀空間谱秽，此時(shí)可得到Fib(4)=3，通過第⑨步返回Fib(4)的值摹迷，此過程最大占用4個(gè)函數(shù)棧幀空間疟赊。

⑩-···：最后和上面一樣，調(diào)用Fib(3)峡碉，將返回值傳給Fib(5)的模塊近哟，最終得到Fib(5)=5。

整個(gè)程序執(zhí)行過程中鲫寄，最多占用4個(gè)函數(shù)棧幀空間的大小吉执，設(shè)一個(gè)函數(shù)棧幀空間為C
因此可得知當(dāng)n=5時(shí)，該程序空間復(fù)雜度為O(4C)=>O(1)
當(dāng)求第n個(gè)斐波那契數(shù)時(shí)地来，程序空間復(fù)雜度為O(n-1)C (n是常數(shù))=>O(1)

方法二：循環(huán)

image.png

static int f2(int n) {
        int count = 1;
        int Fn_1 = 1;
        int Fn_2 = 1;
        while (n > 2) {
            Fn_2 = Fn_1;
            Fn_1 = count;
            count = Fn_1 + Fn_2;
            n--;
        }
        return count;
    }

1.時(shí)間復(fù)雜度 O(n)
程序中循環(huán)了n-2次戳玫，時(shí)間復(fù)雜度為O(n-2),保留最高階時(shí)間復(fù)雜度為O(n)

2.空間復(fù)雜度 O(1)
該程序中創(chuàng)建了3個(gè)變量，即創(chuàng)建了3個(gè)內(nèi)存空間未斑，空間復(fù)雜度為O(3)即O(1)

方法三：尾遞歸

image.png

int fib(int n) {
    int pre = 1;
    int ppre = 0;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        ret = pre + ppre;
        ppre = pre;
        pre = ret;
    }
    return ret;
}

1.時(shí)間復(fù)雜度 O(n)
根據(jù)尾遞歸的圖解可看出咕宿，計(jì)算Fib(1,1,5)時(shí)，函數(shù)調(diào)用了3次蜡秽，那么計(jì)算Fib(1,1,n)時(shí)府阀，函數(shù)將調(diào)用n-2次，
由此可得時(shí)間復(fù)雜度為O(n-2)即O(n)载城。

2.空間復(fù)雜度 O(n)

image.png

尾遞歸的方法，需開辟n-2個(gè)空間费就，空間復(fù)雜度為O(n-2)即O(n)诉瓦。

方法四：記憶化搜索(Memory Search)

記憶化搜索，即在搜索過程中記錄下搜索結(jié)果力细，在下次的搜索過程中如果算出過這個(gè)結(jié)果睬澡，就可以直接拿來用。
時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(n)

/**
     * memory search
     * 遞歸
     * 時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(n)
     * @param n
     * @return
     */
    public static int fib_ms(int n){
        if(n==0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int[] memory = new int[n+1];
        if(memory[n] != 0){
            return memory[n];
        }
        memory[n] = fib_ms(n-1) + fib_ms(n-2);
        return memory[n];
    }

方法五：動(dòng)態(tài)規(guī)劃(Dynamic Programming)

非遞歸眠蚂，減少了系統(tǒng)棧的建立煞聪，比記憶化搜索還快，將原問題拆解成若干子問題逝慧，同時(shí)保存子問題的答案昔脯，使得每個(gè)子問題只求解一次啄糙，最終獲得原問題的答案
時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(1)

/**
     * dynamic programming
     * 非遞歸，減少了系統(tǒng)棧的建立云稚，比記憶化搜索還快
     * 將原問題拆解成若干子問題隧饼，同時(shí)保存子問題的答案，使得每個(gè)子問題只求解一次静陈，最終獲得原問題的答案
     * 時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(1)
     * @param n
     * @return
     */
    public static int fib_dp(int n){
        if(n==0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int pre = 1;
        int ppre = 1;
        int result = 0;
        for(int i=3; i<=n; i++){
            result = pre + ppre;
            ppre = pre;
            pre = result;
        }
        return result;
    }

————————————————
原文鏈接：https://blog.csdn.net/lxf_style/java/article/details/80458519