第9章复杂度及其分析 本章主要介绍下列内容(教材第一章) 1.算法的复杂度 2.算法分析 3.复杂度分析 4.展开法 5.母函数法 6.差分法 课时分配:第1、2节三个学时,第3、4节三个学时,第5、6节共三个学时 重点、难点:算法复杂度分析的步骤、递归算法分析及递归方程解法 第一节算法的复杂度 算法 1.介绍有关统计数据(曹书p1引言) 2.算法的通俗定义 (一个)算法是由有限个指令(规则)组成的有序集合(序列)。这些指令确定了解 决某一问题的一个运算序列。 3.算法的五大特征 ①有穷性 ③能行性 ④输入 ⑤输出 4.求最大公因数的文字算法和高级语言算法。Cp2 5.算法与过程、程序的区别。Cp2 (有穷于无穷,描述多样性与执行多样性) 6.问题、问题实例及与算法运行的关系。pl 、算法设计和算法分析的步骤cp3 1.问题的陈述 2.模型的选择或拟制 3.算法设计和正确性证明 4.算法的程序实现 5.算法分析 三、评价算法的标准(p1)(详见1.2算法分析) 1.正确(算法己隐含该条) 2.易理解、易编程(上机实现)、易修改、可扩展 3.高效(节省时间与空间) 2、3条的辩证关系,谁放在首位,视具体情况而定。(p1,p2) 四、算法复杂度定义
第 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.O与Ω的定义 运算规则:O(f+g)=O(max{f,g}),O(Kf)=O(f) 5.最佳算法的概念定义 6.按算法复杂度对问题分类(cp6) 7.复杂度函数中的常量因子不可忽视(cp6) 第二节算法分析 、评价分析算法的指标(标准)见p5-7略讲 二、复杂度的具体分析指标 1.基本运算次数 2.问题规模量化 3.平均工作量与最坏情况工作量 空间与此类似 第三节复杂度分析 如何具体确定一个完整算法的时间复杂度 1.问题实例大小的量化 2.基本运算的选择 3.分析构成算法各种成分执行时所需工作量 4.利用大○规则求总和 、举例进一步剖析讲解 、用一次课时间补充递推关系的差分解法,内容详见第六节(补充)。 第四节展开法 、如何由具体问题的算法得到形如下式的递归方程 介绍解递归方程maTn+d(n) n> 勺展开法 (举例见第五节) 例1218Ta2Tn-1+1 用母函数法解(定义T=0) n>1
1．决定算法复杂度的两个因素 ① 问题实例大小 ② 实例的具体情况（数据出现的顺序及概率） 2．三种复杂度的定义 本课程重点讨论时间复杂度 3． 用三个表说明算法复杂度的重要性（p2-3） 4．○与W 的定义 运算规则：○(f+g)=○(max{f,g}), ○(Kf)=○(f) 5．最佳算法的概念定义（cp6） 6．按算法复杂度对问题分类（cp6） 7．复杂度函数中的常量因子不可忽视（cp6） 第二节 算法分析 一、评价分析算法的指标（标准）见 p5-7 略讲 二、复杂度的具体分析指标 1．基本运算次数 2．问题规模量化 3．平均工作量与最坏情况工作量 空间与此类似。 第三节 复杂度分析 一、如何具体确定一个完整算法的时间复杂度 1．问题实例大小的量化 2．基本运算的选择 3．分析构成算法各种成分执行时所需工作量 4．利用大○规则求总和 二、举例进一步剖析讲解 三、用一次课时间补充递推关系的差分解法，内容详见第六节（补充）。 第四节 展开法 一、如何由具体问题的算法得到形如下式的递归方程 二、介绍解递归方程 Tn= ïî ï í ì + > = aT d(n) n 1 c n 1 b n 的展开法 （举例见第五节） 例 12 p18 T n = î í ì + > = - 2T 1 n 1 1 n 1 n 1 用母函数法解（定义 T0=0）
(教材代公式,此处直接推导) 令母函数为:G(x)=Ta+Tx+T,x2+…+T,x”+ 2x G(x)=2T X+2 TIx+2T, X 曰G(x)-2xG(x)=To+(T-2T0)x+(T2-2T)x2+… G(x)= ∑(2x)-∑x=∑(2-1x 展开法:Tn=2Tn1+1=2(2Tn2+1)+1 =22Tn-2+2+1 1(-2)=2 待定系数法(差分) n T-27=1n>1 特征方程:2-2=0=>λ=2 齐次解:T1(n)=c*2 特解:T2(n)=1 通解:Tn(n)=c*2”-1代入初始条件T1=1=1=c*2-1=>c=1 故T=2-1为所求解。 a(1)=0 例13 展开法见教材p1l l(m)=2(n-1)+c*2(m>1) G(x)=u,x+u,x2+…+u,xn+… 2xG(x)=2u1x2+2 G(x)-2xG(x)=u1x+(u2-2u1)x2+(u3-2u2)x3+…+(un-2un1)x"+ u1x+c*2x+c*2“*x++c*2n-1n
（教材代公式，此处直接推导） 令母函数为：G(x)=T 0 + T1x+T 2 x 2 +…+T n x n +… 2x G(x)=2 T 0 x+2 T1x 2 +2 T 2 x 3 +… ð G(x)- 2x G(x)= T 0 +( T1-2 T 0 ) x+( T 2 -2 T1) x 2 +… ð G(x)= x x x x x - - - = - - 1 1 1 2 1 1 * 1 2 1 = n n n n å(2x) -åx = å(2 -1)x ð T n =2n -1 展开法：T n =2Tn-1 +1=2（2Tn-2 +1）+1 =2 2 Tn-2 +2+1 = 2 1 1 2 1(1 2 ) = - - - n n 待定系数法（差分）： î í ì - = > = 2 - 1 1 1 1 1 T T n T n n n 特征方程：l - 2 = 0 => l = 2 齐次解： 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 î í ì = - + > = - ( ) 2 ( 1) * 2 ( 1) (1) 0 1 u n u n c n u n 展开法见教材 p11 G(x)=u1 x+u 2 x 2 + …+ u n x n +… 2x G(x)=2 u1 x 2 +2 u 2 x 3 +…+2 u n-1 x n +2 u n x n+1 +… G(x)- 2x G(x)= u1 x+( u 2 - 2 u1 ) x 2 +( u 3 -2 u 2 ) x 3 +…+( u n -2 u n-1 ) x n +… = u1 x+c*2 x 2 +c*2 2 *x 3 +…+c*2 n-1 *x n +…
=u1x+x*C*2x+(2x)2+…+(2x)m1+… =u xtx**c*** 2 =cx与p19相同 (1-2x) 或=c/2*( 公式法(待定系数) u1(n)=c12或c12 特解:u2(n)=(p1n+p2)2 代入:(p1nt+p2)2=2(p1(n-1)+p2)2-+c*2 2(p1nt+p2)=2p1(n-1)+2p2+c p1=c/2p2为任意常数 u2(m)=(c/2和n+p)2=cn2"(取p=0) →u(n)=c12+cn 由u1=0→2c1+c=0→c1=c/2 →u(n)=-c/2*2+cn2m=-c*2+cn*2=c(n-1)2n全部变成N 也可以用展开法直接求解18页例13第一式,不进行变换。 例14推导 因为k>2/=k 1-2
= u1 x+x*c*[2x+ (2x) 2 +…+ (2x) n-1 +…] = u1 x+x*c* n x 1 2 2 - = x cx 1 2 2 2 - Þ G(x)= 2 2 (1 2 ) 2 x cx - =cx* x x 1 2 2 - * 1 2x 1 - =cx 与 p19 相同 或 =c/2*( x x 1 2 2 - ) 2 公式法（待定系数）： u1 (n)=c1 2 n或 c1 2 n-1 特解：u 2 (n)=(p1 n+ p 2 )2n 代入：(p1 n+ p 2 )2n =2(p1 (n-1)+ p 2 )2n-1+c*2n-1 2(p1 n+ 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)= c1 2 n +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 (k j)2 1 0 å - = - =kå - = 1 2 k j o j -å - = 1 2 k j o j j 因为 kå - = 1 2 k j o j =k 1 2 2 (1 2 ) 0 - - k =(2 k -1)k å - = 1 2 k j o j j =å - = 1 1 2 k j j j =21 +
-2;ak-2 (k-2项) k-1+2-1+2-+…2k-1+9k-1 2(1-2),2(1-2 2-(1-22) (2-21)+(2k-22)+…+(2k-2*-2)+(2k-2k-1) (k-1)2-[2+22+…2-] 2(1-2) 所以∑(k-)21=(2-1)k-24(k=2)-2=24#-k-2 另1:令s=∑j21=1*20+22+3*2+…,+h >2s=1*2+2*2-+3*2+…+h米 2(1-2b) 亦即∑j=(h-2)2-1+1 两边乘2得:∑p2=h-2)2+2 另2:令s(x)=
2 2 +2 2 + 2 3 +2 3 +2 3 +… 2 k -2 +2 k -2 +2 k -2 +…+2 k -2 +… (k-2 项) 2 k -1 +2 k -1 +2 k -1 +…2 k -1 +2 k -1 (k-1 项) = 1 2 2 (1 2 ) 1 2 2 (1 2 ) ... 1 2 2 (1 2 ) 1 2 2 (1 2 ) 1 1 2 2 2 2 1 1 - - + - - + + - - + - - k- k- k - k - =(2 k -21 )+(2 k -2 2 )+…+(2 k -2 k -2 )+(2 k -2 k -1 ) =(k-1) 2 k -[21 +2 2 +…2 k -1 ] =(k-1) 2 k - 1 2 2 (1 2 ) 1 1 - - k- =(k-1) 2 k +2-2 k =2 k (k-2)+2 所以 j k j (k j)2 1 0 å - = - =(2 k -1)k-2 k (k-2)-2=2 k +1 -k-2 另 1：令 s=å= - h j 1 j 1 j2 =1*2 0 +2*21 +3*2 2 +…+h*2 h-1 =>2s=1*21 +2*2 2 +3*2 3 +…+h*2 h =>s-2s=2 0 +21 +2 2 +…+2 h-1 -h*2 h = 1 2 2 (1 2 ) 0 - - h - h*2 h =>s= h*2 h - 2 h +1 亦即å - = - h 1 j 1 j 1 j2 =(h-2) 2 h-1 +1 两边乘 2 得: å - = h 1 j 1 j j2 =(h-2) 2h +2 另 2：令 s(x)= å= - h j 1 j 1 jx 则