遞歸代碼的時間複雜度分析起來非常麻煩，今天我們嘗試來藉助遞歸樹分析遞歸演算法的時間複雜度。

1. 遞歸樹與時間複雜度分析

遞歸的思想就是將大問題一層一層地分解為小問題來求解，如果我們把這個分解過程畫成圖，它其實就是一棵樹，我們稱之為遞歸樹。

上圖為斐波那契數列的遞歸樹，節點裡的數字表示數據的規模，一個節點的求解可以分解為左右子節點兩個問題的求解。

下面我們用遞歸樹來分析一下歸併排序的時間複雜度。歸併排序每次都將數據分為左右兩部分，然後將左右兩部分排好序的數據再合併起來。

可以看到，歸併排序大部分的時間都消耗在將兩部分數據合併成一部分的歸併操作上。而在樹的每一層，可以看到，我們總共要歸併的數據規模是一樣的，都為n。而且，這是一個滿二叉樹，樹的高度大約為log_2n。因此，歸併排序的時間複雜度也就為O(nlog_2n) = O(nlogn)。

2. 快速排序的時間複雜度

快速排序在最好的情況下，每次分區都恰好將數據一分為二，這時候遞推公式為T(n) = 2T(frac{n}{2})+n，我們可以很容易地就推導出時間複雜度為O(nlogn)。

但實際上，我們不可能每次都做到將數據恰好一分為二。假設每次兩個分區的大小比例為1:k，當k=9時，遞推公式就為T(n) = T(frac{n}{10})+T(frac{9n}{10})+n，這時候推導起來就比較複雜了。

針對同樣的情況，下面我們來看遞歸樹的分析法。

可以看到，在快速排序的每一層，我們需要遍歷的數據總數都為n。接下來，我們只需要知道遞歸樹的深度就可以得出時間複雜度了。

如果每次都乘以frac{1}{10}，那麼樹就會最快到達節點值為 1 的葉節點；而如果每次都乘以frac{9}{10}，那麼樹就會最慢到達節點值為 1 的葉節點，此即為樹的最大深度。

因此快速排序的時間複雜度就介於O(nlog_{10}n)和O(nlog_{frac{10}{9}}n)之間。而當k變化的時候，也只是底數發生了變化，用大O法表示的時間複雜度都為O(nlogn)。

3. 斐波那契數列的時間複雜度

斐波那契數列的演算法如下，我們可以很容易地建立一個遞歸樹。

int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}

可以看到節點總數隨著層數指數級增加，而每一層需要的加法次數與節點個數成正比，第k層的時間消耗為2^{k-1}。

如果每次都取n-1，那麼此時從根節點到葉節點路徑最長，大約為n；而如果每次都取n-2，那麼此時從根節點到葉節點路徑最短，大約為frac{n}{2}。

因此，演算法的時間複雜度就介於

O(min) =1+2+cdots+2^{frac{n}{2}-1} = 2^{frac{n}{2}}-1O(max) = 1+2+cdots+2^{n-1} = 2^n-1

這樣，我們就基本知道了這個演算法的時間複雜度是指數級的，非常高。

4. 全排列的時間複雜度

求n個數的全排列也可以藉助遞歸來實現，如果我們確定了最後一位數據，那問題就變成了求解剩餘n-1個數據的全排列這個子問題。

假設數組中存儲的是 1，2， 3...n。

f(1,2,...n) = {最後一位是 1, f(n-1)} + {最後一位是 2, f(n-1)} +...+{最後一位是 n, f(n-1)}。

寫成代碼如下：

// 調用方式：
// int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
// k 表示要處理的子數組的數據個數
public void printPermutations(int[] data, int n, int k) {
if (k == 1) {
for (int i = 0; i < n; ++i) {
System.out.print(data[i] + " ");
}
System.out.println();
}

for (int i = 0; i < k; ++i) {
int tmp = data[i];
data[i] = data[k-1];
data[k-1] = tmp;

printPermutations(data, n, k - 1);

tmp = data[i];
data[i] = data[k-1];
data[k-1] = tmp;
}
}

同樣，我們也可以畫出這個演算法的遞歸樹，只不過這個樹已經不是標準的二叉樹了。

第一層我們需要n次數據交換，第二層有n個n-1次數據交換，以此類推，第k層數據交換總次數為n*(n-1)*(n-2)cdots*(n-k+1)。所以，演算法總的時間複雜度為

n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1

這個求和公式比較複雜，但我們知道最後一項為n!，而前面的項都小於n!，因此總和肯定介於1*n!和n*n!之間。演算法的時間複雜度為階乘級的，非常高。

參考資料-極客時間專欄《數據結構與演算法之美》

獲取更多精彩，請關注「seniusen」!

weixin.qq.com/r/PilRSSf (二維碼自動識別)

推薦閱讀：

相關文章