1、第第1010章章 遞推方程與生成函數(shù)遞推方程與生成函數(shù)第第1010章章 遞推方程與生成函數(shù)遞推方程與生成函數(shù) 10.1 遞推方程及其運用遞推方程及其運用 10.2 生成函數(shù)及其運用生成函數(shù)及其運用 10.3 指數(shù)生成函數(shù)及其運用指數(shù)生成函數(shù)及其運用 10.4 Catalan數(shù)與數(shù)與Stirling數(shù)數(shù)10.1 遞推方程及其運用遞推方程及其運用 10.1.1 遞推方程的定義及實例遞推方程的定義及實例 10.1.2 常系數(shù)線性齊次遞推方程的求解常系數(shù)線性齊次遞推方程的求解 10.1.3 常系數(shù)線性非齊次遞推方程的求解常系數(shù)線性非齊次遞推方程的求解 10.1.4 遞推方程的其他解法遞推方程的其他解法

2、 10.1.5 遞推方程與遞歸算法遞推方程與遞歸算法遞推方程的定義遞推方程的定義定義定義10.1 設(shè)序列設(shè)序列 a0, a1, , an, , 簡記為簡記為 an . 一個把一個把 an 與與某些個某些個ai (i0實例實例解解 H(k) = 2 H(k1) + 2k1 H(1) = 1 令令 H*(k) = P1k2k + P2 , 解得解得 P1=P2=1 H*(k) = k2k + 1通解通解 H(k) = c 2k + k2k + 1 代入初值得代入初值得 c = 1 H(k) = 2k + k2k +1 W(n) = n log n n + 1 0 (1)2 , 1 ) /2 (2

3、)(WnnnWnWk例例14 14 歸并排序歸并排序迭代歸納法迭代歸納法歸并排序歸并排序 0 (1)2 , 1 ) /2 (2 )(WnnnWnWk例例15151log122)12.22(2(1)2.122222)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkWWWWWWnWkkkkkkkkkkkkkkkkkkkkkk解解迭代歸納法迭代歸納法錯位陳列錯位陳列例例16 Dn = (n1)(Dn1 + Dn2) 0,)1()1(2)1(.)1(112122211 DnDDDDDnDnDDnnnnnnnnn解：解：!1)

4、1(.! 21! 111 !)1()1(.)1(4).1()1(3).1(2).1(.)1()1()1)(1()2)(1()1()1(13211232nnnnnnnDnnnnnDnnnnDnnDnnnnnnnnnn )log()()(log31.1112)1(31.1111)1(1)()()1()1()()()1(2)1()1()()1()(2)1()1()(2)(212211nnOnTnOnncTnncncnnTnnTnOnTnnnTnOnTnTnnnTnciTnTncniTnnTnini 差消法差消法化簡遞推方程化簡遞推方程 0)1(2),()(2)(11TnnOiTnnTni例例1717

5、)(log2ln)1ln(ln131.1111212nOnxdxxnnnn 積分近似積分近似遞歸樹遞歸樹二分歸并排序二分歸并排序T(n)n-1T(n/2) T(n/2)n/2-1 n/2-1T(n/4) T(n/4) T(n/4) T(n/4)n/4-1 n/4-1 n/4-1 n/4-1 .1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 T(n) = nk (1+2+2k1) = nk (2k 1) = n log n n + 1 n1n2n4. n2k1k層層knnnTnT2 , 1 ) /2 (2 )( (1) T(n)=C, 左邊左邊=O(1)嘗試法嘗試法1)(2)(1

6、1 niTnnTni)(1221)1(2nOnnCCnnCn 右右邊邊1)1(1)1(12)1)(11(21211 cncnncnnnncncinni右邊右邊例例18 (2) T(n)=cn, 左邊左邊=cn, 嘗試法嘗試法(續(xù)續(xù))(321)(3212223112nOncnnOcnnncinni 右右邊邊)(log)2ln21(log1)log(2ln4log221log22211nOncncnnnnOnnnncniincni 右邊右邊(3) T(n)=cn2, 左邊左邊=cn2(4) T(n)=cnlogn , 左邊左邊=cnlogn )442ln24(2ln1)4ln2(2ln14ln22

7、ln1ln2lnlog2222222 nnnxxxxdxxxdxxnnn積分近似積分近似)log(2ln4log2log2211nnOnnniini ankbbnaaloglog 分治戰(zhàn)略與遞歸算法分治戰(zhàn)略與遞歸算法n為輸入規(guī)模，為輸入規(guī)模，n/b為子問題輸入規(guī)模，為子問題輸入規(guī)模，a為子問題個數(shù)，為子問題個數(shù)，d(n)為分解及綜合的代價為分解及綜合的代價)/()()/(.)/()/()/(.)()/()/()(1)1(),()/()(10221122ikiikkkkkkkkbndaandbnadbnabndabnTandbnadbnTanTTbnndbnaTnT akikiikbnabnda

8、anTlog10),/()( 分治戰(zhàn)略與遞歸算法分治戰(zhàn)略與遞歸算法(續(xù)續(xù))(1) d(n)=c 1)(log)(1)()(11)(loganOkcOkcaanOaOaacanTkakkkb 實例：實例： 二分搜索二分搜索 W(n) = W(n/2) + 1 a = 1, b = 2, d(n) = c W(n) = O(logn) 分治戰(zhàn)略與遞歸算法分治戰(zhàn)略與遞歸算法(續(xù)續(xù)) (2) d(n)=cn banObabacababacnabannOcnknbanObabacnnbacnabcnaanTakkkkkkakiikikiikbb)(1/1/1)/()log()(1/1)/()()(loglog1111實例：歸并排序?qū)嵗簹w并排序 W(n) = 2W(n/2) + n1 a = 2, b = 2, d(n) = O(n), W(n)= O(nlogn) 實例實例位乘問題位乘問題位乘問題：位乘問題：X,Y 為為 n 位二進制數(shù)，位二進制數(shù)，n=2k, 求求 XY 普通方法：普通方法：W(n)= O(n2)分治法：令分治法：令X = A2n/2+B, Y = C2n/2 +D, 那么那么 XY = AC 2n + (AD+BC)2n/2 + BD W(n)= 4 W(n/2) + cn W(1)