算法時空復雜度分析實用指南（下）

遞歸算法分析

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

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

所以：

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

遞歸算法的空間復雜度 = 遞歸堆棧的深度 + 算法申請的存儲空間

或者再說得直觀一點：

遞歸算法的時間復雜度 = 遞歸樹的節(jié)點個數(shù) x 每個節(jié)點的時間復雜度

遞歸算法的空間復雜度 = 遞歸樹的高度 + 算法申請的存儲空間

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

首先說一下動態(tài)規(guī)劃算法 ，還是拿前文 動態(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;
    // 時間 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;
}

當amount = 11, coins = [1,2,5]時，該算法的遞歸樹就長這樣：

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

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

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

當然，之前也說了，這個復雜度只是一個粗略的上界，并不準確，真實的效率肯定會高一些。

這個算法的空間復雜度很容易分析：

dp函數(shù)本身沒有申請數(shù)組之類的，所以算法申請的存儲空間為O(1)；而dp函數(shù)的堆棧深度為遞歸樹的高度O(N)，所以這個算法的空間復雜度為O(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;
    // 查備忘錄，防止重復計算
    if (memo[amount] != -666)
        return memo[amount];

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

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

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

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

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

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

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

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

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

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

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

    dp[0] = 0;
    // 時間 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];
}

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

接下來說一下回溯算法 ，需要你看過前文回溯算法秒殺排列組合問題的 9 種變體，下面我會以標準的全排列問題和子集問題的解法為例，分析一下其時間復雜度。

先看標準全排列問題 （元素無重不可復選）的核心函數(shù)backtrack：

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

    // 非葉子節(jié)點，遍歷所有子節(jié)點，時間 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;
    }
}

當nums = [1,2,3]時，backtrack其實在遍歷這棵遞歸樹：

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

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

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

PS：函數(shù)本身（每個節(jié)點）的時間復雜度并不是樹枝的條數(shù)?？创a，每個節(jié)點都會執(zhí)行整個 for 循環(huán)，所以每個節(jié)點的復雜度都是O(N)。

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

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

第 1 層有P(N, 1) = N個節(jié)點。

第 2 層有P(N, 2) = N x (N - 1)個節(jié)點。

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

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

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

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

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

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

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

當然，由于計算節(jié)點總數(shù)的時候我們?yōu)榱朔奖阌嬎惆牙奂禹棓U大了很多，所以這個結果肯定也是偏大的，不過用來描述復雜度的上界還是可以接受的。

分析下該算法的空間復雜度：

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

最后看下標準子集問題 （元素無重不可復選）的核心函數(shù)backtrack：

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

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

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

當nums = [1,2,3]時，backtrack其實在遍歷這棵遞歸樹：

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

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

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

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

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

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

第 1 層有C(N, 1) = N個節(jié)點。

第 2 層有C(N, 2)個節(jié)點。

第 3 層有C(N, 3)個節(jié)點。

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

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

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

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

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

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

分析下該算法的空間復雜度：

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

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

最后總結

本文篇幅較大，我簡單總結下重點：

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

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

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