什么是遞歸樹
遞歸的思想，就是將大問題分解為小問題，再將小問題分解為小小問題。這樣一層一層分解，直到問題的數(shù)據(jù)規(guī)模被分解得足夠小，不用繼續(xù)分解為止。
如果我們把這個一層一層分解的過程畫成圖，它其實就是一棵樹。我們給這棵樹起一個名字，叫做遞歸樹。
遞歸樹
用遞歸樹來分析遞歸算法的時間復(fù)雜度
以遞推公式 f(n) = f(n-1) + f(n-2) 為例，它的時間復(fù)雜度遞推公式為 T(n) = T(n-1) + T(n-2) + c。
從出發(fā)到葉子節(jié)點，最短路徑是一直走 n-2 這條遞歸路線，長度是 n/2；最長路徑是一直走 n-1這條遞歸路線，長度是 n。
每次分解需要做一次加法運算，我們把這次加法運算的時間復(fù)雜度記為常數(shù) 1。那么第一層需要消耗時間 1，第二層需要消耗時間 2，第三層需要消耗時間 2^2=4 ……。依次類推，第 k 層需要消耗 2^(k-1) 的時間。從第一層累加到第 k 層， 總共需要消耗 1 + 2 + 4 + …… + 2^(k-1) = 2^k -1 的時間。
然后回頭看遞歸樹的圖，如果遞歸時都走 n-2，那么路徑長度就是 2/n，如果整棵樹的所有路徑長度都是 n/2，那么整個算法的時間復(fù)雜度就是 O(2^(n/2) - 1) 。同理如果都是最長路徑 n ，那么整個算法的時間復(fù)雜度就是 O(2^n -1)。當(dāng)我們從圖中可以看到，整個遞歸樹是介于全部都是最短路徑和全部都是最長路徑之間的情況，所以時間復(fù)雜度也是在兩者之間，但是我們可以看到兩者 O(2^(n/2) - 1) 和 O(2^n -1) 都是指數(shù)級別的時間復(fù)雜度。故最后整個算法是指數(shù)級別的時間復(fù)雜度。
概況分析方法
- 畫出遞歸樹，遞推公式。
- 分析每層需要消耗的時間
- 計算邊界時間復(fù)雜度（都是最長路徑、都是最短路徑）
- 總復(fù)雜度就在邊界復(fù)雜度之間。
