最后一層節點的個數：2^n

空間復雜度分析

一般書上寫的空間復雜度是指：

演算法運行期間所需占用的所有記憶體空間

但是在公司里大家常用的，也是面試時問的指的是
Auxiliary space complexity：

運行演算法時所需占用的額外空間，

舉例說明區別：比如結果讓你輸出一個長度為 n 的陣列，那么這 O(n) 的空間是不算在演算法的空間復雜度里的，因為這個空間是跑不掉的，不是取決于你的演算法的，

那空間復雜度怎么分析呢？

我們剛剛說到了馮諾伊曼體系，從圖中也很容易看出來，是最左邊這條路線占用 stack 的空間最多，一直不斷的壓堆疊，也就是從 5 到 4 到 3 到 2 一直壓到 1，才到 base case 回傳，每個節點占用的空間復雜度是 O(1)，所以加起來總的空間復雜度就是 O(n).

優化演算法

那我們就想了，為什么這么一個簡簡單單的運算竟然要指數級的時間復雜度？到底是為什么讓時間如此之大，

那也不難看出來，在這棵 Recursion Tree 里，有太多的重復計算了，

比如一個 F(2) 在這里都被計算了 3 次，F(3) 被計算了 2 次，每次還都要再重新算，這不就是狗熊掰棒子嗎，真的是一把辛酸淚，

那找到了原因之后，為了解決這種重復計算，計算機采用的方法其實和我們人類是一樣的：記筆記，

對很多職業來說，比如醫生、律師、以及我們工程師，為什么越老經驗值錢？因為我們見得多積累的多，下次再遇到類似的問題時，能夠很快的給出解決方案，哪怕一時解決不了，也避免了一些盲目的試錯，我們會站在過去的高度不斷進步，而不是每次都從零開始，

回到優化演算法上來，那計算機如何記筆記呢？

我們要想求 F(n)，無非也就是要
記錄 F(0) ~ F(n-1) 的值，
那選取一個合適的資料結構來存盤就好了，

那這里很明顯了，用一個陣列來存：

那有了這個 cheat sheet，我們就可以從前到后得到結果了，這樣每一個點就只算了一遍，用一個 for loop 就可以寫出來，代碼也非常簡單，

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N== 1) {
            return 1;
        }
        int[] notes = new int[N+1];
        notes[0] = 0;
        notes[1] = 1;
        for(int i = 2; i <= N; i++) {
            notes[i] = notes[i-1] + notes[i-2];
        }
        return notes[N];
    }
}

這個速度就是 100% 了～

但是我們可以看到，空間應該還有優化的余地，

那仔細想想，其實我們記筆記的時候需要記錄這么多嗎？需要從幼兒園到小學到初中到高中的筆記都留著嗎？

那其實每項的計算只取決于它前面的兩項，所以只用保留這兩個就好了，

那我們可以用一個長度為 2 的陣列來計算，或者就用 2 個變數，

更新代碼：

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

這樣我們就把空間復雜度優化到了 O(1)，時間復雜度和用陣列記錄一樣都是 O(n).

這種方法其實就是動態規劃 Dynamic Programming，寫出來的代碼非常簡單，

那我們比較一下 Recursion 和 DP：

Recursion 是從大到小，層層分解，直到 base case 分解不了了再組合回傳上去；
DP 是從小到大，記好筆記，不斷進步，
也就是 Recursion + Cache = DP

如何記錄這個筆記，如何高效的記筆記，這是 DP 的難點，

有人說 DP 是拿空間換時間，但我不這么認為，這道題就是一個很好的例證，

在用遞回解題時，我們可以看到，空間是 O(n) 在堆疊上的，但是用 DP 我們可以把空間優化到 O(1)，DP 可以做到時間空間的雙重優化，

其實呢，斐波那契數列在現實生活中也有很多應用，

比如在我司以及很多大公司里，每個任務要給分值，1分表示大概需要花1天時間完成，然后分值只有>1，2，3，5，8這5種，（如果有大于8分的任務，就需要把它 break down 成8分以內的，以便大家在>兩周內能完成，）
因為任務是永遠做不完的而每個人的時間是有限的，所以每次小組會開會，挑出最重要的任務讓大家來>做，然后每個人根據自己的 available 的天數去 pick up 相應的任務，

那有同學可能會想，這題這么簡單，這都 2020 年了，面試還會考么？

答：真的會，

只是不能以這么直白的方式給你了，

比如很有名的爬樓梯問題：

一個 N 階的樓梯，每次能走一層或者兩層，問一共有多少種走法，

這個題這么想：

站在當前位置，只能是從前一層，或者前兩層上來的，所以 f(n) = f(n-1) + f(n-2).

這題是我當年面試時真實被問的，那時我還在寫 python，為了炫技，還用了lambda function:

f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)

遞回的寫法時間復雜度太高，所以又寫了一個 for loop 的版本

def fib(n)
  a, b = 1, 1
  for i in range(n-1):
    a, b = b, a+b
  return a 

然后還寫了個 caching 的方法:

def cache(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper
@cache
def fibR(n):
    if n==1 or n==2: return 1
    return fibR(n-1) + fibR(n-2)

還順便和面試官聊了下 tail recursion:

tail recursion 尾遞回：就是遞回的這句話是整個方法的最后一句話，

那這個有什么特別之處呢？

尾遞回的特點就是我們可以很容易的把它轉成 iterative 的寫法，當然有些智能的編譯器會自動幫我們做了（不是說顯性的轉化，而是在運行時按照 iterative 的方式去運行，實際消耗的空間是O(1)）

那為什么呢？

因為回來的時候不需要 backtrack，遞回這里就是最后一步了，不需要再往上一層返值，

def fib(n, a=0, b=1):
    if n==0: return a
      if n==1: return b
    return fib(n-1, b, a+b)

最終，拿出了我的殺手锏：lambda and reduce

fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])

看到面試官滿意的表情后，就開始繼續深入的聊了...

所以說，不要以為它簡單，同一道題可以用七八種方法來解，分析好每個方法的優缺點，引申到你可以引申的地方，展示自己扎實的基本功，這場面試其實就是你 show off 的機會，這樣才能騙過面試官啊～lol

這就是本文的所有內容了，不知道大家看完感受如何？留言告訴我你的感受吧～

點擊在看，鼓勵下我啊！

瞎寫評論，顯得我很紅啊！

轉發轉發轉發，愛她，就送給她！

還想跟我看更多資料結構和演算法題的小伙伴們，記得關注我，我是程式零世界，演算法就這么回事，

作者：小齊本齊