算法设计与分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,算法设计与分析,1,课程目的,对算法设计与分析进行一个较为全面的介绍，使大家具有进行简单的算法设计与分析的基本能力,先修课程,程序设计语言,数据结构,高等数学,离散数学,概率论,2,主要内容介绍,第1章算法引论,第2章递归与分治策略,第3章动态规划,第4章贪心算法,第5章回溯法,第6章分支限界法,第7章概率算法,第8章NP完全性理论,3,教学用书,王晓东,算法设计与分析,清华大学出版社,4,T.,C,ormen,C.,L,eiserson,R.,R,ivest,and C.Stein,Introduction to Algorithms,2nd Ed.,MIT Press and McGraw-Hill Book Company,2001,教学参考书,5,D.E.Knuth,The Art of Computer Programming,Vol.1 and 3,Third Edition,Addison Wesley,1997.,6,第1章 算法引论,程序=算法+数据结构,1.1 算法与程序,一.算法在计算机科学中的重要地位,7,解二.,开 始,输入,m、n,r=m%n,r=0?,mn，nr,输出,n,是,否,10,解三.,Euclid(int,m,int,n,),int,r;,while(,n,!=0),r,=,m,%,n;,m,=,n;,n,=,r;,printf(,“,%,d”,m,),11,3.算法的描述方法.,（1）自然语言,（2）流程图,（3）程序设计语言,12,三.算法设计与分析的步骤,1.问题的描述.,2.模型的选择.,3.算法设计和正确性证明.,4.算法的分析.,5.算法的实现.,13,1.2 算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量，,需要时间资源的量称为,时间复杂性,，需要的空间资源的,量称为,空间复杂性,。,这个量应该只依赖于算法要解的问,题的规模、算法的输入和算法本身的函数。如果分别用,n,、I,和,A,表示算法要解问题的规模、算法的输入和算法,本身，而且用,C,表示复杂性，那么，应该有,C=F(,n,I,A),。,一般把时间复杂性和空间复杂性分开，并分别用,T,和,S,来,表示，则有：,T=T(,n,I),和,S=S(,n,I),。,（,通常，让,A,隐含在复杂性函数名当中）,14,最坏情况下的时间复杂度：,渐近时间复杂度：,平均情况下的时间复杂性：,设,D,n,是规模为,n,的合法输入的集合；,I,*,是,D,n,中使,T(,n,I,*,),达到,T,max,(,n,),的合法输入；而,P(I),是在算法的应用中出现输入,I,的概率。则：,n,时，,T,(,n,),的主要部分,算法共有,k,种基本步骤，,第,i,种步骤所需时间,t,i,，,出现次数,e,i,.,用问题体积,n,表示的运行时间,T(,n,),称为时间复杂度,15,算法复杂度的重要性,假设计算机每秒可作,1000,次基本运算,16,有效算法,最佳算法,计算问题的分类,1.无法写出算法的问题.,2.有多项式算法的问题.,3.介于上述两问题之间的问题.,17,例,解,用最直观的方法,用,Horner,算法,Horner(int,a,n,+1,real,x,),int,p,=,a,n,;,for(,i,=1;,i,=,n,;,i,+),p,=,p,*,x,+,a,n,-,i,;,return,p,;,18,表示算法渐近复杂度的数学符号：,渐近意义下的记号：,O,、,、,、,o,设,f(,n,),和,g(,n,),是定义在正数集上的正函数。,O,的定义,：如果存在正的常数,C,和自然数,N,0,，,使得当,n,N,0,时有,f(,n,),C,g(,n,),，则称函数,f(,n,),当,n,充分大时上有界，且,g(,n,),是它的一个上界，记为,f(,n,)=O(g(n),。即,f(,n,),的阶不高于,g(,n,),的阶。,根据,O,的定义，,容易证明它有如下运算规则：,(1),O(f)+O(g)=O(max(f,g)；,(2),O(f)+O(g)=O(f+g)；,(3),O(f)O(g)=O(fg)；,(4),如果,g=O(f),，,则,O(f)+O(g)=O(f),；,(5),O(Cf)=O(f),，,其中,C,是一个正的常数；,(6),f=O(f),。,19,的定义,：如果存在正的常数,C,和自然数,N,0,，,使得当,n,N,0,时,有,f(,n,),C,g(,n,),，则称函数,f(,n,),当,n,充分大时下有界，且,g(,n,),是它的一个下界，记为,f(,n,)=,(g(,n,),。即,f(,n,),的阶不低于,g(,n,),的阶。,的定义,：定义,f(,n,),=,(g(,n,),当且仅当,f(,n,)=O(g(,n,),且,f(,n,)=,(g(,n,),。,此时称,f(,n,),与,g(,n,),同阶。,o,的定义,：对于任意给定的,0,，,都存在正整数,N,0,，,使得,当,n,N,0,时有,f(,n,),/,g(,n,),则称函数,f(,n,),当,n,充分大时的阶比,g(,n,),低，记为,f(,n,)=o(g(,n,),。,例如，,4,n,log,n,+7=o(3,n,2,+4,n,log,n,+7),。,20,第2章 递归与分治策略,凡治众如治寡，分数是也。,-,孙子兵法,21,2.1,递归的概念,直接或间接地调用自身的较小模式的算法称为,递归算法,。,用函数自身的较小模式给出其定义的函数称为,递归函数,。,由分治法产生的子问题往往是原问题的较小模式，子问题的复杂度也原问题复杂度的较小模式，这就为使用递归技术进行算法分析提供了方便。,分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,22,例1 阶乘函数,阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,下面来看几个实例:,factorial,(int n),if,(n=0),return,1;,else,return,factorial,(n-1);,T(n)=T(n-1)+1,T(n)=,O,(n),23,阶乘函数可以找到相应的非递归方式定义：,factorial,(int n),int i,p=1,;,for(i=1;i=n;i+)p=p*i;,return p;,循环,n,次，故,T(n)=n,24,例,2 Fibonacci,数列,25,Fibonacci数列的前10项为1，1，2，3，5，8，13，21，34，55，它可以递归地定义为：,边界条件,递归方程,第,n,个,Fibonacci,数可递归地计算如下：,fibonacci,(int n),if,(n 1)，和A(1,1)=2，得A(n,1)=2*n,m=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=。,m=3时，类似的可以推出,m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,29,定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。,定义其拟逆函数(n)为：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。,(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有,(n)4,。但在理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,30,例4 排列的生成问题,设计一个递归算法生成n个元素r,1,r,2,r,n,的全排列。,设,R=r,1,r,2,r,n,是要进行排列的,n,个元素，,R,i,=Rr,i,。,集合,X,中元素的全排列记为,perm(X),。,(r,i,)perm(X),表示在全排列,perm(X),的每一个排列前加上前缀,r,i,得到的排列。,R,的全排列可归纳定义如下：,当,n=1,时，,perm(R)=(r),，其中,r,是集合,R,中唯一的元素；,当,n1,时，,perm(R),由,(r,1,)perm(R,1,),，,(r,2,)perm(R,2,),，,，,(r,n,)perm(R,n,),构成。,31,perm(list,int k,int m)/,产生前缀是,list0:k-1,后缀是,listk:m,的所有排列,/,perm(list,0,n-1),产生,list0:n-1,的去全排列,if(k=m)/,单元素排列,for(int i=0;i=m;i+)cout listi;cout endl;else /,多元素序列，递归产生排列,for(int i=k;im1;,正整数,n,的最大加数,n,1,不大于,m,的划分由,n,1,=m,的划分和,n,1,m-1,的划分组成。,(3)q(1,m)=1,m,1,;,36,显然，正整数,n,的划分数,p(n)=q(n,n),。,q(int n,int m),if(m=1|n=1)return 1;,else if(n 0),hanoi,(n-1,a,c,b);,move,(a,b);,hanoi,(n-1,c,b,a);,39,例.描述,n=3,时,hanoi,(n,a,b,c),的运行过程。,层次,栈状态,塔状态,1,3,a,b,c,c,b,a,3,2,1,2,2,a,c,b,3,a,b,c,c,b,a,1,3,2,3,1,a,b,c,2,a,c,b,3,a,b,c,层次,栈状态,塔状态,c,b,a,2,1,3,2,2,a,c,b,3,a,b,c,c,b,a,2,3,1,3,1,c,a,b,2,a,c,b,3,a,b,c,2,a,c,b,3,a,b,c,2,40,层次,栈状态,塔状态,层次,栈状态,塔状态,1,3,a,b,c,c,b,a,2,2,b,a,c,3,a,b,c,3,2,1,c,b,a,2,3,1,3,1,b,c,a,2,b,a,c,3,a,b,c,c,b,a,3,1,2,2,2,b,a,c,3,a,b,c,c,b,a,3,2,1,3,1,a,b,c,2,b,a,c,3,a,b,c,41,c,b,a,3,2,1,2,2,b,a,c,3,a,b,c,层次,栈状态,塔状态,c,b,a,3,2,1,3,a,b,c,1,层次,栈状态,塔状态,c,b,a,3,2,1,栈空,0,42,递归小结,优点：,结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,缺点：,递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,43,递归小结,解决方法：,在递归算法中消除递归调用，使其转化为非递归算法。,1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。,2.用递推来实现递归函数。,3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。,后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,44,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,将问题分为,a,个子问题，对这,a,个子问题分别求解。如果子问题的规模仍然不够小，则每个子问题再划分为,a,个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,2.2 分治法的基本思想,45,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治算法的程序具有递归的特点,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),46,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题，即该问题具有,最优子结构性质,利用该问题分解出的子问题的解可以合并为该问题的解；,该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑,贪心算法,或,动态规划,。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用,动态规划,较好。,47,分治法的基本步骤,divide-and-conquer,(P),if,(|P|=n,0,),adhoc,(P);/解决小规模的问题,divide,P into smaller subinstances P,1,P,2,.,P,a,；/分解问题,for,(i=1,i=,a,i+),y,i,=,divide-and-conquer,(P,i,);/递归的解各子问题,return,merge(y,1,.,y,a,);/将各子问题的解合并为原问题的解,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的,a,个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种,平衡,(balancing),子问题,的思想，它几乎总是比子问题规模不等的做法要好。,48,分治法的复杂性分析,一个分治法将规模为,n,的问题分成,a,个规模为,n,/,b,的子问题去解。设分解阀值,n,0,=1,，且,adhoc,解规模为,1,的问题耗费,1,个单位时间。再设将原问题分解为,a,个规模为,b,的,子问题以及用,merge,将这,a,个子问题的解合并为原问题的解需用,f(,n,),个单位时间。用,T(,n,),表示该分治法解规模为,|P|=,n,的问题所需的计算时间，则有：,通过迭代法求得方程的解：,注意,：,递归方程及其解只给出,n,等于,b,的方幂时,T(n),的值，但是如果认为,T(n),足够平滑，那么由,n,等于,b,的方幂时,T(n),的值可以估计,T(n),的增长速度。通常假定,T(n),是单调上升的，从而当,b,i,nb,i,+1,时，,T(b,i,)T(n)T(b,i,+1,),。,49,50,if,T,(,n,)=,aT,(,n,/,b,)+,f,(,n,)then,The Master Theorem,51,52,53,54,2.3,二分搜索技术,分析：,如果,n=1,即只有一个元素，则只要比较这个元素和,x,就可以确定,x,是否在表中。因此这个问题满足分治法的第一个适用条件,分析：,比较,x,和,a,的中间元素,amid,，若,x=amid,，则,x,在,L,中的位置就是,mid,；如果,xai,，同理我们只要在,amid,的后面查找,x,即可。无论是在前面还是后面查找,x,，其方法都和在,a,中查找,x,一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：,很显然此问题分解出的子问题相互独立，即在,ai,的前面或后面查找,x,是独立的子问题，因此满足分治法的第四个适用条件。,给定已按升序排好序的,n,个元素,a0:n-1,，现要在这,n,个元素中找出一特定元素,x,。,分析：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题,;,分解出的子问题的解可以合并为原问题的解；,分解出的各个子问题是相互独立的。,55,给定已按升序排好序的,n,个元素,a0:n-1,，现要在这,n,个元素中找出一特定元素,x,。,据此容易设计出,二分搜索算法,：,BinarySearch,(int a,int x,int n),/,在,a0=a1=.=an-1,中搜索,x,/,找到,x,时返回其在数组中的位置，否则返回,-1,int left=0;int right=n-1;,while,(left amiddle)left=middle+1;,else,right=middle-1;,return,-1;/,未找到,x,算法复杂度分析：,每执行一次算法的,while,循环，待搜索数组的大小减少一半。因此，在最坏情况下，,while,循环被执行了,O(log,2,n),次。循环体内运算需要,O(1),时间，因此整个算法在最坏情况下的计算时间复杂性为,O(log,2,n),。,例.在 中查找6,.,8,7,6,5,4,3,2,1,56,2.4,大整数的乘法,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),效率太低,分治法,:,a,b,c,d,X=,Y=,X=,a,2,n/2,+,b,Y=,c,2,n/2,+,d,XY=,ac,2,n,+(,ad,+,bc,)2,n/2,+,bd,复杂度分析,T(n)=O(n,2,),没有改进,57,由：,XY=,ac,2,n,+(,ad,+,bc,)2,n/2,+,bd,得：,XY=,ac,2,n,+(,a,-,b,)(,d,-,c,)+,ac,+,bd,)2,n/2,+,bd,或：,XY=,ac,2,n,+(,a,+,b,)(,c,+,d,)-,ac,-,bd,)2,n/2,+,bd,复杂度分析,T(n)=O(n,log3,)=O(n,1.59,),较大的改进,细节问题,：两个,XY,的复杂度都是,O(n,log3,),，但考虑到,a+c,b+d,可能得到,m+1,位的结果，使问题的规模变大，故不选择第,2,种方案。,为了降低时间复杂度，必须减少乘法的次数。,58,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),效率太低,分治法,:O(n,1.59,),较大的改进,更快的方法,?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。,最终的，这个思想导致了,快速傅利叶变换,(Fast Fourier Transform),的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在,O(nlogn,),时间内解决。,是否能找到线性时间的算法？目前为止还没有结果。,59,2.5,Strassen矩阵乘法,A,和,B,的乘积矩阵,C,中的元素,C,i,j,定义为,:,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C,i,j,，需要做,n,次乘法和,n,-1,次加法。因此，算出矩阵C的 个元素所需的计算时间为O(,n,3,),传统方法,60,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,分治法,由此可得：,复杂度分析,T(,n,)=O(,n,3,),没有改进,61,为了降低时间复杂度，必须减少乘法的次数。,对,变形,复杂度分析,T,(,n,)=O(,n,log7,)=O(,n,2.81,),较大的改进,62,传统方法,：,O(n,3,),分治法,:,O(n,2.81,),更快的方法,?,Hopcroft,和,Kerr,已经证明,(1971),，计算,2,个,矩阵的乘积，,7,次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算,22,矩阵的,7,次乘法这样的方法了。或许应当研究,或,矩阵的更好算法。,在,Strassen,之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是,O(n,2.376,),是否能找到,O(n,2,),的算法？目前为止还没有结果。,63,2.6,棋盘覆盖,在一个,2,k,2,k,个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的,4,种不同形态的,L,型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何,2,个,L,型骨牌不得重叠覆盖。,64,算法,当,k0,时，将,2,k,2,k,棋盘分割为,4,个,2,k-1,2,k-1,子棋盘,(a),所示。,特殊方格必位于,4,个较小子棋盘之一中，其余,3,个子棋盘中无特殊方格。为了将这,3,个无特殊方格的子棋盘转化为特殊棋盘，可以用一个,L,型骨牌覆盖这,3,个较小棋盘的会合处，如,(b),所示，从而将原问题转化为,4,个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘大小为,11,。,65,程序,代码,ChessBoard,(int tr,int tc,int dr,int dc,int size),/tr、tc：,棋盘左上角方格的行号、列号,/,dr、dc：,特殊方格的行号、列号,if,(size=1),return,;,int t=tile+;/L,型骨牌号，,tile,初值为1,int s=size/2;/,分割棋盘,/,用,L,型骨牌号覆盖左上角子棋盘,if,(dr tr+s&dc=tr+s&dc=tr+s&dc=tc+s),/,特殊方格在此棋盘中,chessBoard,(tr+s,tc+s,dr,dc,s);,else,/,用,t,号,L,型骨牌覆盖左上角,boardtr+stc+s=t;,/,覆盖本子棋盘中的其余方格,chessBoard,(tr+s,tc+s,tr+s,tc+s,s);,复杂度分析,T,(,n,)=,O,(4,k,),渐进意义下的最优算法,66,2,2,2,chessBoard,(0,0,0,1,2),chessBoard,(0,0,0,1,1),chessBoard,(0,0,0,1,2),1,chessBoard,(0,0,0,1,1),3,33,chessBoard,(0,0,0,1,2),1,chessBoard,(0,0,0,1,1),4,4,4,chessBoard,(0,0,0,1,2),1,chessBoard,(0,0,0,1,1),5,5,5,例,chessBoard,(0,0,0,1,4),67,2.7,合并排序,基本思想：,将待排序元素分成大小大致相同的,2,个子集合，分别对,2,个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,MergeSort,(int a,int left,int right),if,(leftright)/,至少有,2,个元素,int i=(left+right)/2;/,取中点,mergeSort,(a,left,i);,mergeSort,(a,i+1,right);,merge,(a,b,left,i,right);/,合并到数组,b,copy,(a,b,left,right);/,复制回数组,a,复杂度分析,T,(,n,)=,O,(,n,log,n,),渐进意义下的最优算法,68,A=;,;,;,;,;,;,;,;,;,;,;,;,;,;,Show Merge_Sort()running on the array,Example,;,;,;,;,69,复杂度,最坏时间复杂度：,O,(,n,log,n,),平均时间复杂度：,O,(,n,log,n,),辅助空间：,O,(,n,),稳定性：稳定,思考题：给定有序表,A1:n,，修改合并排序算法，求出该有序表的逆序对数。,70,2.8,快速排序,在快速排序中，记录的比较和交换是从两端向中间,进行的，关键字较大的记录一次就能交换到后面单,元，关键字较小的记录一次就能交换到前面单元，,记录每次移动的距离较大，因而总的比较和移动次,数较少。,qSort,(int p,int r),if,(pr),int q=,partition,(p,r);/,以,ap,为基准元素将,ap:r,划分成,3,段,ap:q-1,aq,和,aq+1:r,，使得,ap:q-1,中任何元素小于等于,aq,，,aq+1:r,中任何元素大于,aq,。下标,q,在划分过程中确定。,qSort,(p,q-1);/,对左半段排序,qSort,(q+1,r);/,对右半段排序,快速排序是对气泡排序的一种改进方法,它是由,C.A.R.Hoare,于,1962,年提出的,71,快速排序具有,不稳定性,。,函数,partition,的代码,2,5,5,6,7,8,完成,partition,(int p,int r),int i=p;,int j=r+1;,int x=ap;,/,将,x,的元素交换到右边区域,while,(,true,),while,(a+i x);,if,(i=j),break,;,swap,(a,i,j);,ap=aj;,aj=x;,return,j;,6,7,5,2,5,8,i+,j-;,初始序列,6,7,5,2,5,8 ,6,7,5,2,5,8,j-;,6,5,5,2,7,8,交换,i+;,i+;,i+;,j-;,6,5,5,2,7,8,例,用,快速排序法将6,7,5,2,5,8排序,72,randomizedPartition,(int p,int r),int i=,random,(p,r);,swap,(a,i,p);,return,partition,(p,r);,快速排序的,复杂度,快速排序算法的性能取决于划分的对称性。通过修改算法,partition,，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在,ap:r,中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。,最坏时间复杂度：,O,(,n,2,),平均时间复杂度：,O,(,nlogn,),稳定性：不稳定,73,快速排序时间复杂度的分析,最坏情况?,分割总是最不平衡,最好情况,?,每次将数组对半分割,最可能情况,?,介于上述两者之间,T,(1)=,(1),T,(,n,)=,T,(,n,-2)+(,n,),T,(,n,)=(,n,2,),T,(,n,)=2,T,(,n,/2)+,(,n,),T,(,n,)=(,n,log,n,),T,(,n,)=2,T,(,n,/,b,)+,(,n,),bb,ac,bc,ac,ac,bc,bc,output c,b,a,output,b,c,a,output,b,a,c,output,c,a,b,output,a,c,b,output a,b,c,Example,82,设树的高度为,h,，则：,n,!,2,h,log,(,n,!),h,由Stirling公式:,从而,:,定理 具有,n,！个叶结点,的决策树的高度为,(,nlogn,),83,2.9,顺序统计,给定线性序集中,n,个元素和一个整数,k,，,1kn,，要求找出这,n,个元素中第,k,小的元素,randomizedSelect,(int p,int r,int k),if,(p=r),return,ap;,int i=,randomizedpartition,(p,r);,j=i-p+1;/,基准元素,ai,的序数,if,(k=j),return,randomizedSelect,(p,i,k);,else,return,randomizedSelect,(i+1,r,k-j);,下面证明:在最坏情况下，算法,randomizedSelect,需要,O(,n,2,),计算时间,但在平均情况下，算法,randomizedSelect,可以在,O(,n,),时间内找出,n,个输入元素中的第,k,小元素。,84,RandomizedSelect,(),的时间复杂度,最坏情形,:,数组总被分为,1,:,n,-,1,T(,n,)=T(,n,-1)+O(,n,),=?,=O(,n,2,),比先排序还差,!,最好情形,:,数组总被分为,9:1,T(,n,)=T(9,n,/10)+O(,n,),=?,=O(,n,),(Master Theorem),优于排序,!,数组总被分为,99:1,会怎样,?,85,平均时间复杂度,假定要找的元素总落在较大的子数组中,:,下面用归纳法证明,T(,n,)=,O,(,n,),86,设存在数,c,，使得对,k,n,有：,T,(,k,),ck,，则：,87,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的,2,个子数组的长度都至少为原数组长度的,倍,(01,是某个正常数,),，那么就可以,在最坏情况下,用,O(,n,),时间完成选择任务。,例如，若,=9/10,，算法递归调用所产生的子数组的长度至少缩短,1/10,。所以，在最坏情况下，算法所需的计算时间,T(,n,),满足递归式,T(,n,)T(9,n,/10)+O(,n,),。由此,Master,定理可得,T(,n,)=O(,n,),。,寻找,基准,元素,88,将,n,个输入元素划分成,n/5,个组，每组,5,个元素，只可能有一个组不是,5,个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共,n/5,个。,递归调用,select,来找出这,n/5,个元素的中位数,(,如果,n/5,是偶数，就找它的,2,个中位数中较大的一个,),。以这个元素作为划分基准。,设所有元素互不相同。在这种情况下，,n/5,个中位数中有,(n-5)/10,个数大于基准,x,。因此，,n,个数中至少有3,(n-5)/10,个数大于基准,x,。同理，至少有,3,(n-5)/10,个元素小于基准,x。,而当,n75,时，,3(n-5)/10,n/4。,所以，按基准,x,划分所得的,2,个子数组的长度都至少缩短,1/4,。,89,select,(int p,int r,int k),if,(r-p75),/,用某个简单排序算法对数组,a,p:r,排序,;,bubbleSort,(p,r);,return,a,p+k-1;,/,将,a,p+5*i,至,a,p+5*i+4,的第,3,小元素,/,与,a,p+i,交换位置,;,/,找中位数的中位数，,r-p-4,即上面所说的,n-5,for,(int i=0;i=(r-p-4)/5;i+),int s=p+5*i;,t=s+4;,for,(int j=0;j3;j+),bubble,(s,t-j);/,冒泡3次即可找到第3小元素,swap,(,a,p+i,s+2);,x=,select,(p,p+(r-p-4)/5,(r-p+6)/10);/(r-p+6)/10=p+p+(r-p-4)/5/2+1,T(n/5),int i=,partition,(p,r,x),j=i-p+1;,if,(k=j),return,select,(p,i,k);/,T(3n/4),else return select,(i+1,r,k-j);,复杂度分析,T,(,n,)20,C,n,=,O,(,n,),上述算法将每一组的大小定为,5,，并选取,75,作为是否作递归调用的分界点。这两点保证了,T(n),的递归式中,2,个自变量之和,n/5+3n/4=19n/20=n,，,01,。这是使,T(n)=,O,(n),的关键之处。当然，除了,5,和,75,之外，还有其他选择。,90,第3章 动态规划,Those who cannot remember the past are doomed to repeat it.,-George Santayana,The life of Reason,Book I:Introduction and,Reason in Common,Sense(1905),91,算法总体思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，而问题的解可用子问题的解表示，即要解决的问题具有,最优子结构性质,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,92,但是经分解得到的子问题往往不是互相独立的。,在用分治法求解时,，,有些子问题被反复计算多次。这种性质称为,子问题的重叠性质,。,如果能够保存已解决的子问题的答案，而在需要时直接使用已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,n,=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,n/2,T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),T(n/4),T(n),算法总体思想,93,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,94,矩阵连乘问题,给定,n,个矩阵 ，其中 与 是可乘的，。考察这,n,个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积,如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少?,16000,10500,36000,87500,34500,设有四个矩阵,它们的维数分别是：,总共有五中完全加括号的方式:,95,穷举法,：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A,1,.A,k,)(A,k+1,A,n,),可以得到关于,P(n),的递推式如下：,生成函数法！,矩阵连乘问题的解,96,动态规划方法,将矩阵连乘积 简记为,A,i,:,j,，这里,i,j,考察计算,A,i,:,j,的最优计算次序。设这个计算次序在矩阵,A,k,和,A,k,+1,之间将矩阵链断开，,i,k,j,，则其相应完全,加括号方式为,计算量：,A,i,:,k,的计算量加上,A,k,+1:,j,的计算量，再加上,A,i,:,k,和,A,k,+1:,j,相乘的计算量,97,分析最优解的结构,特征：计算,A,i,:,j,的最优次序所包含的计算矩阵子链,A,i,:,k,和,A,k,+,1,:,j,的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,98,建立递归关系,设计算,A,i,:,j,，,1,i,j,n,，所需要的最少数乘次数,m,i,j,，则原问题的最优值为,m,1,n,当,i,=,j,时，,A,i,:,j,=A,i,，因此，,m,i,i,=0,，,i,=1,2,n,当,i,j,时，,故可以递归地定义,m,i,j,为：,这里 的维数为,的位置只有,种,可能,99,计算最优值,对于,1,i,j,n,不同的有序对,(,i,j,),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,100,matrixChain,(int n,int pn+1,int mn+1n+1,int sn+1n+1),for,(int i=1;i=n;i+)mii=0;/,填主对角线,d,1,for,(int r=2;r=n;r+)/,填次对角线,d,r,(r=2n),for,(int i=1;i=n-r+1;i+),/,填次对角线的各个元素,int