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