第二章算法的復雜性分析

1、1第二章第二章 算法的復雜性分析算法的復雜性分析 2.1 常用的函數(shù)和公式（略）常用的函數(shù)和公式（略） 2.2 算法的時間復雜性分析算法的時間復雜性分析 2.3 最好情況、最壞情況和平均情況分析最好情況、最壞情況和平均情況分析 2.4 用生成函數(shù)求解遞歸方程用生成函數(shù)求解遞歸方程 2.5 用特征方程求解遞歸方程用特征方程求解遞歸方程 2.6 用遞推方法求解遞歸方程用遞推方法求解遞歸方程 2.7 算法的空間復雜性算法的空間復雜性 2.8 最優(yōu)算法最優(yōu)算法 22.2 算法的時間復雜性分析算法的時間復雜性分析一一 循環(huán)次數(shù)的統(tǒng)計循環(huán)次數(shù)的統(tǒng)計 二二 基本操作頻率的統(tǒng)計基本操作頻率的統(tǒng)計 三三 計算步

2、的統(tǒng)計計算步的統(tǒng)計 3一一 循環(huán)次數(shù)的統(tǒng)計循環(huán)次數(shù)的統(tǒng)計循環(huán)次數(shù)表示乘以一個常數(shù)因子的運行時間循環(huán)次數(shù)表示乘以一個常數(shù)因子的運行時間例：計算多項式：例：計算多項式： Horner 法則改寫：法則改寫： 輸入：存放多項式系數(shù)的數(shù)組輸入：存放多項式系數(shù)的數(shù)組 A , 實數(shù)實數(shù) x, 多項式的階多項式的階 n 輸出：多項式的值輸出：多項式的值1. float polynomial(float A ,float x,int n)2. int i; 循環(huán)控制變量循環(huán)控制變量 i 賦初值所花賦初值所花4. float value; 費的單位時間數(shù)費的單位時間數(shù) 5. for (i=n;i0;i-) 循環(huán)體

3、的平均執(zhí)行時間循環(huán)體的平均執(zhí)行時間6. value = Ai * x + Ai-1; 7. return value; 8. 011n1-nnna+xa+xa+xa=)x(P011-nna+x)a+x)a+xa(=)x(P1c2cnc+c=)n(T21)n(=4例：冒泡排序算法的執(zhí)行時間例：冒泡排序算法的執(zhí)行時間1. template 13. void swap(Type &x,Type &y)2. void bubble(Type A,int n) 14. Type temp;3. int i,k; 16. temp = x;5. for (k=n-1;k0;k-) 17.

4、x = y;6. for (i=0;i Ai+1) 19. 8. swap(Ai,Ai+1);9. ：輔助操作的執(zhí)行時間：輔助操作的執(zhí)行時間 c：循環(huán)體的平均執(zhí)行時間：循環(huán)體的平均執(zhí)行時間算法總的執(zhí)行時間算法總的執(zhí)行時間 T(n) 為為 cc+c)1+)2n(+)1-n( (=)n(T-c+)1-n(n2c=)n(=25例：選手的競技淘汰比賽例：選手的競技淘汰比賽 有有 位選手進行競技淘汰比賽，最后決出冠軍。位選手進行競技淘汰比賽，最后決出冠軍。用如下的函數(shù)：用如下的函數(shù)： BOOL comp(Type mem1,Type mem2)模擬兩位選手的比賽，勝則返回模擬兩位選手的比賽，勝則返回 T

5、RUE，否則返回，否則返回 FALSE假定可以在常數(shù)時間內(nèi)完成函數(shù)假定可以在常數(shù)時間內(nèi)完成函數(shù) comp 的執(zhí)行。的執(zhí)行。 k2=n6例：選手的競技淘汰比賽（續(xù)例：選手的競技淘汰比賽（續(xù) 1） 輸入：選手成員輸入：選手成員 group , 選手個數(shù)選手個數(shù) n輸出：冠軍的選手輸出：冠軍的選手 1. Type game(Type group ,int n) 2. 3. int j,i = n; while 循環(huán)體共執(zhí)行循環(huán)體共執(zhí)行 k 次次 4. while (i1) for 循環(huán)體的執(zhí)行次數(shù)分別為循環(huán)體的執(zhí)行次數(shù)分別為 5. i = i / 2; n/2，n/4，1 6. for (j=0;j

6、i;j+) 7. if (comp(group j+i ,group j ); 8. group j = group j+i ; 9. 10. return group0;11. 7例：選手的競技淘汰比賽（續(xù)例：選手的競技淘汰比賽（續(xù) 2） 函數(shù)函數(shù) comp 可以在常數(shù)時間內(nèi)完成可以在常數(shù)時間內(nèi)完成算法的執(zhí)行時間為：算法的執(zhí)行時間為：nn+4n+2n=)n(T)21+41+21(n=k)21-1(n=k1-n=)n(=8例：洗牌例：洗牌 對對 n 張牌進行張牌進行 n 次洗牌次洗牌規(guī)則如下：規(guī)則如下： 在第在第 k 次洗牌時（次洗牌時（ k = 1,n ），）， 對第對第 i 張牌（張牌（

7、i = 1, n/k ）隨機地產(chǎn)生一個小于）隨機地產(chǎn)生一個小于 n 的正整數(shù)的正整數(shù) d，互換第，互換第 i 張牌和第張牌和第 d 張牌的位置張牌的位置 9例：洗牌（續(xù)例：洗牌（續(xù) 1） 1. template 2. void shuffle(Type A ,int n) 3. int i,k,m,d; 5. random_seed(0); 6. for (k=1;k=n;k+) 外循環(huán)的循環(huán)體共執(zhí)行外循環(huán)的循環(huán)體共執(zhí)行 n 次次 7. m = n / k ; 8. for (i=1;i=m;i+) 內(nèi)循環(huán)的循環(huán)體分別執(zhí)行內(nèi)循環(huán)的循環(huán)體分別執(zhí)行 9. d = random(1,n); n, n

8、/2 , n/3 , , n/n 10. swap(Ai,Ad);11. 12. 13. 10例：洗牌（續(xù)例：洗牌（續(xù) 2） 算法的執(zhí)行時間為內(nèi)部算法的執(zhí)行時間為內(nèi)部for循環(huán)的循環(huán)體的執(zhí)行次數(shù)乘以一個循環(huán)的循環(huán)體的執(zhí)行次數(shù)乘以一個常數(shù)時間常數(shù)時間 n1=ii /n=)n(Ti /ni /n1)- i /n(n1=in1=in1=i1+nln(1/i)1+n(lnn=1i1+elognlog) i /1(elog)1+n(logn1=in+elognlognn/in-elog) 1+nlog(nn1=i)nlogn(=)n(T11二二 基本操作頻率的統(tǒng)計基本操作頻率的統(tǒng)計1. 基本操作的定義基

9、本操作的定義 2. 用基本操作的執(zhí)行頻率估計算法的時間復雜性用基本操作的執(zhí)行頻率估計算法的時間復雜性 121. 基本操作的定義基本操作的定義定義：算法中的某個初等操作，如果它的最高執(zhí)行頻定義：算法中的某個初等操作，如果它的最高執(zhí)行頻 率，和所有其它初等操作的最高執(zhí)行頻率，相率，和所有其它初等操作的最高執(zhí)行頻率，相 差在一個常數(shù)因子之內(nèi)，就說這個初等操作是差在一個常數(shù)因子之內(nèi)，就說這個初等操作是 一個基本操作。一個基本操作。初等操作的執(zhí)行頻率，可正比于任何其它操作的最高初等操作的執(zhí)行頻率，可正比于任何其它操作的最高執(zhí)行頻率執(zhí)行頻率基本操作的選擇，必須反映出該操作隨著輸入規(guī)模的基本操作的選擇，必須

10、反映出該操作隨著輸入規(guī)模的增加而變化的情況增加而變化的情況132. 用基本操作的執(zhí)行頻率估計算法的時間復雜性用基本操作的執(zhí)行頻率估計算法的時間復雜性合并兩個有序的子數(shù)組合并兩個有序的子數(shù)組A 是一個具有是一個具有 m 個元素的整數(shù)數(shù)組，給定三個下標：個元素的整數(shù)數(shù)組，給定三個下標：p，q，r， 0p q r m，Ap Aq，Aq+1 Ar 分分別是兩個以遞增順序排序的子數(shù)組。把這兩個子數(shù)組按別是兩個以遞增順序排序的子數(shù)組。把這兩個子數(shù)組按遞增順序合并在遞增順序合并在 Ap Ar 中。中。piqjrkAB14例：合并兩個有序的子數(shù)組例：合并兩個有序的子數(shù)組1. void merge(int A

11、,int p,int q,int r,int m)2. 3. int *bp = new intm; / 分配緩沖區(qū)分配緩沖區(qū),存放被排序的元素存放被排序的元素 4. int i,j,k;5. i = p; j = q + 1; k = 0;6. while (i=q & j=r) / 逐一判斷兩子數(shù)組的元素逐一判斷兩子數(shù)組的元素 7. if (A i =A j ) / 按兩種情況按兩種情況,把小的元素拷貝到把小的元素拷貝到8. bp k+ = A i+ ; / 緩沖區(qū)緩沖區(qū)*/9. else 10. bp k+ = A j+ ;11. 15例：合并兩個有序的子數(shù)組（續(xù)例：合并兩個有序

12、的子數(shù)組（續(xù)1）12. if (i=q+1) / 按兩種情況按兩種情況,處理其余元素處理其余元素 13. for (;j=r;j+)14. bp+ = Aj+; / 把把A j A r 拷貝到緩沖區(qū)拷貝到緩沖區(qū) 15. else16. for (;i=q;i+)17. bp+ = Ai+; / 把把AiAq拷貝到緩沖區(qū)拷貝到緩沖區(qū) 18. k = 0;19. for (i=p;i=r;i+)/ 最后最后,把數(shù)組把數(shù)組bp的內(nèi)容拷貝的內(nèi)容拷貝20. Ai+ = bpk+; / 到到 ApAr 21. delete bp;22. 16例：合并兩個有序的子數(shù)組（續(xù)例：合并兩個有序的子數(shù)組（續(xù)2）基本

13、操作的選擇：基本操作的選擇：1. 數(shù)組元素的賦值操作作為基本操作，操作頻率：數(shù)組元素的賦值操作作為基本操作，操作頻率：2 n 1）隨輸入規(guī)模的增大而增加）隨輸入規(guī)模的增大而增加 2）執(zhí)行頻率與其它操作的執(zhí)行頻率相差一個常數(shù)因子）執(zhí)行頻率與其它操作的執(zhí)行頻率相差一個常數(shù)因子 2. 數(shù)組元素的比較操作作為基本操作數(shù)組元素的比較操作作為基本操作 令兩個子數(shù)組的大小分別為令兩個子數(shù)組的大小分別為 n1 和和 n2，n1 + n2 = n 數(shù)組元素的比較次數(shù)，數(shù)組元素的比較次數(shù)， 最少為最少為 min(n1,n2) 次，最多為次，最多為 n 1 次。次。 算法的時間復雜性算法的時間復雜性 (n)2478

14、10 13 15 182420810 13 15 1817三三 計算步的統(tǒng)計計算步的統(tǒng)計1. 計算步計算步 定義：計算步是一個語法或語義意義上的程序段，該程序定義：計算步是一個語法或語義意義上的程序段，該程序 段的執(zhí)行時間與輸入實例無關(guān)。段的執(zhí)行時間與輸入實例無關(guān)。 例：例：flag = (a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0); a = b; 和輸入規(guī)模無關(guān)。連續(xù)和輸入規(guī)模無關(guān)。連續(xù) 200 個乘法操作可為一個計算步，個乘法操作可為一個計算步，n 次加法不能作為一個計算步次加法不能作為一個計算步2. 計算步的統(tǒng)計計算步的統(tǒng)計 把全局變量把全局變量 c

15、ount 嵌入實現(xiàn)算法的程序中，每執(zhí)行一個計嵌入實現(xiàn)算法的程序中，每執(zhí)行一個計 算步，算步， count 就加就加1。算法運行結(jié)束時，。算法運行結(jié)束時， count 的值，就的值，就 是算法所需執(zhí)行的計算步數(shù)是算法所需執(zhí)行的計算步數(shù) 觀察計算步數(shù)隨輸入實例增長而增長的情況觀察計算步數(shù)隨輸入實例增長而增長的情況182.3 最好情況、最壞情況和平均情況分析最好情況、最壞情況和平均情況分析 一一 最好情況、最壞情況和平均情況最好情況、最壞情況和平均情況 二二 最好情況和最壞情況分析最好情況和最壞情況分析 三三 平均情況分析平均情況分析 19一一 最好情況、最壞情況和平均情況最好情況、最壞情況和平均情

16、況1. 影響運行時間的因素影響運行時間的因素 問題規(guī)模的大小、輸入的具體數(shù)據(jù)（算法性能除外）問題規(guī)模的大小、輸入的具體數(shù)據(jù)（算法性能除外）2. 算法時間復雜性的三種分析算法時間復雜性的三種分析 最壞情況的分析、平均情況的分析、和最好情況的分最壞情況的分析、平均情況的分析、和最好情況的分 析析 20例：插入排序的最壞情況和最好情況分析例：插入排序的最壞情況和最好情況分析1. void insert_sort(int A ,int n)2. int a,i,j; 一般情況的工作過程一般情況的工作過程4. for (i=1;i=0 & Aja) 8. A j+1 = A j ;9. j- -

17、;10. 11. A j+1 = a;12. 13. 比較次數(shù)比較次數(shù)012345jia9871361889127789231178934337893566789321例：插入排序的最壞情況和最好情況分析（續(xù)）例：插入排序的最壞情況和最好情況分析（續(xù)） 最好情況的工作過程最好情況的工作過程 最壞情況的工作過程最壞情況的工作過程012345jia1367891313126361376714878159891012345jia987631188912778923667893433678945113678951-n1=i)1-n(n21=i)n(=2)n(22二二 最好情況和最壞情況分析最好情況和最

18、壞情況分析1. 線性檢索算法：在線性檢索算法：在 n 個已排序的元素的數(shù)組個已排序的元素的數(shù)組 A 中，用中，用 線性檢索算法檢索元素線性檢索算法檢索元素 x輸出：若輸出：若x = Aj,0jn-1,輸出輸出j,否則輸出否則輸出-1 1 int linear_search(int A,int n,int x); 2 int j = 0; 4 while (jn & x!=Aj) 5 j+; 6 if (jn) 7 return j; 8 else 9 return -1;10 23二二 最好情況和最壞情況分析最好情況和最壞情況分析線性檢索算法分析：線性檢索算法分析：最好情況：數(shù)組的第一

19、個元素是最好情況：數(shù)組的第一個元素是 x，其運行時間為，其運行時間為 (1)；最壞情況：數(shù)組中不存在元素，或元素是數(shù)組的最后一個最壞情況：數(shù)組中不存在元素，或元素是數(shù)組的最后一個 元素，其運行時間為元素，其運行時間為 O(n)、(n)、 (n)24二二 最好情況和最壞情況分析最好情況和最壞情況分析2. 二叉檢索算法：二叉檢索算法： 1 int binary_search(int A,int n,int x) 2 int mid,low = 0,high = n 1,j = -1; 4 while (low=high & j0) 5 mid = (low + high) / 2; 6 i

20、f (x=Amid) j = mid; 7 else if (xAmid) high = mid 1; 8 else low = mid + 1; 9 10 return j;11 25二二 最好情況和最壞情況分析最好情況和最壞情況分析二叉檢索算法分析：二叉檢索算法分析：最好情況：數(shù)組第最好情況：數(shù)組第 n/2 個元素是個元素是 x，執(zhí)行一次比較操作就可結(jié)，執(zhí)行一次比較操作就可結(jié) 束算法，算法的時間復雜性是束算法，算法的時間復雜性是 (1) 最壞情況：數(shù)組中不存在元素最壞情況：數(shù)組中不存在元素 x，或元素，或元素 x 是數(shù)組的第一個元是數(shù)組的第一個元 素、或最后一個元素素、或最后一個元素 第第

21、 1 次比較時，數(shù)組元素個數(shù)為次比較時，數(shù)組元素個數(shù)為 n 個個 第第 2 次比較時，數(shù)組元素個數(shù)為次比較時，數(shù)組元素個數(shù)為 個個 第第 j 次比較時，數(shù)組元素個數(shù)為次比較時，數(shù)組元素個數(shù)為 個個 設(shè)第設(shè)第 j 次比較是最后一次比較，有次比較是最后一次比較，有 則：則： 算法的時間復雜性是算法的時間復雜性是 (logn)2/n12/jn12/1jn22/11jnjjn2211lognj26二二 最好情況和最壞情況分析最好情況和最壞情況分析3. 線性檢索和二叉檢索混合使用：線性檢索和二叉檢索混合使用： 1. int linear_search(int A ,int n,int x);2. int

22、 binary_search(int A ,int n,int x);3. int serach(int A ,int n,int x)4. if (n%2)=0)6. return linear_search(A,n,x);7. else8. return binary_search(A,n,x);10. 27二二 最好情況和最壞情況分析最好情況和最壞情況分析最壞情況：最壞情況： 數(shù)組中不存在元素數(shù)組中不存在元素 x，或元素，或元素 x 是數(shù)組的最后一個元素是數(shù)組的最后一個元素 時間復雜性：時間復雜性：O(n)、(logn)最好情況：最好情況： 元素元素 x 是數(shù)組的第一個元素、是數(shù)組的第一

23、個元素、 時間復雜性：時間復雜性： O(logn)、(1)28三三 平均情況分析平均情況分析1. 插入排序算法的平均情況分析插入排序算法的平均情況分析2. 冒泡排序算法的下界平均情況分析冒泡排序算法的下界平均情況分析 291. 插入排序算法的平均情況分析插入排序算法的平均情況分析數(shù)組中的元素為數(shù)組中的元素為 ，n 個元素共有個元素共有 n! 種排列，假定，每一種排列的概率相同。種排列，假定，每一種排列的概率相同。前面前面 i 1 個元素已按遞增順序排序，把元素個元素已按遞增順序排序，把元素 插入到合適插入到合適位置的位置的 i 種可能：種可能：j = 1： 是序列中最小的，需執(zhí)行是序列中最小的

24、，需執(zhí)行 i 1 次比較；次比較；j = 2： 是這個序列中第二小的，仍需執(zhí)行是這個序列中第二小的，仍需執(zhí)行 i 1 次比較；次比較；j = 3： 是這個序列中第三小的，需執(zhí)行是這個序列中第三小的，需執(zhí)行 i 2 次比較；次比較；j = i： 是這個序列中最大的，需執(zhí)行是這個序列中最大的，需執(zhí)行1次比較。次比較。當當 2 j i 時，算法需執(zhí)行的比較次數(shù)為時，算法需執(zhí)行的比較次數(shù)為 i j + 1 x,x,xn21ji ,nj , i1,xxjiixixixixix30插入排序算法的平均情況分析（續(xù)插入排序算法的平均情況分析（續(xù)1） i 種可能性的概率種可能性的概率 。元素。元素 插入到合適的

25、位置的平均比較插入到合適的位置的平均比較次數(shù)次數(shù) ixi /1iTi2=jii1+j- i+i1- i=T-1i1=jij+i1- i=)1i (21+i1-1=-i1-2i+21=1)+1- i)(1i (i21+i1-1=-31插入排序算法的平均情況分析（續(xù)插入排序算法的平均情況分析（續(xù)2）把把 插入到序列中的合適位置，所需的平均比插入到序列中的合適位置，所需的平均比較總次數(shù)較總次數(shù) T n32x,x,xn2=in2=ii)i1-2i+21(=T=T1+i1i21+)1-n(21=n1=in2=i-n1=ii11+)2)1+n(n(41+)1-n(21=n1=i2i1-)n3+n(41=1

26、+nlni1) 1+n(lnn1=inln-)n3+n(41T2)n(=2322. 冒泡排序算法的下界平均情況分析冒泡排序算法的下界平均情況分析定義：設(shè)定義：設(shè) 是集合是集合 1,2,n 的一個排列，如果的一個排列，如果 i a)a,a(ji33冒泡排序算法的下界平均情況分析（續(xù)冒泡排序算法的下界平均情況分析（續(xù) 1）例：集合例：集合 A = 1,2,3 有如下種有如下種 3! 種排列：種排列： 排排 列列 逆序數(shù)目逆序數(shù)目k1 2 301 3 21 2 1 312 3 123 1 223 2 13令令 S(k) 是逆序個數(shù)為是逆序個數(shù)為 k 時的排列數(shù)目，則有：時的排列數(shù)目，則有： S(0)

27、 = 1 S(1) = 2 S(2) = 2 S(3) = 1具有具有 3 個元素集合的逆序的平均個數(shù)為：個元素集合的逆序的平均個數(shù)為：5.1=)3)3(S+2)2(S+1)1(S+0)0(S(!31=)3(mean34冒泡排序算法的下界平均情況分析（續(xù)冒泡排序算法的下界平均情況分析（續(xù) 2）考慮考慮 n 個元素的集合的所有排列：個元素的集合的所有排列：最好的情況：所有的元素都已順序排列，該排列的逆序個數(shù)最好的情況：所有的元素都已順序排列，該排列的逆序個數(shù) 為為 0；最壞的情況：所有的元素都是逆序排列，該排列的逆序個數(shù)最壞的情況：所有的元素都是逆序排列，該排列的逆序個數(shù) 為為 n(n-1)/2

28、。逆序的平均個數(shù)為：逆序的平均個數(shù)為：)k(Sk!n1=)n(mean2/ )1-n(n0=k-n1=k21k=)1n(n41=-352.4 用生成函數(shù)求解遞歸方程用生成函數(shù)求解遞歸方程 一一 生成函數(shù)及其性質(zhì)生成函數(shù)及其性質(zhì) 二二 用生成函數(shù)求解遞歸方程用生成函數(shù)求解遞歸方程 36一一 生成函數(shù)及其性質(zhì)生成函數(shù)及其性質(zhì) 1. 生成函數(shù)的定義生成函數(shù)的定義 2. 生成函數(shù)的性質(zhì)生成函數(shù)的性質(zhì) 371. 生成函數(shù)的定義生成函數(shù)的定義定義：令定義：令 是一個實數(shù)序列，構(gòu)造如下的函數(shù)：是一個實數(shù)序列，構(gòu)造如下的函數(shù)： 則函數(shù)則函數(shù) G(z) 稱為序列稱為序列 的生成函數(shù)的生成函數(shù)例：函數(shù)例：函數(shù)則函

29、數(shù)則函數(shù) 便是序列便是序列 的生成函數(shù)的生成函數(shù),a,a,a210k0=kk2210za=+za+za+a=)z(G,a,a,a210nnn22n1n0nnxC+xC+xC+C=)x+1(nn2n1n0nC,C,C,Cn)x+1(382. 生成函數(shù)的性質(zhì)生成函數(shù)的性質(zhì)1）加法）加法 和和 分別是序列分別是序列 及及 的生成函數(shù)，則的生成函數(shù)，則 是序列是序列 的生成函數(shù)的生成函數(shù)k0=kkza=)z(Gk0=kkzb=)z(H,a,a,a210,b,b,b210k0=kkk0=kkzb+za=)z(H+)z(Gk0=kkkz)b+a(=,b+a,b+a,b+a221100392）移位）移位 是

30、序列是序列 的生成函數(shù)，則的生成函數(shù)，則 是序列是序列 的生成函數(shù)的生成函數(shù)k0=kkza=)z(G,a,a,a210km=km-kmza=)z(Gz,a,a,a,0,0210403）乘法）乘法 和和 分別是序列分別是序列 及及 的生成函數(shù)，則的生成函數(shù)，則 是序列是序列 的生成函數(shù)，其中的生成函數(shù)，其中k0=kkza=)z(Gk0=kkzb=)z(H,a,a,a210,b,b,b210)+zb+zb+b( )+za+za+a(=)z(H)z(G22102210+z)ba+ba+ba(+z)ba+ba(+ba=2021120011000 k0=kkzc=,c,c,c210knn0=kknba=

31、c-414）z 變換變換 是序列是序列 的生成函數(shù)，則的生成函數(shù)，則 是序列是序列 的生成函數(shù)的生成函數(shù) 是序列是序列 的生成函數(shù)的生成函數(shù) 用生成函數(shù)求解漢諾塔問題的遞歸方程用生成函數(shù)求解漢諾塔問題的遞歸方程k0=kkza=)z(G,a,a,a210+)zc(a+)zc(a+)zc(a+a=)zc(G332210+zac+zac+zac+a=33322210,ac,ac,a2210+zc+zc+zc+1=zc113322-zc11-,c,c,c, 13242去掉級數(shù)中的奇數(shù)項和偶數(shù)項去掉級數(shù)中的奇數(shù)項和偶數(shù)項 +za+za+a=) )z(G+)z(G(2144220-+za+za+za=)

32、)z(G)z(G(2155331-43二二 用生成函數(shù)求解遞歸方程用生成函數(shù)求解遞歸方程1. 漢諾塔（漢諾塔（Hanoi）問題的遞歸方程）問題的遞歸方程2. 用生成函數(shù)求解漢諾塔問題的遞歸方程用生成函數(shù)求解漢諾塔問題的遞歸方程3. 菲波那契序列問題的遞歸方程菲波那契序列問題的遞歸方程4. 用生成函數(shù)求解菲波那契序列問題的遞歸方程用生成函數(shù)求解菲波那契序列問題的遞歸方程441. 漢諾塔（漢諾塔（Hanoi）問題的遞歸方程）問題的遞歸方程漢諾塔（漢諾塔（Hanoi）問題：）問題：h(n)：移動：移動 n 個金盤的移動次數(shù)個金盤的移動次數(shù) n = 1 h(1) = 1 n = 2 h(2) = 2

33、h(1) + 1 n = 3 h(3) = 2 h(2) + 1遞歸方程：遞歸方程： h(n) = 2 h(n-1) + 1 h(1) = 1用用 h(n) 作系數(shù)，構(gòu)造生成函數(shù)：作系數(shù)，構(gòu)造生成函數(shù)：+x)3(h+x)2(h+x)1(h=)x(G321=kkx)k(h=452. 用生成函數(shù)求解漢諾塔問題的遞歸方程用生成函數(shù)求解漢諾塔問題的遞歸方程G(x) 2xG(x) z 變換變換 +x)3(h+x)2(h+x)1(h=)x(G321=kkx)k(h=-3232x)2(h2x)1(h2+x)3(h+x)2(h+x)1(h=+x) )2(h2)3(h(+x) )1(h2)2(h(+x)1(h=

34、32-)+x+x+1(x=+x+x+x=)x(G)x21(232-x1x=-)x21( )x1(x=)x(G-46用生成函數(shù)求解漢諾塔問題的遞歸方程（續(xù)）用生成函數(shù)求解漢諾塔問題的遞歸方程（續(xù)） A + B = 0 - 2A B = 1 解得：解得：A = - 1 B = 1 )x21( )x1(x=)x(G-)x21(B+)x1(A=)x(G-)x21( )x1(BxB+Ax2A=-)x1(1)x21(1=)x(G- )+x+x+x+1()+x2+x2+x2+1(=323322 -+x)12(+x)12(+x)12(=3322-k1=kkx)12(=-12=)n(hn-472.5 用特征方程

35、求解遞歸方程用特征方程求解遞歸方程 一一 k 階常系數(shù)線性齊次遞歸方程階常系數(shù)線性齊次遞歸方程 二二 k 階常系數(shù)線性非齊次遞歸方程階常系數(shù)線性非齊次遞歸方程 48一一 k 階常系數(shù)線性齊次遞歸方程階常系數(shù)線性齊次遞歸方程 1. k 階常系數(shù)線性齊次遞歸方程及其特征方程階常系數(shù)線性齊次遞歸方程及其特征方程 2. k 階常系數(shù)線性齊次遞歸方程的求解過程階常系數(shù)線性齊次遞歸方程的求解過程 491. k 階常系數(shù)線性齊次遞歸方程及其特征方程階常系數(shù)線性齊次遞歸方程及其特征方程1）遞歸方程的形式：）遞歸方程的形式：2）遞歸方程的特征方程）遞歸方程的特征方程 取代取代 f(n)： 兩邊分別除以兩邊分別除

36、以ki0b=) i ( f)kn( fa+)2n( fa+)1n( fa=)n( fik21-nxknk2n21n1nxa+xa+xa=x-k2k21k1ka+xa+xa=x-knx-0=axaxaxk2k21k1k-502. k 階常系數(shù)線性齊次遞歸方程的求解過程階常系數(shù)線性齊次遞歸方程的求解過程1）特征方程有）特征方程有 k 個互不相同的根個互不相同的根 ，通解為：，通解為：2）特征方程的）特征方程的 k 個根中有個根中有 r 個重根個重根 通解為：通解為：3）求解過程：）求解過程： 把遞歸方程的初始條件代入通解，建立聯(lián)立方程，確定系數(shù)把遞歸方程的初始條件代入通解，建立聯(lián)立方程，確定系數(shù)

37、，從而可求出通解，從而可求出通解 k21q,q,qnkkn22n11qc+qc+qc=)n( f1r+i1+iiq,q,q-nkkni1r1r+i1+iin1i1in11qc+q)nc+nc+c(+qc+qc=)n( f-k21c,c,c513. 例子例子1） f(n) = 6f(n 1) 11f(n 2) + 6f(n 3) f(0) = 0 f(1) = 2 f(3) = 10 特征方程：特征方程： 特征根：特征根： 通解：通解： 由初始條件得：由初始條件得： n3n213c+2c+c=0=6x11+x6x23-0=6x2+x9+x3x3x223-0=)3x( )2x( )1x(-3=q2

38、=q1=q321n33n22n11qc+qc+qc=)n( f0=c+c+c=)0( f3212=c3+c2+c=)1( f32110=c9+c4+c=)2( f3212=c2=c0=c321-)23(2=)n( fnn-52例子（續(xù)）例子（續(xù)）2） f(n) = 5f(n 1) 7f(n 2) +3f(n 3) f(0) = 1 f(1) = 2 f(3) = 7 特征方程：特征方程： 特征根：特征根： 通解：通解： 由初始條件得：由初始條件得： 3=q1=q1=q3211=c+c=)0( f312=c3+c+c=)1( f3217=c9+c2+c=)2( f3211=c1=c0=c321-

39、n3=)n( fn-0=3x7+x5x23-0=3x+x6+2x-x3x223-0=)1+x2x( )3x(2-0=)3x( )1x( )1x(-n33n121qc+q)nc+c(=)n( fn3213c+nc+c=53二二 k 階常系數(shù)線性非齊次遞歸方程階常系數(shù)線性非齊次遞歸方程 1. 非齊次遞歸方程及其通解的形式非齊次遞歸方程及其通解的形式 2. 非齊次遞歸方程特解的求取非齊次遞歸方程特解的求取 3. 非齊次遞歸方程通解的求取非齊次遞歸方程通解的求取 4. 例子例子 541. 非齊次遞歸方程及其通解的形式非齊次遞歸方程及其通解的形式1）遞歸方程的形式）遞歸方程的形式 ：2）通解形式：）通解

40、形式： 對應(yīng)齊次遞歸方程的通解對應(yīng)齊次遞歸方程的通解 原非齊次遞歸方程的特解原非齊次遞歸方程的特解 ki0b=) i ( f)n(g+)kn( fa+)2n( fa+)1n( fa=)n( fik21-)n(*f+)n( f=)n( f)n( f)n(*f552. 非齊次遞歸方程特解的求取非齊次遞歸方程特解的求取1）g(n) 是是 n 的的 m 次多項式次多項式 是常數(shù)是常數(shù) 特解也是的次多項式特解也是的次多項式 待定系數(shù)待定系數(shù) 1+mm1m2m1b+nb+nb+nb=)n(g-1+m,2,1=i ,bi1+mm1m2m1A+nA+nA+nA=)n(*f-1+m,2,1=i ,Ai562）g

41、(n) 是如下形式的指數(shù)函數(shù)是如下形式的指數(shù)函數(shù) 是常數(shù)是常數(shù) a 不是特征方程的重根，特解為不是特征方程的重根，特解為 a 是特征方程的是特征方程的 r 重根，特解為重根，特解為 為待定系數(shù)為待定系數(shù) 1+m,2,1=i ,bi1+m,2,1=i ,Ain1+mm1m2m1a)b+nb+nb+nb(=)n(g-n1+mm1m2m1a)A+nA+nA+nA(=)n(*f-nr1+mm1m2m1an)A+nA+nA+nA(=)n(*f-573. 非齊次遞歸方程通解的求取非齊次遞歸方程通解的求取1）求對應(yīng)齊次遞歸方程的通解）求對應(yīng)齊次遞歸方程的通解 2）求非齊次遞歸方程的特解）求非齊次遞歸方程的特

42、解 把帶有待定系數(shù)的特解代入原非齊次遞歸方程把帶有待定系數(shù)的特解代入原非齊次遞歸方程 比較方程兩邊系數(shù)，列出待定系數(shù)的聯(lián)立方程比較方程兩邊系數(shù)，列出待定系數(shù)的聯(lián)立方程 解聯(lián)立方程，求出待定系數(shù)解聯(lián)立方程，求出待定系數(shù)3）求非齊次遞歸方程的通解）求非齊次遞歸方程的通解 把初始條件代入通解，列出通解中待定系數(shù)的聯(lián)立方程把初始條件代入通解，列出通解中待定系數(shù)的聯(lián)立方程 解聯(lián)立方程，求出待定系數(shù)解聯(lián)立方程，求出待定系數(shù) )n( f)n(*f)n(*f+)n( f=)n( f584. 例子例子 f(n) = 7f(n 1) 10f(n 2) + 4 f(0) = 1 f(1) = 2對應(yīng)的齊次遞歸方程的

43、特征方程對應(yīng)的齊次遞歸方程的特征方程 ： 特征根特征根 ：對應(yīng)的齊次遞歸方程的通解對應(yīng)的齊次遞歸方程的通解 ：令非齊次遞歸方程的特解令非齊次遞歸方程的特解 ：代入原遞歸方程，得代入原遞歸方程，得 ：2n0=10+x7x2-0=)5x( )2x(-5=q2=q21n2n15c+2c=)n( f3221A+nA+nA=)n(*f2322132213221n4=)A+)2n(A+)2n(A(10+)A+)1n(A+)1n(A(7A+nA+nA-59例子（續(xù)）例子（續(xù)）得到聯(lián)立方程得到聯(lián)立方程 ：解得：解得：非齊次遞歸方程的通解非齊次遞歸方程的通解 ：代入初始條件：代入初始條件：通解通解 ：23212

44、121n4=A4+A13A33+n)A4+A26(+nA4-4=A410=A4+A2621-0=A4+A13A33321-8712=A216=A1=A3218712+n216+n+5c+2c=)n( f2n2n11=8712+c+c=)0( f212=8320+c5+c2=)1( f2124191=c23213=c1-8712+n216+n+524191+23213=)n( f2nn-602.6 用遞推方法求解遞歸方程用遞推方法求解遞歸方程 一一 用遞推法求解非齊次遞歸方程用遞推法求解非齊次遞歸方程 二二 用遞推法求解變系數(shù)遞歸方程用遞推法求解變系數(shù)遞歸方程 三三 換名換名 61一一 用遞推法求解非齊次遞歸方程用遞推法求解非齊次遞歸方程非齊次遞歸方程：非齊次遞歸方程： f(n) = bf(n 1) + g(n) f(0) = c其中，其中，b、c 為常數(shù)為常數(shù))n(g+) )1n(g+)2n( fb(b=)n( f-)n(g+)1n(gb+)2n( fb=2-)n(g+)1n(gb+) )2n(g+)3n( fb(