1、絕大部分算法的執(zhí)行，都表現(xiàn)為按某種條件重復(fù)地執(zhí)行一些循環(huán)。而這些循環(huán)又經(jīng)?？梢杂眠f歸關(guān)系表達(dá)。因此，算法的運(yùn)行時(shí)間也經(jīng)常存在著一種遞歸關(guān)系。例如：求n！時(shí)間復(fù)雜度的分析1遞歸算法的時(shí)間復(fù)雜度分析 用生成函數(shù)求解遞歸方程用特征方程求解遞歸方程用遞推法求解遞歸方程時(shí)間復(fù)雜度的分析2用生成函數(shù)求解遞歸方程原理： 遞歸算法的運(yùn)行時(shí)間，隨著遞歸深度的增加而增加。假定序列：a0,a1,ak表示遞歸算法在不同遞歸深度時(shí)的運(yùn)行時(shí)間，則序列中每一個(gè)元素之間，存在著一定的遞歸關(guān)系。一般希望了解當(dāng)遞歸深度k=n時(shí)，序列中元素an的值，即找出運(yùn)行時(shí)間an與問題規(guī)模n的關(guān)系。3用生成函數(shù)求解遞歸方程 可以借助一個(gè)“參數(shù)

2、”z來建立一個(gè)無(wú)窮級(jí)數(shù)的和：通過對(duì)G(z)的一系列演算，得到序列a0,a1,ak的一個(gè)通項(xiàng)表達(dá)式，便可容易地獲得遞歸算法在遞歸深度k=n時(shí)的運(yùn)行時(shí)間。4用生成函數(shù)求解遞歸方程定義：令 是一個(gè)實(shí)數(shù)序列，構(gòu)造如下的函數(shù)：則函數(shù)G(z)稱為序列 的生成函數(shù)。5例如：函數(shù)則函數(shù) 便是序列 的生成函數(shù)用生成函數(shù)求解遞歸方程6生成函數(shù)的性質(zhì)加法乘法z變換積分與微分用生成函數(shù)求解遞歸方程7當(dāng)c=1時(shí)：則函數(shù) 便是序列 1,1,1, 的生成函數(shù)用生成函數(shù)求解遞歸方程8如果對(duì) 求導(dǎo)數(shù)，可得則函數(shù) 便是序列 1,2,3的生成函數(shù)用生成函數(shù)求解遞歸方程如果對(duì)（2.2.7）式求導(dǎo)數(shù)，可得 9如果對(duì) 求積分，可得則函數(shù)

3、 便是序列 的生成函數(shù)用生成函數(shù)求解遞歸方程如果對(duì)（2.2.7）式求導(dǎo)數(shù)，可得 10舉例1：漢諾塔(Hanoi)問題void Hanoi(char a,char b,char c,int n) if(n=1)printf(“%c-%c”,a,b); else Hanoi(a,c,b,n-1);/將n-1個(gè)盤子a-c printf(“%c-%c”,a,b);/將n從a到b Hanoi(c,b,a,n-1);/將n-1個(gè)盤子b-c 用生成函數(shù)求解遞歸方程如果對(duì)（2.2.7）式求導(dǎo)數(shù)，可得 ba11建立移動(dòng)次數(shù)h(n)的遞歸方程，n代表盤數(shù)用生成函數(shù)求解遞歸方程12構(gòu)造生成函數(shù)：用h(n)作為系數(shù)，

4、構(gòu)造一個(gè)生成函數(shù)（n從1開始）用生成函數(shù)求解遞歸方程13根據(jù)遞歸方程，對(duì)G(x)進(jìn)行變換，確定一個(gè)函數(shù)的冪級(jí)數(shù)展開式，令用生成函數(shù)求解遞歸方程14用生成函數(shù)求解遞歸方程因?yàn)椋篽(n)=2h(n-1)+1, 所以：h(n)-2h(n-1)=115令 用生成函數(shù)求解遞歸方程求得：16所以 用生成函數(shù)求解遞歸方程，它是式中第n項(xiàng)的系數(shù)。當(dāng)時(shí)n=64， 移動(dòng)次數(shù)為264-1。 17舉例2：若某遞歸算法執(zhí)行時(shí)間的遞歸表達(dá)式為：構(gòu)造生成函數(shù)f(x)：對(duì)f(x)進(jìn)行演算：用生成函數(shù)求解遞歸方程如果對(duì)（2.2.7）式求導(dǎo)數(shù)，可得 18練習(xí)：用生成函數(shù)解下面的遞歸方程（1）f(n)=3f(n-1)+1 f(1)

5、=2（2）f(n)=5f(n-1)-6f(n-2) f(0)=1 f(1)=0用生成函數(shù)求解遞歸方程如果對(duì)（2.2.7）式求導(dǎo)數(shù)，可得 19用特征方程解遞歸方程的兩種情況K階常系數(shù)線性齊次遞歸方程K階常系數(shù)線性非齊次遞歸方程用特征方程求解遞歸方程如果對(duì)（2.2.7）式求導(dǎo)數(shù)，可得 20K階常系數(shù)線性齊次遞歸方程用特征方程求解遞歸方程其中第2式是方程的初始條件，其中bi為常數(shù)。特征方程的建立可以求出特征方程的根，得到遞歸方程的通解。再利用遞歸方程的初始條件，確定通解中的待定系數(shù)，從而得到遞歸方程的解21分成兩種情況討論 是特征方程的k個(gè)互不相同的根。則遞歸方程的通解為：c1,c2,ck為待定系數(shù)，把遞歸方程的初始條件代入其中，建立聯(lián)立方程，確定系數(shù)c1,c2,ck ，從而可求出通解f(n) 用特征方程求解遞歸方程222.特征方程的n個(gè)根中有r個(gè)重根 則遞歸方程的通解為：c1,c2,ck為待定系數(shù)，把遞歸方程的初始條件代入其中，建立聯(lián)立方程，確定系數(shù)c1,c2,ck ，從而可求出通解f(n) 用特征方程求解遞歸方程23例題1