加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
今天，我們來講樹這種數據結構的一種特殊應用，遞歸樹。
我們都知道，遞歸代碼的時間複雜度分析起來很麻煩。我們在第 12 節《排序（下）》那裡講過，如何利用遞推公式，求解歸併排序、快速排序的時間複雜度，但是，有些情況，比如快排的平均時間複雜度的分析，用遞推公式的話，會涉及非常複雜的數學推導。
除了用遞推公式這種比較複雜的分析方法，有沒有更簡單的方法呢？今天，我們就來學習另外一種方法，藉助遞歸樹來分析遞歸算法的時間複雜度。
遞歸樹與時間複雜度分析
我們前面講過，遞歸的思想就是，將大問題分解為小問題來求解，然後再將小問題分解為小小問題。這樣一層一層地分解，直到問題的數據規模被分解得足夠小，不用繼續遞歸分解為止。
如果我們把這個一層一層的分解過程畫成圖，它其實就是一棵樹。我們給這棵樹起一個名字，叫作
遞歸樹。我這裡畫了一棵斐波那契數列的遞歸樹，你可以看看。節點裡的數字表示數據的規模，一個節點的求解可以分解為左右子節點兩個問題的求解。 通過這個例子，你對遞歸樹的樣子應該有個感性的認識了，看起來並不複雜。現在，我們就來看，如何用遞歸樹來求解時間複雜度。
歸併排序算法你還記得吧？它的遞歸實現代碼非常簡潔。現在我們就藉助歸併排序來看看，如何用遞歸樹，來分析遞歸代碼的時間複雜度。
歸併排序的原理我就不詳細介紹了，如果你忘記了，可以回看一下第 12 節的內容。歸併排序每次會將數據規模一分為二。我們把歸併排序畫成遞歸樹，就是下面這個樣子：
因為每次分解都是一分為二，所以代價很低，我們把時間上的消耗記作常量 1。歸併算法中比較耗時的是歸併操作，也就是把兩個子數組合併為大數組。從圖中我們可以看出，每一層歸併操作消耗的時間總和是一樣的，跟要排序的數據規模有關。我們把每一層歸併操作消耗的時間記作 n。
現在，我們只需要知道這棵樹的高度 h，用高度 h 乘以每一層的時間消耗n，就可以得到總的時間複雜度 O(n∗h)。
從歸併排序的原理和遞歸樹，可以看出來，歸併排序遞歸樹是一棵滿二叉樹。我們前兩節中講到，滿二叉樹的高度大約是 log2 n，所以，歸併排序遞歸實現的時間複雜度就是 O(nlogn)。我這裡的時間複雜度都是估算的，對樹的高度的計算也沒有那麼精確，但是這並不影響複雜度的計算結果。
利用遞歸樹的時間複雜度分析方法並不難理解，關鍵還是在實戰，所以，接下來我會通過三個實際的遞歸算法，帶你實戰一下遞歸的複雜度分析。學完這節課之後，你應該能真正掌握遞歸代碼的複雜度分析。
實戰一：分析快速排序的時間複雜度
在用遞歸樹推導之前，我們先來回憶一下用遞推公式的分析方法。你可以回想一下，當時，我們為什麼說用遞推公式來求解平均時間複雜度非常複雜？
快速排序在最好情況下，每次分區都能一分為二，這個時候用遞推公式 T(n)=2T(n/2)+n，很容易就能推導出時間複雜度是 O(nlogn)。但是，我們並不可能每次分區都這麼幸運，正好一分為二。
我們假設平均情況下，每次分區之後，兩個分區的大小比例為 1:k。當 k=9 時，如果用遞推公式的方法來求解時間複雜度的話，遞推公式就寫成 T(n)=T(n/10)+T(9n/10)+n。
這個公式可以推導出時間複雜度，但是推導過程非常複雜。那我們來看看，用遞歸樹來分析快速排序的平均情況時間複雜度，是不是比較簡單呢？
我們還是取 k 等於 9，也就是說，每次分區都很不平均，一個分區是另一個分區的 9 倍。如果我們把遞歸分解的過程畫成遞歸樹，就是下面這個樣子：
快速排序的過程中，每次分區都要遍歷待分區區間的所有數據，所以，每一層分區操作所遍歷的數據的個數之和就是 n。我們現在只要求出遞歸樹的高度 h，這個快排過程遍歷的數據個數就是 h∗n ，也就是說，時間複雜度就是 O(h∗n)。
因為每次分區並不是均勻地一分為二，所以遞歸樹並不是滿二叉樹。這樣一個遞歸樹的高度是多少呢？
我們知道，快速排序結束的條件就是待排序的小區間，大小為 1，也就是說葉子節點裡的數據規模是 1。從根節點 n 到葉子節點 1，遞歸樹中最短的一個路徑每次都乘以 1/10，最長的一個路徑每次都乘以 9/10。通過計算，我們可以得到，從根節點到葉子節點的最短路徑是 log10 n，最長的路徑是 log10/9 n。
所以，遍歷數據的個數總和就介於 nlog10 n 和 nlog10/9 n 之間。根據複雜度的大 O 表示法，對數複雜度的底數不管是多少，我們統一寫成 log n，所以，當分區大小比例是 1:9 時，快速排序的時間複雜度仍然是 O(nlog n)。
剛剛我們假設 k=9 ，那如果 k=99 ，也就是說，每次分區極其不平均，兩個區間大小是 1:99 ，這個時候的時間複雜度是多少呢？
我們可以類比上面 k=9 的分析過程。當 k=99 的時候，樹的最短路徑就是 log100 n，最長路徑是 log100/99 n，所以總遍歷數據個數介於 nlog100 n 和 nlog100/99 n 之間。儘管底數變了，但是時間複雜度也仍然是 O(nlogn)。
也就是說，對於 k 等於 9，99，甚至是 999，9999……，只要 k 的值不隨 n 變化，是一個事先確定的常量，那快排的時間複雜度就是 O(nlogn)。所以，從概率論的角度來說，快排的平均時間複雜度就是 O(nlogn)。
實戰二：分析斐波那契數列的時間複雜度
在遞歸那一節中，我們舉了一個跨臺階的例子，你還記得嗎？那個例子實際上就是一個斐波那契數列。為了方便你回憶，我把它的代碼實現貼在這裡。
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
這樣一段代碼的時間複雜度是多少呢？你可以先試著分析一下，然後再來看，我是怎麼利用遞歸樹來分析的。
我們先把上面的遞歸代碼畫成遞歸樹，就是下面這個樣子：
這棵遞歸樹的高度是多少呢？
f(n) 分解為 f(n−1)和 f(n−2)，每次數據規模都是 −1 或者 −2，葉子節點的數據規模是 1 或者 2。所以，從根節點走到葉子節點，每條路徑是長短不一的。如果每次都是 −1，那最長路徑大約就是 n；如果每次都是 −2，那最短路徑大約就是 n/2。
每次分解之後的合併操作只需要一次加法運算，我們把這次加法運算的時間消耗記作 1。所以，從上往下，第一層的總時間消耗是 1，第二層的總時間消耗是 2，第三層的總時間消耗就是 2*2。依次類推，第 k 層的時間消耗就是 2 的k−1次方，那整個算法的總的時間消耗就是每一層時間消耗之和。
如果路徑長度都為 n，那這個總和就是 2的n次方−1。
如果路徑長度都是 n/2 ，那整個算法的總的時間消耗就是 2n/2 −1。
所以，這個算法的時間複雜度就介於 O(2n) 和 O(2n/2) 之間。雖然這樣得到的結果還不夠精確，只是一個範圍，但是我們也基本上知道了上面算法的時間複雜度是指數級的，非常高。
實戰三：分析全排列的時間複雜度
前面兩個複雜度分析都比較簡單，我們再來看個稍微複雜的。
我們在高中的時候都學過排列組合。“如何把 n 個數據的所有排列都找出來”，這就是全排列的問題。
我來舉個例子。比如，1，2，3 這樣 3 個數據，有下面這幾種不同的排列：
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
如何編程打印一組數據的所有排列呢？這裡就可以用遞歸來實現。
如果我們確定了最後一位數據，那就變成了求解剩下 n−1 個數據的排列問題。而最後一位數據可以是 n 個數據中的任意一個，因此它的取值就有 n 種情況。所以，“n 個數據的排列”問題，就可以分解成 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 次交換，所以第二層總的交換次數是 n∗(n−1。第三層有 n∗(n−1) 個節點，每個節點分解需要 n−2 次交換，所以第三層總的交換次數是 n∗(n−1)∗(n−2)。
以此類推，第 k 層總的交換次數就是 n∗(n−1)∗(n−2)∗…∗(n−k+1)。最後一層的交換次數就是 n∗(n−1)∗(n−2)∗…∗2∗1。每一層的交換次數之和就是總的交換次數。
n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1
這個公式的求和比較複雜，我們看最後一個數，n∗(n−1)∗(n−2)∗…∗2∗1 等於 n!，而前面的 n−1 個數都小於最後一個數，所以，總和肯定小於 n∗n!，也就是說，全排列的遞歸算法的時間複雜度大於 O(n!)，小於 O(n∗n!)，雖然我們沒法知道非常精確的時間複雜度，但是這樣一個範圍已經讓我們知道，全排列的時間複雜度是非常高的。
這裡我稍微說下，掌握分析的方法很重要，思路是重點，不要糾結於精確的時間複雜度到底是多少。
內容小結
今天，我們用遞歸樹分析了遞歸代碼的時間複雜度。加上我們在排序那一節講到的遞推公式的時間複雜度分析方法，我們現在已經學習了兩種遞歸代碼的時間複雜度分析方法了。
有些代碼比較適合用遞推公式來分析，比如歸併排序的時間複雜度、快速排序的最好情況時間複雜度；有些比較適合採用遞歸樹來分析，比如快速排序的平均時間複雜度。而有些可能兩個都不怎麼適合使用，比如二叉樹的遞歸前中後序遍歷。
時間複雜度分析的理論知識並不多，也不復雜，掌握起來也不難，但是，在我們平時的工作、學習中，面對的代碼千差萬別，能夠靈活應用學到的複雜度分析方法，來分析現有的代碼，並不是件簡單的事情，所以，你平時要多實戰、多分析，只有這樣，面對任何代碼的時間複雜度分析，你才能做到遊刃有餘、毫不畏懼。
閱讀更多 xiuxiuing 的文章
