這才是面試官想聽(tīng)的：詳解「遞歸」正確的打開(kāi)方式

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

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

空間復(fù)雜度分析

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

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

但是在公司里大家常用的，也是面試時(shí)問(wèn)的指的是
Auxiliary space complexity：

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

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

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

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

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

優(yōu)化算法

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

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

比如一個(gè) 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);">記筆記。

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

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

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

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

那有了這個(gè) cheat sheet，我們就可以從前到后得到結(jié)果了，這樣每一個(gè)點(diǎn)就只算了一遍，用一個(gè) for loop 就可以寫出來(lái)，代碼也非常簡(jiǎn)單。

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

這個(gè)速度就是 100% 了～

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

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

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

那我們可以用一個(gè)長(zhǎng)度為 2 的數(shù)組來(lái)計(jì)算，或者就用 2 個(gè)變量。

更新代碼：

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)，時(shí)間復(fù)雜度和用數(shù)組記錄一樣都是 O(n).

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

那我們比較一下 Recursion 和 DP：

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

也就是 Recursion + Cache = DP

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

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

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

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

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

披著羊皮的狼

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

答：真的會(huì)。

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

比如很有名的爬樓梯問(wèn)題：

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

這個(gè)題這么想：

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

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

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

遞歸的寫法時(shí)間復(fù)雜度太高，所以又寫了一個(gè) for loop 的版本

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

然后還寫了個(gè) 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 尾遞歸：就是遞歸的這句話是整個(gè)方法的最后一句話。

那這個(gè)有什么特別之處呢？

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

那為什么呢？

因?yàn)榛貋?lái)的時(shí)候不需要 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])

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

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