遞歸函數時間復雜度分析

?

(1)?遞歸執行過程?
???例子：求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)?
????------------------------------>??------------------------------>?
????????????????遞歸????????????????????????????回溯?
??遞歸算法在運行中不斷調用自身降低規模的過程，當規模降為1，即遞歸到fact(1)時，滿足停止條件停止遞歸，開始回溯(返回調用算法)并計算，從fact(1)=1計算返回到fact(2);計算2*fact(1)=2返回到fact(3)；計算3*fact(2)=6，結束遞歸。?
???算法的起始模塊也是終止模塊。?
(2)?遞歸實現機制?
????每一次遞歸調用，都用一個特殊的數據結構"棧"記錄當前算法的執行狀態，特別地設置地址棧，用來記錄當前算法的執行位置，以備回溯時正常返回。遞歸模塊的形式參數是普通變量，每次遞歸調用得到的值都是不同的，他們也是由"棧"來存儲。?
(3)?遞歸調用的幾種形式?
????一般遞歸調用有以下幾種形式(其中a1、a2、b1、b2、k1、k2為常數)。?
???<1>?直接簡單遞歸調用：?f(n)?{...a1?*?f((n?-?k1)?/?b1);?...};?
????
???<2>?直接復雜遞歸調用：?f(n)?{...a1?*?f((n?-?k1)?/?b1);?a2?*?f((n?-?k2)?/?b2);?...};?
????<3>?間接遞歸調用：??f(n)?{...a1?*?f((n?-?k1)?/?b1);?...}，?
????????????????????????g(n)?{...a2?*?f((n?-?k2)?/?b2);?...}。?
2.?遞歸算法效率分析方法?
???遞歸算法的分析方法比較多，最常用的便是迭代法。?
??迭代法的基本步驟是先將遞歸算法簡化為對應的遞歸方程，然后通過反復迭代，將遞歸方程的右端變換成一個級數，最后求級數的和，再估計和的漸進階。?
??<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種遞歸調用形式，比較常用的是第一種情況，第二種形式也有時出現，而第三種形式(間接遞歸調用)使用的較少，且算法分析?
比較復雜。?下面舉個第二種形式的遞歸調用例子。?
??<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)?
????由此例子表明，對于第二種遞歸形式調用，借助于遞歸樹，用迭代法進行算法分析是簡單易行的。

總結

以上是生活随笔為你收集整理的递归函数时间复杂度分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。