第9章 复杂度及其分析 本章主要介绍下列内容（教材第一章） 1. 算法的复杂度 2. 算法分析 3. 复杂度分析 4. 展开法 5. 母函数法 6. 差分法 课时分配：第1、2节三个学时，第3、4节三个学时，第5、6节共三个学时 重点、难点：算法复杂度分析的步骤、递归算法分析及递归方程解法 第一节 算法的复杂度 一、算法 1. 介绍有关统计数据（曹书p1 引言） 2. 算法的通俗定义 （一个）算法是由有限个指令（规则）组成的有序集合（序列）。这些指令确定了解 决某一问题的一个运算序列。 3. 算法的五大特征 ① 有穷性 ② 确定性 ③ 能行性 ④ 输入 ⑤ 输出 4.求最大公因数的文字算法和高级语言算法。Cp2 5.算法与过程、程序的区别。Cp2 (有穷于无穷，描述多样性与执行多样性) 6.问题、问题实例及与算法运行的关系。p1 二、算法设计和算法分析的步骤 cp3 1.问题的陈述 2.模型的选择或拟制 3.算法设计和正确性证明 4.算法的程序实现 5.算法分析 三、评价算法的标准（p1）（详见1.2算法分析） 1．正确（算法已隐含该条） 2．易理解、易编程（上机实现）、易修改、可扩展 3．高效（节省时间与空间） 2、3条的辩证关系，谁放在首位，视具体情况而定。（ p1,p2） 四、算法复杂度定义 1．决定算法复杂度的两个因素 ① 问题实例大小 ② 实例的具体情况（数据出现的顺序及概率） 2．三种复杂度的定义 本课程重点讨论时间复杂度 3． 用三个表说明算法复杂度的重要性（p2-3） 4．○与?的定义 运算规则：○(f+g)=○(max{f,g}), ○(Kf)=○(f) 5．最佳算法的概念定义（cp6） 6．按算法复杂度对问题分类（cp6） 7．复杂度函数中的常量因子不可忽视（cp6） 第二节 算法分析 一、评价分析算法的指标（标准）见p5-7 略讲 二、复杂度的具体分析指标 1．基本运算次数 2．问题规模量化 3．平均工作量与最坏情况工作量 空间与此类似。 第三节 复杂度分析 一、如何具体确定一个完整算法的时间复杂度 1．问题实例大小的量化 2．基本运算的选择 3．分析构成算法各种成分执行时所需工作量 4．利用大○规则求总和 二、举例进一步剖析讲解 三、用一次课时间补充递推关系的差分解法，内容详见第六节（补充）。 第四节 展开法 一、如何由具体问题的算法得到形如下式的递归方程 二、介绍解递归方程 Tn= ?? ??? >+ =1n)n(daT 1nc b n 的展开法 （举例见第五节） 例12 p18 T n = ?? ? >+ = ? 1n1T2 1n1 1n 用母函数法解（定义T0=0） （教材代公式，此处直接推导） 令母函数为：G(x)=T0 + T1x+T 2 x 2 +…+T n x n +… 2x G(x)=2 T 0 x+2 T1x 2 +2 T 2 x3 +… G(x)- 2x G(x)= T0 +( T1-2 T0 ) x+( T 2 -2 T1) x 2 +… G(x)= xxxxx ???=?? 1 121 11*21 1 = nnnn xxx ∑∑∑ ?=? )12()2( T n =2n-1 展开法：T n =2 1?nT +1=2（2 2?nT +1）+1 =2 2 2?nT +2+1 = 1221 )21(1 ?=?? n n 待定系数法（差分）： ?? ? >=? = ? 112 1 1 1 nTT nT nn 特征方程： 202 ==>=? ll 齐次解： T1（n）=c*2 n 令 T 2（n）= p*1n =〉p-2p=1 =〉p=-1 =〉 特解：T 2（n）=-1 通解：Tn（n）= c*2 n -1 代入初始条件T1=1 =>1=c*2-1=>c=1 故T n =2n-1为所求解。 例13 ?? ? >+?= = ? )1(2*)1(2)( 0)1( 1 ncnunu u n 展开法见教材p11 G(x)=u1x+u 2 x 2 + …+ u n x n +… 2x G(x)=2 u1x 2 +2 u 2 x3 +…+2 u 1?n x n +2 u n x 1+n +… G(x)- 2x G(x)= u1x+( u 2 - 2 u1) x 2 +( u3 -2 u 2 ) x3 +…+( u n -2 u 1?n ) x n +… = u1x+c*2 x 2 +c*2 2 *x3 +…+c*2 1?n *x n +… = u1x+x*c*[2x+ (2x) 2 +…+ (2x) 1?n +…] = u1x+x*c* nx21 2? = xcx212 2 ? ? G(x)= 2 2 )21( 2 x cx ? =cx* x x 21 2 ? * x21 1 ? =cx 与p19相同 或 =c/2*( xx212? ) 2 公式法（待定系数）： u 1 (n)=c12n或c12n-1 特解：u 2 (n)=(p1n+ p 2 )2n 代入：(p 1n+ p 2 )2 n=2(p 1(n-1)+ p 2 )2 n-1+c*2n-1 2(p1n+ p 2 )=2p1(n-1)+2 p 2 +c ? p1=c/2 p 2为任意常数 ? u 2 (n)=(c/2*n+p) 2n =cn2n-1 (取p=0) ? u (n)= c12n+cn2n-1 由u1=0?2 c1+c=0 ? c1=-c/2 ? u (n)= -c/2*2n + cn2n-1=-c*2n-1+cn*2n-1=c(n-1) 2n-1 n全部变成N 也可以用展开法直接求解18页例13第一式，不进行变换。 例14 推导： j k j jk 2)( 1 0 ∑? = ? =k∑ ? = 1 2 k oj j -∑ ? = 1 2 k oj jj 因为k∑ ? = 1 2 k oj j =k 21 )21(20 ? ? k =(2 k -1)k ∑ ? = 1 2 k oj jj =∑ ? = 1 1 2 k j jj =21+ 2 2 +2 2 + 23 +23 +23 +… 2 2?k +2 2?k +2 2?k +…+2 2?k +… (k-2项) 2 1?k +2 1?k +2 1?k +…2 1?k +2 1?k (k-1项) = 21 )21(221 )21(2...21 )21(221 )21(2 11222211 ? ?+ ? ?++ ? ?+ ? ? ???? kkkk =(2 k -21)+(2 k -2 2 )+…+(2 k -2 2?k )+(2 k -2 1?k ) =(k-1) 2 k -[21+2 2 +…2 1?k ] =(k-1) 2 k - 21 )21(2 11 ? ? ?k =(k-1) 2 k +2-2 k =2 k (k-2)+2 所以 j k j jk 2)( 1 0 ∑? = ? =(2 k -1)k-2 k (k-2)-2=2 1+k -k-2 另1：令s=∑ = ? h 1j 1j2j =1*20 +2*21+3*2 2 +…+h*2 1?h =>2s=1*21+2*2 2 +3*23 +…+h*2 h =>s-2s=20 +21+2 2 +…+2 1?h -h*2 h = 21 )21(2 0 ? ? h - h*2 h =>s= h*2 h - 2 h +1 亦即∑ ? = ? 1h 1j 1j2j =(h-2) 2 1h? +1 两边乘2得: ∑ ? = 1h 1j j2j =(h-2) 2h+2 另2：令s(x)= ∑ = ? h 1j 1jjx 则 ∫ =dx)x(s ∑∫ = ? h 1j 1j dxjx =∑ = + h 1j j )cx( = hc x1 )x1(x h + ? ? s(x)= [ x1 )x1(x h ? ? ] ' = 2 1hh )x1( )xx)x1(x)1h(1( ? ?+?+? + ∑ = ? h 1j 1j2j =s(2) =(1-(h+1)2 h )(-1)+2-2 1h+ =(h+1) 2 h -1+2-2 1h+ =2 h (h+1-2)+1 =(h-1) 2 h +1 h代为k-1且两端同乘2得：∑ ? = 1k 0j j2j =2 2)2k(k +? 例15.①母函数： 令G(x)= T1x+T 2 x 2 +…+T n x n +… 2x G(x)=2 T 0 x+2 T1x 2 +2 T 2 x3 +…+2 T 1?n x n +2 T n x 1+n +… G(x)- 2x G(x)= 2T1x+( T 2 -2 T1) x 2 +(T3 -2 T 2 ) x3 +…+( T n -2 T 1?n ) x n +… =x+2 x 2 +3 x3 +…+n x n +…=∑ ∞ =1j jjx =x x 2 + x 2 + x3 + x3 + x3 + M x 1?n + x 1?n + x 1?n +…+ x 1?n + (n-1项) x n + x n + x n +…+ x n + x n + (n项) M x n ->0(n->∞) = x1 x? + x1x 2 ? +…+ x1 x 1n ? ? + x1x n ? +… = x1 ...x...xx n2 ? ++++ = x1 x1 x ? ? = 2)x1( x ? G(x)= x21 1? * x1 x? * x1 1? =[ x21 1? - x1 x? ][ x1 1? ] =[(2x)0 + (2x)1+…+(2x) n +…]-[x0 +x1+…+x n +…]]* x?1 1 [(21-1)x1+…+(2 n -1)x n ]*[ x0 +x1+…+x n +…] 结果中，x n的系数为： (21-1)+( 2 2 -1)+…+(2 1?n -1)+ (2 n -1) =21+ 2 2 +…+2 n -n= 21 )21(2 ?? n -n=2 `1n+ -2-n 此即 T(n)= 2 `1n+ -2-n 另：∑ ∞ =1j jjx =x∑ ∞ = ? 1j 1jjx 令G 1(x)= ∑ ∞ = ? 1j 1jjx 则 G1(x)= ∫ ′)dx)x(G( 1 = )dxjx( 1j 1j ′∑ ∫ ∞ = ? = 2)x1( 1 ? =>∑ ∞ =1j jjx =x G 1(x)= 2)x1( x ? ②展开法： T(n)=2T(n-1)+n =2(2T(n-2)+n-1)+n=2 2 T(n-2)+2(n-1)+n =2 2 (2T(n-3)+n-2)+2(n-1)+n =23 T(n-3)+ 2 2 (n-2)+2(n-1)+n M =2 1?n T(1)+ 2 2?n *2+2 3?n *3+…+20 *n =2 1?n *1+2 2?n *2+…+20 *n ∑? = ? 1 0 2)( n j jjn =2 1n+ -2-n (利用前面例14结论) ③待定系数法： T n = ?? ? >+ = ? 12 11 1 nnT n n l =2 T1(n)=c*2 n 令T 2 (n)=p1n+ p 2 则p1n+ p 2 =2 p1(n-1)+ 2p 2 +n => -p1n+2p1- p 2 =n => ?? ? ?== ?= 22 1 12 1 pp p => T 2 (n)=-n-2 =>T(n)=c*2 n -n-2 由T(1)=1有c*2-1-2=1 =>c=2 例16 T n = ?? ? >+ = ? 1 11 1 ncaT n n n ①母函数法： G(x)= T1x+T 2 x 2 +…+T n x n +… ax G(x)=aT1x 2 +aT 2 x3 +…+2 T 1?n x n +aT n x 1+n +… G(x)- ax G(x)= T1x+( T 2 -aT1) x 2 +(T3 -aT 2 ) x3 +…+( T 1+n -a T n ) x 1+n +… =x+c 2 x 2 +c3 x3 +…+c n x n +…=x+ cx1 xc 22 ? G(x)= ax1 x? + )ax1)(cx1 xc 22 ?? =x[ ax1 1? + acc? 2 *( ax1 1cx1 1 ??? )] =x* ?? ?? ?+?? ? ∑ ∑∑ ∞ = ∞ = ∞ = ])ax()cx([acc)ax( 0n 0n nn 2 0n n =x* n 0n n 2 n 2 n x)a* ac cc* ac ca(∑∞ = ? ??+ =>T n =a 1n 2 1n 2 1n a* ac cc* ac c ??? ???+ =a 1n? +c 2 * ac ac 1n1n ? ? ?? ②待定系数法： a. c≠ a: 此时c不是特征根，而 a=l => T1(n)=c1a n 令T 2 (n)=pc n => pc n =a pc 1?n + c n =>p= ac c? T(n)= c1a n + acc n ? +1 代入T(1)=1的 a)ac( ca1c 2 1 ??= =>T(n)=a 1?n + ac ac nn ? ? ?? 11 *c 2 b. c=a: 即c是原方程特征根 即 c=l => T1(n)= c1* c n 令T 2 (n)= (p1n+ p 2 ) c n代入原方程： (p1n+ p 2 ) c n =c*[ p1(n-1)+ p 2 ] c 1?n + c n => p1n+ p 2 = p1n- p1+ p 2 +1 => p1=1, p 2任意，可取为0 即T 2 (n)=n c n 故T n = c1c n +n c n 代入T(1)= 1，得： c1c+1*c=1 => c1= c c?1 故：T n = c c?1 * c n +n c n = c 1?n +(n-1) c n ③直接展开法见教材p21 ④间接展开法（变换后用公式（5）），不可取，不自然，不直观，省略。 P15例10的直接展开： T(n)=3T( 2n )+2*n 5.1 =3[3T( 22n )+2*( 2n ) 5.1 ]+2*n 5.1 =3 2 T( 22n )+（3*2*2 5.1? +2）n 5.1 =3 2 [3T( 32n )+2( 22n ) 5.1 ]+（3*2*2 5.1? +2）n 5.1 =33 T( 32n )+（3 32 2*2* ? +3*2*2 5.1? +2）n 5.1 = n 5.1 [3T( 42n )+2( 32n ) 5.1 ]+（3 32 2*2* ? +3*2*2 5.1? +2）n 5.1 =3 4 T( 42n )+[33 2*2 5.4? +3*2*2 5.1? +2] n 5.1 … kn 2= 3 k T(1)+[3 5.1)*1(1 2* ??? kk +…+3*2 5.1? +30 *20 ]*2* n 5.1 =3 k + *2*2*31 )2*31(*1 5.1 5.1 ? ? ? ? kk n 5.1 =3 k + *2* 123 12*3 5.1 5.1 ? ?? kk n 5.1 =3 k + *2*06.0 1)2(*3 5.1 ??kk n 5.1 =3log 2 n+ 5.1 5.1log *2*06.0 1*3 2 nn n ?? 换底nlog 2 3+ 03.0 5.1log2 ?? nn n ≈34 nlog 2 3-33 n 5.1 =>T(n) =O( nlog 2 3) 注：3log 2 n =3 2log log 3 3 n =（3log 3 n） 2log 1 3 =n 2log 1 3 =n 2log 3log 3 3 = nlog 2 3 P15例11的直接展开： T n =2T 2 n +nlog 2 n=2 2 T 22 n +2n*log 2 n-n =23 T 32 n +n/2 2 *log 2 (n/2)]+2nlog 2 n-n =23 T 32 n +3nlog 2 n-2n-n =23 [2T 42n + 323 2log2 nn ]+3nlog 2 n-2n-n =2 4 T 42n +4nlog 2 n-3n-2n-n n2k = 2 k T 1+{klog 2 n+[(k-1)+(k-2)+…+3+2+1]}n =n+{(log 2 n) 2 - 2 )1)(11( ??+ kk }n = n[1+（log 2 n）2 - 2 )1( ?kk ] =n[1+（log 2 n）2 -1/2（log 2 n）2 +1/2*log 2 n] =[（log 2 n）2 +log 2 n+2]]/2*n 第六节 差分法(递推关系解法补充) (取自[美]C.L.Liu著，刘振宏译《离散数学基础》， 邮电出版社，1982.2, P258) 一、有关定义及术语 1. 递推关系或差分方程：对于序列 a0,a1,...,ar,...，一个关系到 ar与几个 ai(i<r)的方程式 就称为刻划该序列的递推关系或差分方程。 2. 边界条件或初始条件：只要给定了一个序列在一个或几个时刻的值，按递推关系， 我们就可以逐步地由 ar-1,ar-2,...求出ar，再由 ar,ar-1,...求出 ar+1等等。这些给定的值即称为边 界条件或初始条件。 3. 具有常系数的线性递推关系：形如 c0ar+c1ar-1+c2ar-2+...+ckar-k=f(r) (1) 的递推关系称为k阶常系数的线性递推关系。其中，所有的 ci为常数，c0和 ck均不为 0。 二、解法 通解＝齐次解（方程右边等于0时的解）＋特解（方程右边有f(r)时的解） （一）齐次解的求法 形如 c0 α k＋c1 α k-1＋c2 α k-2＋...＋ck＝0 (2) 的方程称为差分方程(1) 的特征方程。若 1α 是其特征根，则 r1Aα 就是(1)的一个齐次解。 1. k阶特征方程有k个特征根，假定特征方程的根都不相同，那么，可以验证 r kk r 22 r 11r AAAa α++α+α= L (3) 也是差分方程的一个齐次解（通项）。 其 中 k21 ,,, ααα L 是 不同的特征根，A1,A2,...,AK是由边界条件所确定的常数。 例：回顾斐波那契数列，其递推关系是：ar=ar-1+ar-2，对应的特征方程为 012 =?α?α , r22r11r21 AAa2 51,2 51 α+α=??=α+=α? 是一个齐次解。 其中A1,A2可由边界条件a0=1,a1=1来确定。 2. 某些根是重根，不妨令 1α 是m重根（m=1时下式就是(3)式的第一项）， 则与 1α 对应 的齐次解为： ar=(A1rm-1+A2rm-2+...+Am-1r1+Amr0) r1α (4) 整个方程的齐次解由形如(4)式的齐次解相加而成。 例：ar＋6ar-1＋12ar-2＋8ar-3=0 特征方程：α 3＋6 α 2＋12 α＋8＝0 ? (α＋2)3＝0 α＝-2 是三重根， 故ar=(A1r2+A2r+A3)(-2)r是给定方程的一个齐次解。 （二）特解的求法 寻求特解，没有一般的方法。然而，在一些简单的情况下，用观察的方法可以得到特 解，下面讨论两种常见形式。 1. 当差分方程的右端属于rt形式时，那么对应的特解属于下述形式： 1tt 1t 2 t 1r prprprpa + ? ++++= L 其中p1,p2,...,pt,pt+1是待定常数。 例：用此法可得ar+5ar-1+6ar-2=3r2的一个特解为 288115r2417r41a 2r ++= 2. 当差分方程的右端属于 rβ 形式时，若β不是差分方程的特征根，则对应的特解是 rpβ 形 式；若β是m重根(m>=1)，则对应的特解是如下形式： ar=(p0rm+p1rm-1+p2rm-2+...+pm) rβ 例：用此法可得ar+5ar-1+6ar-2=42× r4 的一个特解为 2rrr 4416a +=×= （三）通解的求法 假定差分方程的特征根是不同的，那么通解的形式为 )r(pAAAa rkkr22r11r +α++α+α= L 其中p(r)是一特解, k21 A,,A,A L 为任意常数。 有m重根时的通解可类似写出，只是相应项的系数不是常数，而是关于r的一个m-1 次多项式。 （四）满足边界条件的特解的求法 将k个边界条件代入通解，得到关于待定系数 k21 A,,A,A L 的 k阶线性方程组，从 中解出待定常数，代回通解所得的特解即为原差分方程满足边界条件的解。 例： rr2r1r 416)3(A)2(Aa ×+?+?= 是方程 ar+5ar-1+6ar-2=42× r4 的通解，假定边界条 件为 962a,278a 32 == ，则解方程组 ?? ? +??= ++= 1024A27A8962 256A9A4278 21 21 我们得到 A 1=1,A2=2,因此, 差分方程满足边界条件的特解是： rrrr 416)3(2)2(a ×+?+?=