遞歸算法分析

對(duì)很多人來說，遞歸算法的時(shí)間復(fù)雜度是比較難分析的。但如果你有 框架思維，明白所有遞歸算法的本質(zhì)是樹的遍歷，那么分析起來應(yīng)該沒什么難度。

計(jì)算算法的時(shí)間復(fù)雜度，無非就是看這個(gè)算法做了些啥事兒，花了多少時(shí)間。而遞歸算法做的事情就是遍歷一棵遞歸樹，在樹上的每個(gè)節(jié)點(diǎn)所做一些事情罷了。

所以：

遞歸算法的時(shí)間復(fù)雜度 = 遞歸的次數(shù) x 函數(shù)本身的時(shí)間復(fù)雜度

遞歸算法的空間復(fù)雜度 = 遞歸堆棧的深度 + 算法申請(qǐng)的存儲(chǔ)空間

或者再說得直觀一點(diǎn)：

遞歸算法的時(shí)間復(fù)雜度 = 遞歸樹的節(jié)點(diǎn)個(gè)數(shù) x 每個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度

遞歸算法的空間復(fù)雜度 = 遞歸樹的高度 + 算法申請(qǐng)的存儲(chǔ)空間

函數(shù)遞歸的原理是操作系統(tǒng)維護(hù)的函數(shù)堆棧，所以遞歸棧的空間消耗也需要算在空間復(fù)雜度之內(nèi)，這一點(diǎn)不要忘了。

首先說一下動(dòng)態(tài)規(guī)劃算法 ，還是拿前文 動(dòng)態(tài)規(guī)劃核心框架 中講到的湊零錢問題舉例，它的暴力遞歸解法主體如下：

int dp(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = Integer.MAX_VALUE;
    // 時(shí)間 O(K)
    for (int coin : coins) {
        int subProblem = dp(coins, amount - coin);
        if (subProblem == -1) continue;
        res = Math.min(res, subProblem + 1);
    }

    return res == Integer.MAX_VALUE ? -1 : res;
}

當(dāng)amount = 11, coins = [1,2,5]時(shí)，該算法的遞歸樹就長(zhǎng)這樣：

剛才說了這棵樹上的節(jié)點(diǎn)個(gè)數(shù)為O(K^N)，那么每個(gè)節(jié)點(diǎn)消耗的時(shí)間復(fù)雜度是多少呢？其實(shí)就是這個(gè)dp函數(shù)本身的復(fù)雜度。

你看dp函數(shù)里面有個(gè) for 循環(huán)遍歷長(zhǎng)度為K的coins列表，所以函數(shù)本身的復(fù)雜度為O(K)，故該算法總的時(shí)間復(fù)雜度為：

O(K^N) * O(K) = O(K^(N+1))

當(dāng)然，之前也說了，這個(gè)復(fù)雜度只是一個(gè)粗略的上界，并不準(zhǔn)確，真實(shí)的效率肯定會(huì)高一些。

這個(gè)算法的空間復(fù)雜度很容易分析：

dp函數(shù)本身沒有申請(qǐng)數(shù)組之類的，所以算法申請(qǐng)的存儲(chǔ)空間為O(1)；而dp函數(shù)的堆棧深度為遞歸樹的高度O(N)，所以這個(gè)算法的空間復(fù)雜度為O(N)。

暴力遞歸解法的分析結(jié)束，但這個(gè)解法存在重疊子問題，通過備忘錄消除重疊子問題的冗余計(jì)算之后，相當(dāng)于在原來的遞歸樹上進(jìn)行剪枝：

// 備忘錄，空間 O(N)
memo = new int[N];
Arrays.fill(memo, -666);

int dp(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 查備忘錄，防止重復(fù)計(jì)算
    if (memo[amount] != -666)
        return memo[amount];

    int res = Integer.MAX_VALUE;
    // 時(shí)間 O(K)
    for (int coin : coins) {
        int subProblem = dp(coins, amount - coin);
        if (subProblem == -1) continue;
        res = Math.min(res, subProblem + 1);
    }
    // 把計(jì)算結(jié)果存入備忘錄
    memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
    return memo[amount];
}

通過備忘錄剪掉了大量節(jié)點(diǎn)之后，雖然函數(shù)本身的時(shí)間復(fù)雜度依然是O(K)，但大部分遞歸在函數(shù)開頭就立即返回了，根本不會(huì)執(zhí)行到 for 循環(huán)那里，所以可以認(rèn)為遞歸函數(shù)執(zhí)行的次數(shù)（遞歸樹上的節(jié)點(diǎn)）減少了，從而時(shí)間復(fù)雜度下降。

剪枝之后還剩多少節(jié)點(diǎn)呢？根據(jù)備忘錄剪枝的原理，相同「狀態(tài)」不會(huì)被重復(fù)計(jì)算，所以剪枝之后剩下的節(jié)點(diǎn)數(shù)就是「狀態(tài)」的數(shù)量，即memo的大小N。

所以，對(duì)于帶備忘錄的動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度，以下幾種理解方式都是等價(jià)的：

遞歸的次數(shù) x 函數(shù)本身的時(shí)間復(fù)雜度
= 遞歸樹節(jié)點(diǎn)個(gè)數(shù) x 每個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度
= 狀態(tài)個(gè)數(shù) x 計(jì)算每個(gè)狀態(tài)的時(shí)間復(fù)雜度
= 子問題個(gè)數(shù) x 解決每個(gè)子問題的時(shí)間復(fù)雜度
= O(N) * O(K)
= O(NK)

像「狀態(tài)」「子問題」屬于動(dòng)態(tài)規(guī)劃類型問題特有的詞匯，但時(shí)間復(fù)雜度本質(zhì)上還是遞歸次數(shù) x 函數(shù)本身復(fù)雜度，換湯不換藥罷了。反正你愛怎么說怎么說吧，別把自己繞進(jìn)去就行。

備忘錄優(yōu)化解法的空間復(fù)雜度也不難分析：

dp函數(shù)的堆棧深度為「狀態(tài)」的個(gè)數(shù)，依然是O(N)，而算法申請(qǐng)了一個(gè)大小為O(N)的備忘錄memo數(shù)組，所以總的空間復(fù)雜度為O(N) + O(N) = O(N)。

雖然用 Big O 表示法來看，優(yōu)化前后的空間復(fù)雜度相同，不過顯然優(yōu)化解法消耗的空間要更多，所以用備忘錄進(jìn)行剪枝也被稱為「用空間換時(shí)間」。

如果你把自頂向下帶備忘錄的解法進(jìn)一步改寫成自底向上的迭代解法：

int coinChange(int[] coins, int amount) {
    // 空間 O(N)
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);

    dp[0] = 0;
    // 時(shí)間 O(KN)
    for (int i = 0; i < dp.length; i++) {
        for (int coin : coins) {
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

該解法的時(shí)間復(fù)雜度不變，但已經(jīng)不存在遞歸，所以空間復(fù)雜度中不需要考慮堆棧的深度，只需考慮dp數(shù)組的存儲(chǔ)空間，雖然用 Big O 表示法來看，該算法的空間復(fù)雜度依然是O(N)，但該算法的實(shí)際空間消耗是更小的，所以自底向上迭代的動(dòng)態(tài)規(guī)劃是各方面性能最好的。

接下來說一下回溯算法 ，需要你看過前文回溯算法秒殺排列組合問題的 9 種變體，下面我會(huì)以標(biāo)準(zhǔn)的全排列問題和子集問題的解法為例，分析一下其時(shí)間復(fù)雜度。

先看標(biāo)準(zhǔn)全排列問題 （元素?zé)o重不可復(fù)選）的核心函數(shù)backtrack：

// 回溯算法計(jì)算全排列
void backtrack(int[] nums) {
    // 到達(dá)葉子節(jié)點(diǎn)，收集路徑值，時(shí)間 O(N)
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    // 非葉子節(jié)點(diǎn)，遍歷所有子節(jié)點(diǎn)，時(shí)間 O(N)
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            // 剪枝邏輯
            continue;
        }
        // 做選擇
        used[i] = true;
        track.addLast(nums[i]);
        backtrack(nums);
        // 取消選擇
        track.removeLast();
        used[i] = false;
    }
}

當(dāng)nums = [1,2,3]時(shí)，backtrack其實(shí)在遍歷這棵遞歸樹：

假設(shè)輸入的nums數(shù)組長(zhǎng)度為N，那么這個(gè)backtrack函數(shù)遞歸了多少次？backtrack函數(shù)本身的復(fù)雜度是多少？

先看看backtrack函數(shù)本身的時(shí)間復(fù)雜度，即樹中每個(gè)節(jié)點(diǎn)的復(fù)雜度。

對(duì)于非葉子節(jié)點(diǎn)，會(huì)執(zhí)行 for 循環(huán)，復(fù)雜度為O(N)；對(duì)于葉子節(jié)點(diǎn)，不會(huì)執(zhí)行循環(huán)，但將track中的值拷貝到res列表中也需要O(N)的時(shí)間， 所以backtrack函數(shù)本身的時(shí)間復(fù)雜度為O(N) 。

PS：函數(shù)本身（每個(gè)節(jié)點(diǎn)）的時(shí)間復(fù)雜度并不是樹枝的條數(shù)。看代碼，每個(gè)節(jié)點(diǎn)都會(huì)執(zhí)行整個(gè) for 循環(huán)，所以每個(gè)節(jié)點(diǎn)的復(fù)雜度都是O(N)。

再來看看backtrack函數(shù)遞歸了多少次，即這個(gè)排列樹上有多少個(gè)節(jié)點(diǎn)。

第 0 層（根節(jié)點(diǎn)）有P(N, 0) = 1個(gè)節(jié)點(diǎn)。

第 1 層有P(N, 1) = N個(gè)節(jié)點(diǎn)。

第 2 層有P(N, 2) = N x (N - 1)個(gè)節(jié)點(diǎn)。

第 3 層有P(N, 3) = N x (N - 1) x (N - 2)個(gè)節(jié)點(diǎn)。

以此類推，其中P就是我們高中學(xué)過的排列數(shù)函數(shù)。

全排列的回溯樹高度為N，所以節(jié)點(diǎn)總數(shù)為：

P(N, 0) + P(N, 1) + P(N, 2) + ... + P(N, N)

這一堆排列數(shù)累加不好算，粗略估計(jì)一下上界吧，把它們?nèi)紨U(kuò)大成P(N, N) = N!， 那么節(jié)點(diǎn)總數(shù)的上界就是O(N*N!) 。

現(xiàn)在就可以得出算法的總時(shí)間復(fù)雜度：

遞歸的次數(shù) x 函數(shù)本身的時(shí)間復(fù)雜度
= 遞歸樹節(jié)點(diǎn)個(gè)數(shù) x 每個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度
= O(N*N!) * O(N)
= O(N^2 * N!)

當(dāng)然，由于計(jì)算節(jié)點(diǎn)總數(shù)的時(shí)候我們?yōu)榱朔奖阌?jì)算把累加項(xiàng)擴(kuò)大了很多，所以這個(gè)結(jié)果肯定也是偏大的，不過用來描述復(fù)雜度的上界還是可以接受的。

分析下該算法的空間復(fù)雜度：

backtrack函數(shù)的遞歸深度為遞歸樹的高度O(N)，而算法需要存儲(chǔ)所有全排列的結(jié)果，即需要申請(qǐng)的空間為O(N*N!)。 所以總的空間復(fù)雜度為O(N*N!) 。

最后看下標(biāo)準(zhǔn)子集問題 （元素?zé)o重不可復(fù)選）的核心函數(shù)backtrack：

// 回溯算法計(jì)算所有子集（冪集）
void backtrack(int[] nums, int start) {

    // 每個(gè)節(jié)點(diǎn)的值都是一個(gè)子集，O(N)
    res.add(new LinkedList<>(track));

    // 遍歷子節(jié)點(diǎn)，O(N)
    for (int i = start; i < nums.length; i++) {
        // 做選擇
        track.addLast(nums[i]);
        backtrack(nums, i + 1);
        // 撤銷選擇
        track.removeLast();
    }
}

當(dāng)nums = [1,2,3]時(shí)，backtrack其實(shí)在遍歷這棵遞歸樹：

假設(shè)輸入的nums數(shù)組長(zhǎng)度為N，那么這個(gè)backtrack函數(shù)遞歸了多少次？backtrack函數(shù)本身的復(fù)雜度是多少？

先看看backtrack函數(shù)本身的時(shí)間復(fù)雜度，即樹中每個(gè)節(jié)點(diǎn)的復(fù)雜度。

backtrack函數(shù)在前序位置都會(huì)將track列表拷貝到res中，消耗O(N)的時(shí)間，且會(huì)執(zhí)行一個(gè) for 循環(huán)，也消耗O(N)的時(shí)間， 所以backtrack函數(shù)本身的時(shí)間復(fù)雜度為O(N) 。

再來看看backtrack函數(shù)遞歸了多少次，即這個(gè)排列樹上有多少個(gè)節(jié)點(diǎn)。

那就直接看圖一層一層數(shù)唄：

第 0 層（根節(jié)點(diǎn)）有C(N, 0) = 1個(gè)節(jié)點(diǎn)。

第 1 層有C(N, 1) = N個(gè)節(jié)點(diǎn)。

第 2 層有C(N, 2)個(gè)節(jié)點(diǎn)。

第 3 層有C(N, 3)個(gè)節(jié)點(diǎn)。

以此類推，其中C就是我們高中學(xué)過的組合數(shù)函數(shù)。

由于這棵組合樹的高度為N，組合數(shù)求和公式是高中學(xué)過的， 所以總的節(jié)點(diǎn)數(shù)為2^N ：

C(N, 0) + C(N, 1) + C(N, 2) + ... + C(N, N) = 2^N

就算你忘記了組合數(shù)求和公式，其實(shí)也可以推導(dǎo)出來節(jié)點(diǎn)總數(shù)：因?yàn)?code>N個(gè)元素的所有子集（冪集）數(shù)量為2^N，而這棵樹的每個(gè)節(jié)點(diǎn)代表一個(gè)子集，所以樹的節(jié)點(diǎn)總數(shù)也為2^N。

那么，現(xiàn)在就可以得出算法的總復(fù)雜度：

遞歸的次數(shù) x 函數(shù)本身的時(shí)間復(fù)雜度
= 遞歸樹節(jié)點(diǎn)個(gè)數(shù) x 每個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度
= O(2^N) * O(N)
= O(N*2^N)

分析下該算法的空間復(fù)雜度：

backtrack函數(shù)的遞歸深度為遞歸樹的高度O(N)，而算法需要存儲(chǔ)所有子集的結(jié)果，粗略估算下需要申請(qǐng)的空間為O(N*2^N)， 所以總的空間復(fù)雜度為O(N*2^N) 。

到這里，標(biāo)準(zhǔn)排列/子集問題的時(shí)間復(fù)雜度就分析完了，前文 回溯算法秒殺排列組合問題的 9 種變體中的其他問題變形都可以按照類似的邏輯分析，這些就留給你自己分析吧。

最后總結(jié)

本文篇幅較大，我簡(jiǎn)單總結(jié)下重點(diǎn)：

1、Big O 標(biāo)記代表一個(gè)函數(shù)的集合，用它表示時(shí)空復(fù)雜度時(shí)代表一個(gè)上界，所以如果你和別人算的復(fù)雜度不一樣，可能你們都是對(duì)的，只是精確度不同罷了。

2、時(shí)間復(fù)雜度的分析不難，關(guān)鍵是你要透徹理解算法到底干了什么事。非遞歸算法中嵌套循環(huán)的復(fù)雜度依然可能是線性的；數(shù)據(jù)結(jié)構(gòu) API 需要用平均時(shí)間復(fù)雜度衡量性能；遞歸算法本質(zhì)是遍歷遞歸樹，時(shí)間復(fù)雜度取決于遞歸樹中節(jié)點(diǎn)的個(gè)數(shù)（遞歸次數(shù)）和每個(gè)節(jié)點(diǎn)的復(fù)雜度（遞歸函數(shù)本身的復(fù)雜度）。

好了，能看到這里，真得給你鼓掌。需要說明的是，本文給出的一些復(fù)雜度都是比較粗略的估算，上界都不是很「緊」，如果你不滿足于粗略的估算，想計(jì)算更「緊」更精確的上界，就需要比較好的數(shù)學(xué)功底了。不過從面試筆試的角度來說，掌握這些基本分析技術(shù)已經(jīng)足夠應(yīng)對(duì)了。