這才是面試官想聽的：詳解「遞歸」正確的打開方式

最后一層節(jié)點(diǎn)的個數(shù)：2^n

沒看懂？別慌，去 B 站/油管看我的視頻講解哦，搜「田小齊」就好了。

空間復(fù)雜度分析

一般書上寫的空間復(fù)雜度是指：

算法運(yùn)行期間所需占用的所有內(nèi)存空間

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

運(yùn)行算法時所需占用的額外空間。

舉例說明區(qū)別：比如結(jié)果讓你輸出一個長度為 n 的數(shù)組，那么這 O(n) 的空間是不算在算法的空間復(fù)雜度里的，因?yàn)檫@個空間是跑不掉的，不是取決于你的算法的。

那空間復(fù)雜度怎么分析呢？

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

我在上面的視頻里也提到了，不懂的同學(xué)往上翻看視頻哦～

優(yōu)化算法

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

那也不難看出來，在這棵 Recursion Tree 里，有太多的重復(fù)計(jì)算了。

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

那找到了原因之后，為了解決這種重復(fù)計(jì)算，計(jì)算機(jī)采用的方法其實(shí)和我們?nèi)祟愂且粯拥模?code style="font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(239, 112, 96);">記筆記。

對很多職業(yè)來說，比如醫(yī)生、律師、以及我們工程師，為什么越老經(jīng)驗(yàn)值錢？因?yàn)槲覀円姷枚喾e累的多，下次再遇到類似的問題時，能夠很快的給出解決方案，哪怕一時解決不了，也避免了一些盲目的試錯，我們會站在過去的高度不斷進(jìn)步，而不是每次都從零開始。

回到優(yōu)化算法上來，那計(jì)算機(jī)如何記筆記呢？

我們要想求 F(n)，無非也就是要
記錄 F(0) ~ F(n-1) 的值，
那選取一個合適的數(shù)據(jù)結(jié)構(gòu)來存儲就好了。

那這里很明顯了，可以用之前講過的 HashMap （沒看過的點(diǎn)進(jìn)去看哦）或者用一個數(shù)組來存：

那有了這個 cheat sheet，我們就可以從前到后得到結(jié)果了，這樣每一個點(diǎn)就只算了一遍，用一個 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% 了～

但是我們可以看到，空間應(yīng)該還有優(yōu)化的余地。

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

那其實(shí)每項(xiàng)的計(jì)算只取決于它前面的兩項(xiàng)，所以只用保留這兩個就好了。

那我們可以用一個長度為 2 的數(shù)組來計(jì)算，或者就用 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;
    }
}

這樣我們就把空間復(fù)雜度優(yōu)化到了 O(1)，時間復(fù)雜度和用數(shù)組記錄一樣都是 O(n).

這種方法其實(shí)就是動態(tài)規(guī)劃 Dynamic Programming，寫出來的代碼非常簡單。

那我們比較一下 Recursion 和 DP：

Recursion 是從大到小，層層分解，直到 base case 分解不了了再組合返回上去；
DP 是從小到大，記好筆記，不斷進(jìn)步。

也就是 Recursion + Cache = DP

如何記錄這個筆記，如何高效的記筆記，這是 DP 的難點(diǎn)。

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

在用遞歸解題時，我們可以看到，空間是 O(n) 在棧上的，但是用 DP 我們可以把空間優(yōu)化到 O(1)，DP 可以做到時間空間的雙重優(yōu)化。

其實(shí)呢，斐波那契數(shù)列在現(xiàn)實(shí)生活中也有很多應(yīng)用。

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

披著羊皮的狼

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

答：真的會。

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

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

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

這個題這么想：

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

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

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

遞歸的寫法時間復(fù)雜度太高，所以又寫了一個 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 尾遞歸：就是遞歸的這句話是整個方法的最后一句話。

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

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

那為什么呢？

因?yàn)榛貋淼臅r候不需要 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])

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

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