第二章算法的复杂性分析

1、1第二章第二章 算法的复杂性分析算法的复杂性分析 2.1 常用的函数和公式（略）常用的函数和公式（略） 2.2 算法的时间复杂性分析算法的时间复杂性分析 2.3 最好情况、最坏情况和平均情况分析最好情况、最坏情况和平均情况分析 2.4 用生成函数求解递归方程用生成函数求解递归方程 2.5 用特征方程求解递归方程用特征方程求解递归方程 2.6 用递推方法求解递归方程用递推方法求解递归方程 2.7 算法的空间复杂性算法的空间复杂性 2.8 最优算法最优算法 22.2 算法的时间复杂性分析算法的时间复杂性分析一一 循环次数的统计循环次数的统计 二二 基本操作频率的统计基本操作频率的统计 三三 计算步

2、的统计计算步的统计 3一一 循环次数的统计循环次数的统计循环次数表示乘以一个常数因子的运行时间循环次数表示乘以一个常数因子的运行时间例：计算多项式：例：计算多项式： Horner 法则改写：法则改写： 输入：存放多项式系数的数组输入：存放多项式系数的数组 A , 实数实数 x, 多项式的阶多项式的阶 n 输出：多项式的值输出：多项式的值1. float polynomial(float A ,float x,int n)2. int i; 循环控制变量循环控制变量 i 赋初值所花赋初值所花4. float value; 费的单位时间数费的单位时间数 5. for (i=n;i0;i-) 循环体

3、的平均执行时间循环体的平均执行时间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例：冒泡排序算法的执行时间例：冒泡排序算法的执行时间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. ：辅助操作的执行时间：辅助操作的执行时间 c：循环体的平均执行时间：循环体的平均执行时间算法总的执行时间算法总的执行时间 T(n) 为为 cc+c)1+)2n(+)1-n( (=)n(T-c+)1-n(n2c=)n(=25例：选手的竞技淘汰比赛例：选手的竞技淘汰比赛 有有 位选手进行竞技淘汰比赛，最后决出冠军。位选手进行竞技淘汰比赛，最后决出冠军。用如下的函数：用如下的函数： BOOL comp(Type mem1,Type mem2)模拟两位选手的比赛，胜则返回模拟两位选手的比赛，胜则返回 T

5、RUE，否则返回，否则返回 FALSE假定可以在常数时间内完成函数假定可以在常数时间内完成函数 comp 的执行。的执行。 k2=n6例：选手的竞技淘汰比赛（续例：选手的竞技淘汰比赛（续 1） 输入：选手成员输入：选手成员 group , 选手个数选手个数 n输出：冠军的选手输出：冠军的选手 1. Type game(Type group ,int n) 2. 3. int j,i = n; while 循环体共执行循环体共执行 k 次次 4. while (i1) for 循环体的执行次数分别为循环体的执行次数分别为 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例：选手的竞技淘汰比赛（续例：选手的竞技淘汰比赛（续 2） 函数函数 comp 可以在常数时间内完成可以在常数时间内完成算法的执行时间为：算法的执行时间为：nn+4n+2n=)n(T)21+41+21(n=k)21-1(n=k1-n=)n(=8例：洗牌例：洗牌 对对 n 张牌进行张牌进行 n 次洗牌次洗牌规则如下：规则如下： 在第在第 k 次洗牌时（次洗牌时（ k = 1,n ），）， 对第对第 i 张牌（张牌（

7、i = 1, n/k ）随机地产生一个小于）随机地产生一个小于 n 的正整数的正整数 d，互换第，互换第 i 张牌和第张牌和第 d 张牌的位置张牌的位置 9例：洗牌（续例：洗牌（续 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+) 外循环的循环体共执行外循环的循环体共执行 n 次次 7. m = n / k ; 8. for (i=1;i=m;i+) 内循环的循环体分别执行内循环的循环体分别执行 9. d = random(1,n); n, n

8、/2 , n/3 , , n/n 10. swap(Ai,Ad);11. 12. 13. 10例：洗牌（续例：洗牌（续 2） 算法的执行时间为内部算法的执行时间为内部for循环的循环体的执行次数乘以一个循环的循环体的执行次数乘以一个常数时间常数时间 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二二 基本操作频率的统计基本操作频率的统计1. 基本操作的定义基

9、本操作的定义 2. 用基本操作的执行频率估计算法的时间复杂性用基本操作的执行频率估计算法的时间复杂性 121. 基本操作的定义基本操作的定义定义：算法中的某个初等操作，如果它的最高执行频定义：算法中的某个初等操作，如果它的最高执行频 率，和所有其它初等操作的最高执行频率，相率，和所有其它初等操作的最高执行频率，相 差在一个常数因子之内，就说这个初等操作是差在一个常数因子之内，就说这个初等操作是 一个基本操作。一个基本操作。初等操作的执行频率，可正比于任何其它操作的最高初等操作的执行频率，可正比于任何其它操作的最高执行频率执行频率基本操作的选择，必须反映出该操作随着输入规模的基本操作的选择，必须

10、反映出该操作随着输入规模的增加而变化的情况增加而变化的情况132. 用基本操作的执行频率估计算法的时间复杂性用基本操作的执行频率估计算法的时间复杂性合并两个有序的子数组合并两个有序的子数组A 是一个具有是一个具有 m 个元素的整数数组，给定三个下标：个元素的整数数组，给定三个下标：p，q，r， 0p q r m，Ap Aq，Aq+1 Ar 分分别是两个以递增顺序排序的子数组。把这两个子数组按别是两个以递增顺序排序的子数组。把这两个子数组按递增顺序合并在递增顺序合并在 Ap Ar 中。中。piqjrkAB14例：合并两个有序的子数组例：合并两个有序的子数组1. void merge(int A

11、,int p,int q,int r,int m)2. 3. int *bp = new intm; / 分配缓冲区分配缓冲区,存放被排序的元素存放被排序的元素 4. int i,j,k;5. i = p; j = q + 1; k = 0;6. while (i=q & j=r) / 逐一判断两子数组的元素逐一判断两子数组的元素 7. if (A i =A j ) / 按两种情况按两种情况,把小的元素拷贝到把小的元素拷贝到8. bp k+ = A i+ ; / 缓冲区缓冲区*/9. else 10. bp k+ = A j+ ;11. 15例：合并两个有序的子数组（续例：合并两个有序

12、的子数组（续1）12. if (i=q+1) / 按两种情况按两种情况,处理其余元素处理其余元素 13. for (;j=r;j+)14. bp+ = Aj+; / 把把A j A r 拷贝到缓冲区拷贝到缓冲区 15. else16. for (;i=q;i+)17. bp+ = Ai+; / 把把AiAq拷贝到缓冲区拷贝到缓冲区 18. k = 0;19. for (i=p;i=r;i+)/ 最后最后,把数组把数组bp的内容拷贝的内容拷贝20. Ai+ = bpk+; / 到到 ApAr 21. delete bp;22. 16例：合并两个有序的子数组（续例：合并两个有序的子数组（续2）基本

13、操作的选择：基本操作的选择：1. 数组元素的赋值操作作为基本操作，操作频率：数组元素的赋值操作作为基本操作，操作频率：2 n 1）随输入规模的增大而增加）随输入规模的增大而增加 2）执行频率与其它操作的执行频率相差一个常数因子）执行频率与其它操作的执行频率相差一个常数因子 2. 数组元素的比较操作作为基本操作数组元素的比较操作作为基本操作 令两个子数组的大小分别为令两个子数组的大小分别为 n1 和和 n2，n1 + n2 = n 数组元素的比较次数，数组元素的比较次数， 最少为最少为 min(n1,n2) 次，最多为次，最多为 n 1 次。次。 算法的时间复杂性算法的时间复杂性 (n)2478

14、10 13 15 182420810 13 15 1817三三 计算步的统计计算步的统计1. 计算步计算步 定义：计算步是一个语法或语义意义上的程序段，该程序定义：计算步是一个语法或语义意义上的程序段，该程序 段的执行时间与输入实例无关。段的执行时间与输入实例无关。 例：例：flag = (a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0); a = b; 和输入规模无关。连续和输入规模无关。连续 200 个乘法操作可为一个计算步，个乘法操作可为一个计算步，n 次加法不能作为一个计算步次加法不能作为一个计算步2. 计算步的统计计算步的统计 把全局变量把全局变量 c

15、ount 嵌入实现算法的程序中，每执行一个计嵌入实现算法的程序中，每执行一个计 算步，算步， count 就加就加1。算法运行结束时，。算法运行结束时， count 的值，就的值，就 是算法所需执行的计算步数是算法所需执行的计算步数 观察计算步数随输入实例增长而增长的情况观察计算步数随输入实例增长而增长的情况182.3 最好情况、最坏情况和平均情况分析最好情况、最坏情况和平均情况分析 一一 最好情况、最坏情况和平均情况最好情况、最坏情况和平均情况 二二 最好情况和最坏情况分析最好情况和最坏情况分析 三三 平均情况分析平均情况分析 19一一 最好情况、最坏情况和平均情况最好情况、最坏情况和平均情

16、况1. 影响运行时间的因素影响运行时间的因素 问题规模的大小、输入的具体数据（算法性能除外）问题规模的大小、输入的具体数据（算法性能除外）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. 比较次数比较次数012345jia9871361889127789231178934337893566789321例：插入排序的最坏情况和最好情况分析（续）例：插入排序的最坏情况和最好情况分析（续） 最好情况的工作过程最好情况的工作过程 最坏情况的工作过程最坏情况的工作过程012345jia1367891313126361376714878159891012345jia987631188912778923667893433678945113678951-n1=i)1-n(n21=i)n(=2)n(22二二 最好情况和最坏情况分析最好情况和最

18、坏情况分析1. 线性检索算法：在线性检索算法：在 n 个已排序的元素的数组个已排序的元素的数组 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二二 最好情况和最坏情况分析最好情况和最坏情况分析线性检索算法分析：线性检索算法分析：最好情况：数组的第一

19、个元素是最好情况：数组的第一个元素是 x，其运行时间为，其运行时间为 (1)；最坏情况：数组中不存在元素，或元素是数组的最后一个最坏情况：数组中不存在元素，或元素是数组的最后一个 元素，其运行时间为元素，其运行时间为 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二二 最好情况和最坏情况分析最好情况和最坏情况分析二叉检索算法分析：二叉检索算法分析：最好情况：数组第最好情况：数组第 n/2 个元素是个元素是 x，执行一次比较操作就可结，执行一次比较操作就可结 束算法，算法的时间复杂性是束算法，算法的时间复杂性是 (1) 最坏情况：数组中不存在元素最坏情况：数组中不存在元素 x，或元素，或元素 x 是数组的第一个元是数组的第一个元 素、或最后一个元素素、或最后一个元素 第第

21、 1 次比较时，数组元素个数为次比较时，数组元素个数为 n 个个 第第 2 次比较时，数组元素个数为次比较时，数组元素个数为 个个 第第 j 次比较时，数组元素个数为次比较时，数组元素个数为 个个 设第设第 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二二 最好情况和最坏情况分析最好情况和最坏情况分析最坏情况：最坏情况： 数组中不存在元素数组中不存在元素 x，或元素，或元素 x 是数组的最后一个元素是数组的最后一个元素 时间复杂性：时间复杂性：O(n)、(logn)最好情况：最好情况： 元素元素 x 是数组的第一个元素、是数组的第一

23、个元素、 时间复杂性：时间复杂性： O(logn)、(1)28三三 平均情况分析平均情况分析1. 插入排序算法的平均情况分析插入排序算法的平均情况分析2. 冒泡排序算法的下界平均情况分析冒泡排序算法的下界平均情况分析 291. 插入排序算法的平均情况分析插入排序算法的平均情况分析数组中的元素为数组中的元素为 ，n 个元素共有个元素共有 n! 种排列，假定，每一种排列的概率相同。种排列，假定，每一种排列的概率相同。前面前面 i 1 个元素已按递增顺序排序，把元素个元素已按递增顺序排序，把元素 插入到合适插入到合适位置的位置的 i 种可能：种可能：j = 1： 是序列中最小的，需执行是序列中最小的

24、，需执行 i 1 次比较；次比较；j = 2： 是这个序列中第二小的，仍需执行是这个序列中第二小的，仍需执行 i 1 次比较；次比较；j = 3： 是这个序列中第三小的，需执行是这个序列中第三小的，需执行 i 2 次比较；次比较；j = i： 是这个序列中最大的，需执行是这个序列中最大的，需执行1次比较。次比较。当当 2 j i 时，算法需执行的比较次数为时，算法需执行的比较次数为 i j + 1 x,x,xn21ji ,nj , i1,xxjiixixixixix30插入排序算法的平均情况分析（续插入排序算法的平均情况分析（续1） i 种可能性的概率种可能性的概率 。元素。元素 插入到合适的

25、位置的平均比较插入到合适的位置的平均比较次数次数 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插入排序算法的平均情况分析（续插入排序算法的平均情况分析（续2）把把 插入到序列中的合适位置，所需的平均比插入到序列中的合适位置，所需的平均比较总次数较总次数 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. 冒泡排序算法的下界平均情况分析冒泡排序算法的下界平均情况分析定义：设定义：设 是集合是集合 1,2,n 的一个排列，如果的一个排列，如果 i a)a,a(ji33冒泡排序算法的下界平均情况分析（续冒泡排序算法的下界平均情况分析（续 1）例：集合例：集合 A = 1,2,3 有如下种有如下种 3! 种排列：种排列： 排排 列列 逆序数目逆序数目k1 2 301 3 21 2 1 312 3 123 1 223 2 13令令 S(k) 是逆序个数为是逆序个数为 k 时的排列数目，则有：时的排列数目，则有： S(0)

27、 = 1 S(1) = 2 S(2) = 2 S(3) = 1具有具有 3 个元素集合的逆序的平均个数为：个元素集合的逆序的平均个数为：5.1=)3)3(S+2)2(S+1)1(S+0)0(S(!31=)3(mean34冒泡排序算法的下界平均情况分析（续冒泡排序算法的下界平均情况分析（续 2）考虑考虑 n 个元素的集合的所有排列：个元素的集合的所有排列：最好的情况：所有的元素都已顺序排列，该排列的逆序个数最好的情况：所有的元素都已顺序排列，该排列的逆序个数 为为 0；最坏的情况：所有的元素都是逆序排列，该排列的逆序个数最坏的情况：所有的元素都是逆序排列，该排列的逆序个数 为为 n(n-1)/2

28、。逆序的平均个数为：逆序的平均个数为：)k(Sk!n1=)n(mean2/ )1-n(n0=k-n1=k21k=)1n(n41=-352.4 用生成函数求解递归方程用生成函数求解递归方程 一一 生成函数及其性质生成函数及其性质 二二 用生成函数求解递归方程用生成函数求解递归方程 36一一 生成函数及其性质生成函数及其性质 1. 生成函数的定义生成函数的定义 2. 生成函数的性质生成函数的性质 371. 生成函数的定义生成函数的定义定义：令定义：令 是一个实数序列，构造如下的函数：是一个实数序列，构造如下的函数： 则函数则函数 G(z) 称为序列称为序列 的生成函数的生成函数例：函数例：函数则函

29、数则函数 便是序列便是序列 的生成函数的生成函数,a,a,a210k0=kk2210za=+za+za+a=)z(G,a,a,a210nnn22n1n0nnxC+xC+xC+C=)x+1(nn2n1n0nC,C,C,Cn)x+1(382. 生成函数的性质生成函数的性质1）加法）加法 和和 分别是序列分别是序列 及及 的生成函数，则的生成函数，则 是序列是序列 的生成函数的生成函数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、序列是序列 的生成函数，则的生成函数，则 是序列是序列 的生成函数的生成函数k0=kkza=)z(G,a,a,a210km=km-kmza=)z(Gz,a,a,a,0,0210403）乘法）乘法 和和 分别是序列分别是序列 及及 的生成函数，则的生成函数，则 是序列是序列 的生成函数，其中的生成函数，其中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 变换变换 是序列是序列 的生成函数，则的生成函数，则 是序列是序列 的生成函数的生成函数 是序列是序列 的生成函数的生成函数 用生成函数求解汉诺塔问题的递归方程用生成函数求解汉诺塔问题的递归方程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去掉级数中的奇数项和偶数项去掉级数中的奇数项和偶数项 +za+za+a=) )z(G+)z(G(2144220-+za+za+za=)

32、)z(G)z(G(2155331-43二二 用生成函数求解递归方程用生成函数求解递归方程1. 汉诺塔（汉诺塔（Hanoi）问题的递归方程）问题的递归方程2. 用生成函数求解汉诺塔问题的递归方程用生成函数求解汉诺塔问题的递归方程3. 菲波那契序列问题的递归方程菲波那契序列问题的递归方程4. 用生成函数求解菲波那契序列问题的递归方程用生成函数求解菲波那契序列问题的递归方程441. 汉诺塔（汉诺塔（Hanoi）问题的递归方程）问题的递归方程汉诺塔（汉诺塔（Hanoi）问题：）问题：h(n)：移动：移动 n 个金盘的移动次数个金盘的移动次数 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) 作系数，构造生成函数：作系数，构造生成函数：+x)3(h+x)2(h+x)1(h=)x(G321=kkx)k(h=452. 用生成函数求解汉诺塔问题的递归方程用生成函数求解汉诺塔问题的递归方程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用生成函数求解汉诺塔问题的递归方程（续）用生成函数求解汉诺塔问题的递归方程（续） 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 阶常系数线性齐次递归方程阶常系数线性齐次递归方程 二二 k 阶常系数线性非齐次递归方程阶常系数线性非齐次递归方程 48一一 k 阶常系数线性齐次递归方程阶常系数线性齐次递归方程 1. k 阶常系数线性齐次递归方程及其特征方程阶常系数线性齐次递归方程及其特征方程 2. k 阶常系数线性齐次递归方程的求解过程阶常系数线性齐次递归方程的求解过程 491. k 阶常系数线性齐次递归方程及其特征方程阶常系数线性齐次递归方程及其特征方程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 阶常系数线性齐次递归方程的求解过程阶常系数线性齐次递归方程的求解过程1）特征方程有）特征方程有 k 个互不相同的根个互不相同的根 ，通解为：，通解为：2）特征方程的）特征方程的 k 个根中有个根中有 r 个重根个重根 通解为：通解为：3）求解过程：）求解过程： 把递归方程的初始条件代入通解，建立联立方程，确定系数把递归方程的初始条件代入通解，建立联立方程，确定系数

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例子（续）例子（续）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 阶常系数线性非齐次递归方程阶常系数线性非齐次递归方程 1. 非齐次递归方程及其通解的形式非齐次递归方程及其通解的形式 2. 非齐次递归方程特解的求取非齐次递归方程特解的求取 3. 非齐次递归方程通解的求取非齐次递归方程通解的求取 4. 例子例子 541. 非齐次递归方程及其通解的形式非齐次递归方程及其通解的形式1）递归方程的形式）递归方程的形式 ：2）通解形式：）通解

40、形式： 对应齐次递归方程的通解对应齐次递归方程的通解 原非齐次递归方程的特解原非齐次递归方程的特解 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 次多项式次多项式 是常数是常数 特解也是的次多项式特解也是的次多项式 待定系数待定系数 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) 是如下形式的指数函数是如下形式的指数函数 是常数是常数 a 不是特征方程的重根，特解为不是特征方程的重根，特解为 a 是特征方程的是特征方程的 r 重根，特解为重根，特解为 为待定系数为待定系数 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）求对应齐次递归方程的通解）求对应齐次递归方程的通解 2）求非齐次递归方程的特解）求非齐次递归方程的特

42、解 把带有待定系数的特解代入原非齐次递归方程把带有待定系数的特解代入原非齐次递归方程 比较方程两边系数，列出待定系数的联立方程比较方程两边系数，列出待定系数的联立方程 解联立方程，求出待定系数解联立方程，求出待定系数3）求非齐次递归方程的通解）求非齐次递归方程的通解 把初始条件代入通解，列出通解中待定系数的联立方程把初始条件代入通解，列出通解中待定系数的联立方程 解联立方程，求出待定系数解联立方程，求出待定系数 )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对应的齐次递归方程的

43、特征方程对应的齐次递归方程的特征方程 ： 特征根特征根 ：对应的齐次递归方程的通解对应的齐次递归方程的通解 ：令非齐次递归方程的特解令非齐次递归方程的特解 ：代入原递归方程，得代入原递归方程，得 ：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例子（续）例子（续）得到联立方程得到联立方程 ：解得：解得：非齐次递归方程的通解非齐次递归方程的通解 ：代入初始条件：代入初始条件：通解通解 ：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 用递推方法求解递归方程用递推方法求解递归方程 一一 用递推法求解非齐次递归方程用递推法求解非齐次递归方程 二二 用递推法求解变系数递归方程用递推法求解变系数递归方程 三三 换名换名 61一一 用递推法求解非齐次递归方程用递推法求解非齐次递归方程非齐次递归方程：非齐次递归方程： f(n) = bf(n 1) + g(n) f(0) = c其中，其中，b、c 为常数为常数)n(g+) )1n(g+)2n( fb(b=)n( f-)n(g+)1n(gb+)2n( fb=2-)n(g+)1n(gb+) )2n(g+)3n( fb(