什么是遞歸樹
遞歸的思想誊锭，就是將大問題分解為小問題，再將小問題分解為小小問題弥锄。這樣一層一層分解丧靡，直到問題的數(shù)據(jù)規(guī)模被分解得足夠小，不用繼續(xù)分解為止籽暇。
如果我們把這個(gè)一層一層分解的過程畫成圖温治，它其實(shí)就是一棵樹。我們給這棵樹起一個(gè)名字戒悠，叫做遞歸樹熬荆。
用遞歸樹來分析遞歸算法的時(shí)間復(fù)雜度
以遞推公式 f(n) = f(n-1) + f(n-2) 為例，它的時(shí)間復(fù)雜度遞推公式為 T(n) = T(n-1) + T(n-2) + c绸狐。
從出發(fā)到葉子節(jié)點(diǎn)卤恳，最短路徑是一直走 n-2 這條遞歸路線，長度是 n/2寒矿；最長路徑是一直走 n-1這條遞歸路線突琳，長度是 n。
每次分解需要做一次加法運(yùn)算劫窒，我們把這次加法運(yùn)算的時(shí)間復(fù)雜度記為常數(shù) 1本今。那么第一層需要消耗時(shí)間 1，第二層需要消耗時(shí)間 2，第三層需要消耗時(shí)間 2^2=4 ……冠息。依次類推挪凑，第 k 層需要消耗 2^(k-1) 的時(shí)間。從第一層累加到第 k 層逛艰， 總共需要消耗 1 + 2 + 4 + …… + 2^(k-1) = 2^k -1 的時(shí)間躏碳。
然后回頭看遞歸樹的圖，如果遞歸時(shí)都走 n-2散怖，那么路徑長度就是 2/n菇绵，如果整棵樹的所有路徑長度都是 n/2，那么整個(gè)算法的時(shí)間復(fù)雜度就是 O(2^(n/2) - 1) 镇眷。同理如果都是最長路徑 n 咬最，那么整個(gè)算法的時(shí)間復(fù)雜度就是 O(2^n -1)。當(dāng)我們從圖中可以看到欠动，整個(gè)遞歸樹是介于全部都是最短路徑和全部都是最長路徑之間的情況永乌，所以時(shí)間復(fù)雜度也是在兩者之間，但是我們可以看到兩者 O(2^(n/2) - 1) 和 O(2^n -1) 都是指數(shù)級(jí)別的時(shí)間復(fù)雜度具伍。故最后整個(gè)算法是指數(shù)級(jí)別的時(shí)間復(fù)雜度翅雏。
概況分析方法
- 畫出遞歸樹，遞推公式人芽。
- 分析每層需要消耗的時(shí)間
- 計(jì)算邊界時(shí)間復(fù)雜度（都是最長路徑望几、都是最短路徑）
- 總復(fù)雜度就在邊界復(fù)雜度之間。
