求遞歸算法的時間復雜度例題及答案？
(1) 遞歸執(zhí)行過程
例子：求N!。
這是一個簡單的"累乘"問題，用遞歸算法也能解決。
n! = n * (n - 1)! n > 1
0! = 1, 1! = 1 n = 0,1
因此，遞歸算法如下：
Java代碼
fact(int n) {
if(n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);
}
以n=3為例，看運行過程如下：
fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3)
------------------------------> ------------------------------>
遞歸 回溯
遞歸算法在運行中不斷調(diào)用自身降低規(guī)模的過程，當規(guī)模降為1，即遞歸到fact(1)時，滿足停止條件停止遞歸，開始回溯(返回調(diào)用算法)并計算，從fact(1)=1計算返回到fact(2);計算2*fact(1)=2返回到fact(3)；計算3*fact(2)=6，結束遞歸。
算法的起始模塊也是終止模塊。
(2) 遞歸實現(xiàn)機制
每一次遞歸調(diào)用，都用一個特殊的數(shù)據(jù)結構"棧"記錄當前算法的執(zhí)行狀態(tài)，特別地設置地址棧，用來記錄當前算法的執(zhí)行位置，以備回溯時正常返回。遞歸模塊的形式參數(shù)是普通變量，每次遞歸調(diào)用得到的值都是不同的，他們也是由"棧"來存儲。
(3) 遞歸調(diào)用的幾種形式
一般遞歸調(diào)用有以下幾種形式(其中a1、a2、b1、b2、k1、k2為常數(shù))。
<1> 直接簡單遞歸調(diào)用： f(n) {...a1 * f((n - k1) / b1); ...};
<2> 直接復雜遞歸調(diào)用： f(n) {...a1 * f((n - k1) / b1); a2 * f((n - k2) / b2); ...};
<3> 間接遞歸調(diào)用： f(n) {...a1 * f((n - k1) / b1); ...}，
g(n) {...a2 * f((n - k2) / b2); ...}。
2. 遞歸算法效率分析方法
遞歸算法的分析方法比較多，最常用的便是迭代法。
迭代法的基本步驟是先將遞歸算法簡化為對應的遞歸方程，然后通過反復迭代，將遞歸方程的右端變換成一個級數(shù)，最后求級數(shù)的和，再估計和的漸進階。
<1> 例：n!
算法的遞歸方程為： T(n) = T(n - 1) + O(1);
迭代展開： T(n) = T(n - 1) + O(1)
= T(n - 2) + O(1) + O(1)
= T(n - 3) + O(1) + O(1) + O(1)
= ......
= O(1) + ... + O(1) + O(1) + O(1)
= n * O(1)
= O(n)
這個例子的時間復雜性是線性的。
<2> 例：如下遞歸方程：
T(n) = 2T(n/2) + 2, 且假設n=2的k次方。
T(n) = 2T(n/2) + 2
= 2(2T(n/2*2) + 2) + 2
= 4T(n/2*2) + 4 + 2
= 4(2T(n/2*2*2) + 2) + 4 + 2
= 2*2*2T(n/2*2*2) + 8 + 4 + 2
= ...
= 2的(k-1)次方 * T(n/2的(i-1)次方) + $(i:1~(k-1))2的i次方
= 2的(k-1)次方 + (2的k次方) - 2
= (3/2) * (2的k次方) - 2
= (3/2) * n - 2
= O(n)
這個例子的時間復雜性也是線性的。
<3> 例：如下遞歸方程：
T(n) = 2T(n/2) + O(n), 且假設n=2的k次方。
T(n) = 2T(n/2) + O(n)
= 2T(n/4) + 2O(n/2) + O(n)
= ...
= O(n) + O(n) + ... + O(n) + O(n) + O(n)
= k * O(n)
= O(k*n)
= O(nlog2n) //以2為底
一般地，當遞歸方程為T(n) = aT(n/c) + O(n), T(n)的解為：
O(n) (a<c && c>1)
O(nlog2n) (a=c && c>1) //以2為底
O(nlogca) (a>c && c>1) //n的(logca)次方，以c為底
上面介紹的3種遞歸調(diào)用形式，比較常用的是第一種情況，第二種形式也有時出現(xiàn)，而第三種形式(間接遞歸調(diào)用)使用的較少，且算法分析
比較復雜。 下面舉個第二種形式的遞歸調(diào)用例子。
<4> 遞歸方程為：T(n) = T(n/3) + T(2n/3) + n
為了更好的理解，先畫出遞歸過程相應的遞歸樹：
n --------> n
n/3 2n/3 --------> n
n/9 2n/9 2n/9 4n/9 --------> n
...... ...... ...... ....... ......
--------
總共O(nlogn)
累計遞歸樹各層的非遞歸項的值，每一層和都等于n，從根到葉的最長路徑是：
n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1
設最長路徑為k，則應該有：
(2/3)的k次方 * n = 1
得到 k = log(2/3)n // 以(2/3)為底
于是 T(n) <= (K + 1) * n = n (log(2/3)n + 1)
即 T(n) = O(nlogn)
由此例子表明，對于第二種遞歸形式調(diào)用，借助于遞歸樹，用迭代法進行算法分析是簡單易行的。