《【教学课件】第二章算法设计与分析的基本方法及技巧.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章算法设计与分析的基本方法及技巧.ppt（45页珍藏版）》请在三一办公上搜索。
1、第二章算法设计与分析的基本方法及技巧,2.1 程序运行时间2.2 一类递归方程的求解2.3 分治2.4 平衡2.5 贪心法2.6 动态规则2.7 回溯,算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。,Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn Ms al-Kho
2、wrizm（约公元前825年）从字面上看，这个名字的意思是“Jafar 的父亲，Mohammed 和 Ms 的儿子，Khowrizm 的本地人”。Khowrizm 是前苏联XBA(基发)的小城镇。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala(复原和化简的规则)；,资料：Algorithm与Logarithm这个词一直到1957年之前在Websters New World Dictionary(韦氏新世界词典)中还未出现，我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘
3、进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪尔国王Algor”派生而来的。最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm（约公元前825年）从字面上看，这个名字的意思是“Jafar 的父亲，Mohammed 和 Ms 的儿子，Khowrizm
4、的本地人”。Khowrizm 是前苏联XBA(基发)的小城镇。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala(复原和化简的规则)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon(数学大全辞典)，给出了Algorithmu
5、s(算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis(无限小方法)，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。1950年左右，algorithm一词经常地同欧几里德算法(Euclids algorithm)联系在一起。这个算法就是在欧几里德的几何原本(Euclids Elements,第VII卷，命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。,递归技术 最常用的算法设计思想，体现于许多优秀算法之中 分治法 分而制之的算
6、法思想，体现了一分为二的哲学思想 模拟法 用计算机模拟实际场景，经常用于与概率有关的问题 贪心算法 采用贪心策略的算法设计 状态空间搜索法 被称为“万能算法”的算法设计策略 随机算法 利用随机选择自适应地决定优先搜索的方向 动态规划 常用的最优化问题解决方法,“好”的算法的标准：正确性，算法能满足具体问题的需求 可读性，首先方便阅读与交流，其次才是机器执行 健壮性，输入错误时，能作出反应，避免异常出错 效率与低存储量要求,算法的特征：有穷性、确定性、输入、输出、能行性,对算法“正确性”的要求：不含语法错误；对于几组输入数据能得到满足要求的结果；对精心选择苛刻并带有刁难的数据能得到满足要求的结果
7、；对于一切合法的输入均得到满足要求的结果；,算法描述：自然语言；程序设计语言；类语言*；,关于本书采用的类语言描述：结构类型说明 输入输出约定(cin v,cout v)new 和 delete 引入引用类型 其他,影响算法执行的因素：算法实现后所消耗的时间*算法实现后所占存储空间的大小*算法是否易读、易移植等等其它问题,影响时间特性的四个因素：程序运行时输入数据的总量 对源程序编译所需的时间 计算机执行每条指令所需的时间 程序中指令重复执行的次数*,定义 语句频度：语句重复执行的次数,程序运行时间,渐近时间复杂度（时间复杂度）T（n）,算法中基本操作重复执行的次数是问题规模n的某个函数f（n
8、），算法的时间度量记作：T（n）=O（f（n）它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。,渐近空间复杂度（空间复杂度）S（n）,S（n）=O（g（n）,运算法则：设：T1(n)=O(f(n)，T2(n)=O(g(n)加法规则：T1(n)+T2(n)=O(max f(n),g(n)乘法规则：T1(n)T2(n)=O(f(n)g(n),设：,T(x)：取变量或常量x之值所消耗时间T(.V)：取变量V之地址所消耗的时间T(=)：赋值所消耗时间T()：执行基本运算所耗时间T(call/return)：执行函数调用和返回所耗时间T(par)：将参数par传给函数所消耗时间,(
9、1)表达式和赋值语句 exp:=常数|变量|F-name(e1,e2,em)|(exp exp)T(v=exp)=T(.v)+T(=)+T(exp)T(exp exp)=T(exp)+T()+T(exp)T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body)例：T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b)相应的汇编程序为：load a in R1 load b in R2 add R2 to R1 load.c in R2 store R1 in R2,通常取O(1),(2)语句序列 T(s1,s2,sk)=maxT(s1
10、),T(s2),T(sk)(3)条件语句 T(if(B)s1 else s2)=T(B)+T(else)+maxT(s1),T(s2)通常取T(B)+T(else)=O(1)T(if(B)s)=O(1)+T(s)(4)Switch语句 设语句s switch(E)case E1:S1;case Ek:Sk;default:Sm T(s)=T(E)+T(Ei)+maxT(s1),T(sk),T(sm)O(1),ki=1,(5)for语句 T(for(i=1;i=n;i+)s)=(T(s)+T(i=1)+T(i=n)+T(i+)+T(for),O(1),(6)while语句 while(B)s i
11、=0;while(B)s;i+设RT0表示某一次循环开始执行时的绝对时间 关于循环的定时不变式RT为 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j)其中：T(while)代表测试循环终止条件所耗时间 T(j)代表跳回循环头所耗时间 可简化成：T(j)=T(while)T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while),(7)函数调用 递归调用：被调用子函数运行时间 非递归调用：求解递归方程(8)goto语句 goto语句破坏了程序结构 一般对goto语句限制使用 对有条件的goto转移可忽略不计,Void BUBB
12、LE(A)int An;int I,j,temp;for(i=0;i=i+1;j-)O(n-i-1)if(Aj-1Aj)O(n-i-1)1)O(n(n-1)/2)temp=Aj-1;O(1)O(1)=(n-i-1)=O(n2)Aj-1=Aj;O(1)O(1)Aj=temp;O(1),n-2i=0,举例：s=0;f(n)=1;T1(n)=O(f(n)=O(1)常量阶 for(i=1;i=n;+i)+x;s+=x;f(n)=3n+1;T2(n)=O(f(n)=O(n)线性阶 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;f(n)=3n2+2n+1;T3(n)=O(f(
13、n)=O(n2)平方阶 for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;f(n)=2n3+3n2+2n+1;T4(n)=O(f(n)=O(n3)立方阶,举例：Long fact(int n)if(n=0)|(n=1)return(1);else return(n*fact(n 1);,f(n)=n G T(n)=O(f(n)=O(n),int sort(i,j)int i,j;if(i=j)return(xi);else m=(i+j-1)/2;return(merge(sort(i,m),sort(m+1),j)
14、;,这是一个快速排序算法merge的运行时间正比于n（n是2的幂）设T(n)是sort最差情况下的运行时间，则,一类递归方程的求解,猜解法：首先猜出一个解f(n)的形式，令其带有待定参数；在归纳推理过程中确定待定参数，并利用方程证明T(n)f(n)。若推理过程能够完成且待定参数能够确定，则求解完毕。f(n)可以是 O(1),O(n),O(nlogn),O(n2)等等。,猜测1：对参数a，T(n)anlogn，带入n=1，由于anlogn=0 虽然满足T(1)c1，但它与a无关，无法确定a与c1关系。此猜测失败。,猜测2：T(n)=anlogn+b，当n=1时，只要bc1即可。当n2时，设对所有
15、的 kn 有 T(k)aklogk+b 令k=n/2 得 T(n/2)a(n/2)log(n/2)+b 带入原式：T(n)2T(n/2)+c2n2(a(n/2)log(n/2)+b)+c2n=an(logn-1)+c2n+2b=anlogn+b-(an-c2n-b)只要令an-c2n-b0就有 T(n)anlogn+b 选择ac2+b，使an-c2n-b0得到满足。使T(n)anlogn+b成立的两个约束是：bc1，ac2+b 取b=c1,a=c1+c2 是合理的。,一类递归方程的展开式与通解,设T(n)是求解某个问题的时间开销，n使问题的数据量。设计对此问题列出的递归方程为：T(1)=1 T
16、(n)=aT(n/c)+d(n)n2其中c是大于等于1的正整数。全部数据被分割成c等分，每分的数量为n/c。T(n/c)是求解一个子问题的时间开销。aT(n/c)代表求解a个问题的时间开销。D(n)是任意的函数，方程是严格的等式。用n/ci代替n得：T(n/ci)=aT(n/ci+1)+d(n/ci),i=1,2,3,T(n)=aT(n/c)+d(n)=a(aT(n/c2)+d(n/c)+d(n)=a2T(n/c2)+ad(n/c)+dn=a2(aT(n/c3)+d(n/c2)+ad(n/c)+d(n)=a3T(n/c3)+a2d(n/c2)+ad(n/c)+d(n)=ai T(n/ci)+a
17、jd(n/cj),i-1j=0,倍积函数：若对所有的正整数x，y，有f(xy)=f(x)f(y)，则 f 是 正整数上的倍积函数。若d(n)是倍积函数。则有：d(ck-1)=(d(c)k-1,定理：设a,c是非负常数，n是2的幂，d(n)是倍积函数，则,的齐次解是O(nlogc)，且对特解有如下结论：(1)若ad(c)，则特解是O(ak)，或O(nlogc),即特解与齐次解同阶(2)若ad(c)，则特解是O(d(c)k)，或O(nlogcd(c)即特解与d同阶(3)若a=d(c)，则特解是齐次解的logcn。,a,a,基本思想：分而治之。将一个规模为n的问题分解为k个规模较小 的子问题，这些子
18、问题互相独立且与原问题相同。递 归地解这些子问题，然后将各子问题的解合并得到原 问题的解。,设问题输入数据A0.n-1，函数dac(p,q)求子问题Ap,q的解。对函数dac的首次调用是dac(0,n-1)。,int dac(int p,int q)if(small(p,q)return(G(p,q);else(m1,mk)=divide(p,q);return(Combine(dac(p,m1),dac(m1+1,m2),dac(mk+1,q);,分治方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：1)把它分成两个或多个更小的问题；2)分别解决每个小问题；3)把各小问题的解组
19、合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归使用分治策略来解决。,分治（Divide and Conquer）,1、整数乘法,求两个n位数之积，传统方法需要O(n2)次比较运算，运用分治法可以将运算次数的阶降到O(nlog3)O(n1.59)。,设x和y都是n位数，n是2的幂，将x和y各分成两半，每一半都是n/2位数，则xy的积可写成：,xy=(a2n/2+b)(c2n/2+d)=ac2n+(ad+bc)2n/2+bd也可写成：xy=ac2n+ac+(a-b)(d-c)+bd)2n/2+bd,a,b,c,d,x=,y=,int mult(int x,int y,int n)i
20、f(n=1)return(x*y);else s=sign(x)*sign(y);x=abs(x);y=abs(y);a=x的左n/2位；b=x的右n/2位；c=y的左n/2位；d=y的右n/2位；v=mult(a,c,n/2);u=mult(a-b,d-c,n/2);w=mult(b,d,n/2);return(s*(v*2n+(u+v+w)*2n/2+w),例：设 x=3141,y=5327,利用分治法求xy,31,41,53,27,x=,y=,x=3141 a=31 b=41 a-b=-10y=5327 c=53 d=27 d-c=-26 ac=(1643)*,bd=(1107)*,(a
21、-b)(d-c)=(260)*xy=ac104+(ac+(a-b)(d-c)+bd)102+bd=(1643)*104+(1643)*+(260)*+(1107)*102+(1107)*=(16732107)*,a=31 a1=3 b1=1 a1-b1=2c=53 c1=5 d1=3 d1-c1=-2 a1c1=15,b1d1=3,(a1-b1)(d1-c1)=-4ac=15102+(15+3-4)101+3=1632,b=41 a2=4 b2=1 a2-b2=3d=27 c2=2 d2=7 d2-c2=5 a2c2=8,b2d2=7,(a2-b2)(d2-c2)=15bd=8102+(8+7
22、+15)101+7=1107,a-b=10 a3=1 b3=0 a3-b3=1d-c=26 c3=2 d3=6 d3-c3=4 a3c3=2,b3d3=0,(a3-b3)(d3-c3)=4(a-b)(d-c)=2102+(2+0+4)101+0=260,2、求两个矩阵的积,C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22,将A和B分别等分成4个小矩阵,每个元素就是一个(n/2)x(n/2)矩阵,假设用(n/2)(n/2)矩阵的m次相乘和a次相加（减）可以算出Cij，则递归应用这种算法，对nn矩阵之积的时间开
23、销满足：T(n)2其中第一项是计算m对(n/2)(n/2)矩阵之积的时间开销,(n/2)2个数第二项是a次矩阵相加的时间开销。上是可变换成：4/aT(n)=4m/aT(n/2)+n2 U(n)=4m/aU(n/2)+n2其中d(n)=n2是倍积函数，只要ma就有4m/ad(c)，T(n)=O(nlogm)m=8,a=4，T(n)=O(n3),V.Strassen矩阵,引理2.1 两个22矩阵(元素来自任意的环)之积可以用7次相乘和18次相加(减)完成。,M1=(A11A12)(B21+B22)M2=(A11+A22)(B11+B22)M3=(A11A21)(b11+B12)M4=(A11+A1
24、2)B22M5=A11(B12-B22)M6=A22(B21B11)M7=(A21+A22)B11,C11=M1+M2-M4+M6C12=M4+M5C21=M6+M7C22=M2M3+M5M7,定理2.2 两个nn的矩阵(元素来自任意的环)之积可用O(nlog7)次 运算完成 证：设n=2k，T(n)是计算两个nn矩阵之积，由引理2.1得 T(n)=7T(n/2)+18(n/2)2，n=2 故有：T(n)=O(nlog7),在对问题进行分割时，应使各子问题的数据量保持相等或尽可能相等。保持平衡是算法设计的一条基本原则。,例如：常见的是“冒泡”分类算法就是一个不平衡的例子。在分治时将输入数据a1
25、,a2,an分成很不平衡的数据段：从左至右扫描a1,a2,an并求出minai,1=i=n；将它与 a1交换位置；对后面的n-1个元素递归地应用此算法。,T(n)=n(n-1)/2=O(n2),考虑平衡：不妨设n是2的幂。将a1,a2,an分成两个子序列：a1,a2,an/2和a(n/2)+1,an。先对每个子序列进行分类，然后对已分类的子序列进行归并（最多需要n-1次比较），合并成一个有序序列。,T(n)=O(nlogn),平衡,运用局部最佳策略以求达到全局最佳结果。给定输入数据为A1,A2,An，对解附有某些约束条件和表示最佳结果的目标函数，欲求满足约束条件的子集Aik,使目标函数值达到最
26、大（或最小）。满足约束条件的任意子集叫做可用解，使给定的目标值达到最大（或最小）的可用解叫做最佳解。最终目的是求全局最佳解。,Dataset Gready(A,n)LIST A;int n;solution=；for(i=1;i=n;i+)x=select(A);if(feasible(solution,x)solution=union(solution,x);return solution;,select 对 A 确定一种取值办法；每步对一个x=Ai作出判断：x是否可以包含在最佳解中？若x加入局部最佳解时就产生不可用解，放弃x，另作选择。,union将x和solution结合成新的解向量,并
27、修改目标函数的值。,贪心法,在贪心算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。,例找零钱 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择
28、的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。,背包问题设有n个对象和一个背包。对象的重量为wi。背包容量为M(重量)。若将对象i的一部分xi(0 xi1;xi表示重物wi的几分之几)放入背包，则得增益pixi，其中pi叫做重物wi的增益率。目标:在n个对象中选取若干对象，将背包装满(所选对象的总重量不超过M),使总增益最大。,max(pixi),1in,约束条件：wixiM 0 x
29、i1,pi0,wi0,1in 满足的任意集合x1,x2,xn就是可用解使最大的可用解即最佳解,1in,三种贪心策略：(1)局部最大增一策略：即在第i步选过之后第i+1步将当前增益 最大的未选对象装入背包；若该对象太大而溢出背包，则装 入该对象的几分之几。(2)贪心策略之二：背包容量局部消耗最小策略。即按先轻后重 的顺序来选择对象。(3)贪心策略之三：消耗单位容量，获取局部最大增益策略。即 按pi/wi非增加的顺序来选择对象。,例：设n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10),按策略1，对象1的增益率p1最大，取x1=1,则背包容量尚
30、余M-w1=2;对象2的增益率次之,但w2=15,不能全部装入,故令x2=2/15,得解2。按策略2，首先取x3=1,次取x2=2/3,得解3。按策略3，得解4，这才是最佳解。,Void KnapSack(LIST w;int m;LIST,Pi/wi=(1.4,1.6,1.5),定理2.3 若 p1/w1p2/w2pn/wn 则算法Knapsack对给定的 背包问题生成全局最佳解。证明见教材P42（略）。,实例：设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w1,w2,wn。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为S。如果存在一种符合上述要求的选择
31、，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。,enum boolean False,True boolean Kanp(int s,int n)if(s=0)return True;if(s 0,当一个问题的解可以看成是以序列判定的结果时，可以用动态规划方法设计出这类问题的求解算法。,起源于二十世纪五十年代（贝尔曼）属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理，可归结为一个递推公式又称为对阶段规划，特点体现在多阶段性,动态规划,背包问题的解可以看成是一序列判定的结果，这里必须决定xi(1in)的取值。我们可以
32、用不尽的方式首先做关于x1的判定,然后关于x2,x3,等等.最后产生一个最佳的判定序列x1,x2,xn,使目标函数pixi的值最大。,最佳原理一个最佳判定序列有这样一个性质：无论该序列是从什么初始状态开始首次判断的，其后续的判断队首次判断所产生的状态而言，必构成最佳判定序列。贪心法与动态规划方法之间的本质区别：贪心法只生成一个判定序列，而动态规划方法则可能产生许多判定序列。,maxpixi,1ij,例：（0/1）背包问题用Knap(1,I,y)表示下述0/1背包问题,约束条件：wixiy，xi=0 或 1（1ij）,1ij,则0/1背包问题是knap(1,n,M),wiziM-w1，pizip
33、ixi,2in,2in,2in,设：y1,y2,yn是x1,x2,xn所取0/1值的最佳序列。,若y1=0,y2,y3,yn必构成关于Knap(2,n,M)的最佳序列。不然，y1,y2,yn就不是Knap(1,n,M)的最佳序列。,若y1=1,则y2,y3,yn必是关于knap(2,n,M-w1)的最佳序列,如不然，就会有另一个0/1序列z2,z3,zn使：,于是，y1,z2,zn是一个符合目标函数且具有最大增益的序列。这与y1,y2,yn是最佳序列相矛盾,说明最佳原理适用于0/1背包问题。,gj(y)=pixi，wixi y，xi=0/1(j+1in),j+1in,j+1in,若选x1=0：
34、g0(M)=pixi=pixi=g1(M)，约束条件：wixi=wixiM,若选x1=1：g0(M)=pixi=p1+pixi=p1+g1(M-w1),关于目标函数的递推式：,设gj(y)是0/1背包(子)问题Knap(j+1,n,y)的最佳解的目标函数，即：,则g0(M)是knap(1,n,M)的最佳解。,对x1的可能判定是0/1：,其中wixiM是对Knap(2,n,M)的约束条件。因此，如果决定不取w1，则求解Knap(1,n,M)的问题即归结为求解子问题Knap(2,n,M)。,约束条件wixi可以换成：wixiM-w1，就是说，如果决定将w1装入背包，则g0(M)=p1+g1(M-w
35、1)且对0/1背包问题的约束变成wixiM-w1，故求解Knap(1,n,M)的问题可归结为求解Knap(2,n,M-w1)的问题。,1in,1in,1ij,1ij,2in,2in,2in,2in,2in,2in,由最佳原理得：g0(M)=max g1(M),g1(M-w1)+p1,一般向前递推式为：gi(n)=max gi+1(y),gi+1(y-wi+1)+pi+1 由于gn(y)=0对所有的y成立，在上式 代入i=n-1即可由gn(y)求出gn-1(y),一般向后递推式为：gn(M)=max gn-1(M),gn-1(M-wn)+pn gj(y)=maxgj-1(y),gj-1(y-wj
36、)+pj g0(y)=0(y0),0/1背包问题难于非0/1背包问题，因为0/1背包问题将产生2n个判定序列，其中n是解向量(x1,x2,xn)的长度。所以不能用贪心法解0/1背包问题。,M=M1 M2 Mn,M1(M2M3M4)23000次乘法,(M1(M2M3)M4)2200次乘法,设mij是计算MiMi+1Mj的最小代价,求n个矩阵的乘积,for(i=1;i=n;i+)mi,i=0;for(l=1;l=n;l+)for(i=1;i=n-1;i+)j=i+1;mi,j=min(Mi,k+Mk+1,j+ri-1*rk*rj);write(mln);,mij=；for(k=i;kmik+mk+1,j+ri-1*rk*rj)mij=mk+mk+1,j+ri-1*rk*rj；Kij=k;,回溯,
