计算机算法设计与分析 第3章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,3,章 动态规划,1,学习要点,:,理解动态规划算法的概念。,掌握动态规划算法的基本要素,（,1,）最优子结构性质,（,2,）重叠子问题性质,掌握设计动态规划算法的步骤。,(1),找出最优解的性质，并刻划其结构特征。,(2),递归地定义最优值。,(3),以自底向上的方式计算出最优值。,(4),根据计算最优值时得到的信息，构造最优解。,2,通过应用范例学习动态规划算法设计策略。,（,1,）矩阵连乘问题；,（,2,）最长公共子序列；,（,3,）最大子段和,（,4,）凸多边形最优三角剖分；,（,5,）多边形游戏；,（,6,）图像压缩；,（,7,）电路布线；,（,8,）流水作业调度；,（,9,）背包问题；,（,10,）最优二叉搜索树。,3,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,4,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,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),5,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,算法总体思想,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),6,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,7,（,1,）单个矩阵是完全加括号的；,（,2,）矩阵连乘积 是完全加括号的，则 可,表示为,2,个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000, 10500, 36000, 87500, 34500,完全加括号的矩阵连乘积可递归地定义为：,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,完全加括号的矩阵连乘积,8,矩阵连乘问题,给定,n,个矩阵 ， 其中 与 是可乘的， 。考察这,n,个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积,9,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,A,n,，其中,Ai,与,Ai+1,是可乘的，,i=1,，,2,，,n-1,。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法,：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A1.,Ak,)(,Ak,+1An),可以得到关于,P(n),的递推式如下：,10,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,Ak,和,Ak,+1,之间将矩阵链断开，,i,kj,，则其相应完全,加括号方式为,计算量：,Ai:k,的计算量加上,Ak+1:j,的计算量，再加上,Ai:k,和,Ak+1:j,相乘的计算量,11,特征：计算,Ai:j,的最优次序所包含的计算矩阵子链,Ai:k,和,Ak+1:j,的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,分析最优解的结构,12,建立递归关系,设计算,Ai:j,，,1ijn,，所需要的最少数乘次数,mi,j,，则原问题的最优值为,m1,n,当,i=j,时，,Ai:j=Ai,，因此，,mi,i=0,，,i=1,2,n,当,ij,时，,可以递归地定义,mi,j,为：,这里 的维数为,的位置只有,种,可能,13,计算最优值,对于,1ijn,不同的有序对,(i,j),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,14,用动态规划法求最优解,void,MatrixChain,(,int,*p,，,int,n,，,int,*m,，,int,*s),for (,int,i = 1; i = n; i+) mii = 0;,for (,int,r = 2; r = n; r+),for (,int,i = 1; i = n - r+1; i+) ,int,j=i+r-1;,mij = mi+1j+ pi-1*pi*pj;,sij = i;,for (,int,k = i+1; k j; k+) ,int,t = mik + mk+1j + pi-1*pk*pj;,if (t 0) return mij;,if (i = j) return 0;,int,u =,LookupChain,(i,，,i) +,LookupChain,(i+1,，,j) + pi-1*pi*pj;,sij = i;,for (,int,k = i+1; k j; k+) ,int,t =,LookupChain,(i,，,k) +,LookupChain,(k+1,，,j) + pi-1*pk*pj;,if (t u) u = t; sij = k;,mij = u;,return u;,18,最长公共子序列,若给定序列,X=x,1,x,2,x,m,，则另一序列,Z=z,1,z,2,z,k,，是,X,的子序列是指存在一个严格递增下标序列,i,1,i,2,i,k,使得对于所有,j=1,2,k,有：,z,j,=,x,i,j,。例如，序列,Z=B,，,C,，,D,，,B,是序列,X=A,，,B,，,C,，,B,，,D,，,A,，,B,的子序列，相应的递增下标序列为,2,，,3,，,5,，,7,。,给定,2,个序列,X,和,Y,，当另一序列,Z,既是,X,的子序列又是,Y,的子序列时，称,Z,是序列,X,和,Y,的,公共子序列,。,给定,2,个序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,，找出,X,和,Y,的最长公共子序列。,19,最长公共子序列的结构,设序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,的最长公共子序列为,Z=z,1,z,2,z,k,，则,(1),若,x,m,=,y,n,，则,z,k,=,x,m,=,y,n,，且,z,k,-1,是,x,m,-1,和,y,n,-1,的最长公共子序列。,(2),若,x,m,y,n,且,z,k,x,m,，则,Z,是,x,m,-1,和,Y,的最长公共子序列。,(3),若,x,m,y,n,且,z,k,y,n,，则,Z,是,X,和,y,n,-1,的最长公共子序列。,由此可见，,2,个序列的最长公共子序列包含了这,2,个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,20,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用,cij,记录序列和的最长公共子序列的长度。其中，,X,i,=x,1,x,2,x,i,；,Yj,=y,1,y,2,y,j,。当,i=0,或,j=0,时，空序列是,X,i,和,Y,j,的最长公共子序列。故此时,Cij=0,。其它情况下，由最优子结构性质可建立递归关系如下：,21,计算最优值,由于在所考虑的子问题空间中，总共有,(,mn,),个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void,LCSLength,(,int,m,，,int,n,，,char *x,，,char *y,，,int,*c,，,int,*b),int,i,，,j;,for (i = 1; i = m; i+) ci0 = 0;,for (i = 1; i = n; i+) c0i = 0;,for (i = 1; i = m; i+),for (j = 1; j =cij-1) ,cij=ci-1j; bij=2;,else cij=cij-1; bij=3; ,构造最长公共子序列,void,LCS,(,int,i,，,int,j,，,char *x,，,int,*b),if (i =0 | j=0) return;,if (bij= 1) LCS(i-1,，,j-1,，,x,，,b);,cout,xi; ,else if (bij= 2) LCS(i-1,，,j,，,x,，,b);,else LCS(i,，,j-1,，,x,，,b);,22,算法的改进,在算法,lcsLength,和,lcs,中，可进一步将数组,b,省去。事实上，数组元素,cij,的值仅由,ci-1j-1,，,ci-1j,和,cij-1,这,3,个数组元素的值所确定。对于给定的数组元素,cij,，可以不借助于数组,b,而仅借助于,c,本身在时间内确定,cij,的值是由,ci-1j-1,，,ci-1j,和,cij-1,中哪一个值所确定的。,如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算,cij,时，只用到数组,c,的第,i,行和第,i-1,行。因此，用,2,行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至,O(min(m,n),。,23,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即,P=v,0,v,1,v,n,-1,表示具有,n,条边的凸多边形。,若,v,i,与,v,j,是多边形上不相邻的,2,个顶点，则线段,v,i,v,j,称为多边形的一条弦。弦将多边形分割成,2,个多边形,v,i,v,i+1,v,j,和,v,j,v,j,+1,v,i,。,多边形的三角剖分,是将多边形分割成互不相交的三角形的弦的集合,T,。,给定凸多边形,P,，以及定义在由多边形的边和弦组成的三角形上的权函数,w,。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,24,三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积,(A,1,(A,2,A,3,)(A,4,(A,5,A,6,),所相应的语法树如图,(a),所示。,凸多边形,v,0,v,1,v,n,-1,的三角剖分也可以用语法树表示。例如，图,(b),中凸多边形的三角剖分可用图,(a),所示的语法树表示。,矩阵连乘积中的每个矩阵,A,i,对应于凸,(n+1),边形中的一条边,v,i-1,v,i,。三角剖分中的一条弦,v,i,v,j,，,ij,，对应于矩阵连乘积,Ai+1:j,。,25,最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质。,事实上，若凸,(n+1),边形,P=v,0,v,1,v,n,-1,的最优三角剖分,T,包含三角形,v,0,v,k,v,n,，,1kn-1,，则,T,的权为,3,个部分权的和：三角形,v0vkvn,的权，子多边形,v,0,v,1,v,k,和,v,k,v,k,+1,v,n,的权之和。可以断言，由,T,所确定的这,2,个子多边形的三角剖分也是最优的。因为若有,v,0,v,1,v,k,或,v,k,v,k,+1,v,n,的更小权的三角剖分将导致,T,不是最优三角剖分的矛盾。,26,最优三角剖分的递归结构,定义,tij,，,1ijn,为凸子多边形,vi-1,vi,vj,的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形,vi-1,vi,具有权值,0,。据此定义，要计算的凸,(n+1),边形,P,的最优权值为,t1n,。,tij,的值可以利用最优子结构性质递归地计算。当,j-i1,时，凸子多边形至少有,3,个顶点。由最优子结构性质，,tij,的值应为,tik,的值加上,tk+1j,的值，再加上三角形,v,i-1,v,k,v,j,的权值，其中,ikj-1,。由于在计算时还不知道,k,的确切位置，而,k,的所有可能位置只有,j-i,个，因此可以在这,j-i,个位置中选出使,tij,值达到最小的位置。由此，,tij,可递归地定义为：,27,多边形游戏,多边形游戏是一个单人玩的游戏，开始时有一个由,n,个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“,+”,或“*”。所有边依次用整数从,1,到,n,编号。,游戏第,1,步，将一条边删除。,随后,n-1,步按以下方式操作：,(1),选择一条边,E,以及由,E,连接着的,2,个顶点,V1,和,V2,；,(2),用一个新的顶点取代边,E,以及由,E,连接着的,2,个顶点,V1,和,V2,。将由顶点,V1,和,V2,的整数值通过边,E,上的运算得到的结果赋予新顶点。,最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。,问题,:,对于给定的多边形，计算最高得分。,28,最优子结构性质,在所给多边形中，从顶点,i(1in),开始，长度为,j(,链中有,j,个顶点,),的顺时针链,p(i,，,j),可表示为,vi,，,opi+1,，,，,vi+j-1,。,如果这条链的最后一次合并运算在,opi+s,处发生,(1sj-1),，则可在,opi+s,处将链分割为,2,个子链,p(i,，,s),和,p(i+s,，,j-s),。,设,m1,是对子链,p(i,，,s),的任意一种合并方式得到的值，而,a,和,b,分别是在所有可能的合并中得到的最小值和最大值。,m2,是,p(i+s,，,j-s),的任意一种合并方式得到的值，而,c,和,d,分别是在所有可能的合并中得到的最小值和最大值。依此定义有,am1b,，,cm2d,(1),当,opi+s=+,时，显然有,a+cmb+d,(2),当,opi+s=*,时，有,minac,，,ad,，,bc,，,bd,mmaxac,，,ad,，,bc,，,bd,换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。,29,图像压缩,图象的变位压缩存储格式将所给的象素点序列,p1,p2,pn,0pi255,分割成,m,个连续段,S1,S2,Sm,。第,i,个象素段,Si,中,(1im),，有,l,i,个象素,且该段中每个象素都只用,bi,位表示。设 则第,i,个象素段,Si,为,设 ，则,hi,bi,8,。因此需要用,3,位表示,bi,如果限制,1,li,255,，则需要用,8,位表示,li,。因此，第,i,个象素段所需的存储空间为,li*bi+11,位。按此格式存储象素序列,p1,p2,pn,，需要 位的存储空间。,图象压缩问题要求确定象素序列,p1,p2,pn,的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过,256,位。,30,图像压缩,设,l,i,，,bi,，是,p1,p2,pn,的最优分段。显而易见，,l,1,，,b1,是,p,1,p,l1,的最优分段，且,l,i,，,bi,，是,p,l1+1,p,n,的最优分段。即图象压缩问题满足最优子结构性质。,设,si,，,1in,，是象素序列,p1,pn,的最优分段所需的存储位数。由最优子结构性质易知：,其中,算法复杂度分析：,由于算法,compress,中对,k,的循环次数不超这,256,，故对每一个确定的,i,，可在时间,O(1),内完成的计算。因此整个算法所需的计算时间为,O(n),。,31,电路布线,在一块电路板的上、下,2,端分别有,n,个接线柱。根据电路设计，要求用导线,(i,(i),将上端接线柱与下端接线柱相连，如图所示。其中,(i),是,1,2,n,的一个排列。导线,(i,(i),称为该电路板上的第,i,条连线。对于任何,1i(j),。,电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集,Nets=(i,(i),1in,的最大不相交子集。,32,记 。,N(i,j),的最大不相交子集为,MNS(i,j),。,Size(i,j)=|MNS(i,j)|,。,(1),当,i=1,时，,(2),当,i1,时，,2.1 j(i),。此时， 。故在这种情况下，,N(i,j)=N(i-1,j),，从而,Size(i,j)=Size(i-1,j),。,2.2 j(i),，,(i,(i),M,NS(i,j),。,则对任意,(t,(t),M,NS(i,j),有,ti,且,(t)(i),。在这种情况下,MNS(i,j)-(i,(i),是,N(i-1,(i)-1),的最大不相交子集。,2.3,若 ，则对任意,(t,(t),M,NS(i,j),有,t1,时,33,流水作业调度,n,个作业,1,，,2,，,，,n,要在由,2,台机器,M1,和,M2,组成的流水线上完成加工。每个作业加工的顺序都是先在,M1,上加工，然后在,M2,上加工。,M1,和,M2,加工作业,i,所需的时间分别为,a,i,和,b,i,。,流水作业调度问题要求确定这,n,个作业的最优加工顺序，使得从第一个作业在机器,M1,上开始加工，到最后一个作业在机器,M2,上加工完成所需的时间最少。,分析：,直观上，一个最优调度应使机器,M1,没有空闲时间，且机器,M2,的空闲时间最少。在一般情况下，机器,M2,上会有机器空闲和作业积压,2,种情况。,设全部作业的集合为,N=1,，,2,，,，,n,。,S,N,是,N,的作业子集。在一般情况下，机器,M1,开始加工,S,中作业时，机器,M2,还在加工其它作业，要等时间,t,后才可利用。将这种情况下完成,S,中作业所需的最短时间记为,T(S,t),。流水作业调度问题的最优值为,T(N,0),。,34,流水作业调度,设,是所给,n,个流水作业的一个最优调度，它所需的加工时间为,a,(1),+T,。其中,T,是在机器,M2,的等待时间为,b,(1),时，安排作业,(2),，,，,(n),所需的时间。,记,S=N-,(1),，则有,T=T(S,b,(1),),。,证明：,事实上，由,T,的定义知,T,T(S,b,(1),),。若,TT(S,b,(1),),，设,是作业集,S,在机器,M2,的等待时间为,b,(1),情况下的一个最优调度。则,(1),，,(2),，,，,(n),是,N,的一个调度，且该调度所需的时间为,a,(1),+T(S,b,(1),)a,(1),+T,。这与,是,N,的最优调度矛盾。故,T,T(S,b,(1),),。从而,T=T(S,b,(1),),。这就证明了流水作业调度问题具有最优子结构的性质。,由流水作业调度问题的最优子结构性质可知，,35,Johnson,不等式,对递归式的深入分析表明，算法可进一步得到简化。,设,是作业集,S,在机器,M2,的等待时间为,t,时的任一最优调度。若,(1)=i,(2)=j,。则由动态规划递归式可得,:,T(S,t)=,a,i,+T(S-i,b,i,+maxt-,a,i,0)=,a,i,+,a,j,+T(S-i,j,t,ij,),其中，,如果作业,i,和,j,满足,minb,i,a,j,min,b,j,a,i,，则称作业,i,和,j,满足,Johnson,不等式,。,36,流水作业调度的,Johnson,法则,交换作业,i,和作业,j,的加工顺序，得到作业集,S,的另一调度，它所需的加工时间为,T(S,t)=,a,i,+,a,j,+T(S-i,j,t,ji,),其中，,当作业,i,和,j,满足,Johnson,不等式时，有,由此可见当作业,i,和作业,j,不满足,Johnson,不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度,，使得作业,(i),和,(i+1),满足,Johnson,不等式。进一步还可以证明，调度满足,Johnson,法则当且仅当对任意,i2,n,时，算法需要,(,n2,n,),计算时间。,40,算法,改进,由,m(i,j),的递归式容易证明，在一般情况下，对每一个确定的,i(1in),，函数,m(i,j),是关于变量,j,的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数,m(i,j),由其全部跳跃点唯一确定。如图所示。,对每一个确定的,i(1in),，用一个表,pi,存储函数,m(i,，,j),的全部跳跃点。表,pi,可依计算,m(i,，,j),的递归式递归地由表,pi+1,计算，初始时,pn+1=(0,，,0),。,41,一个例子,n=3,，,c=6,，,w=4,，,3,，,2,，,v=5,，,2,，,1,。,x,(0,0),m(4,x),x,(2,1),m(4,x-2)+1,x,(0,0),(2,1),m(3,x),(3,2),x,m(3,x-3)+2,(5,3),x,(0,0),(2,1),m(2,x),(3,2),(5,3),x,m(2,x-4)+5,(4,5),(6,6),(7,7),(9,8),x,(0, 0),(2, 1),m(1,x),(3,2),(5,3),(4,5),(6,6),(7,7),(9,8),x,(0,0),(2,1),m(3,x),x,(0,0),(2,1),m(2,x),(3,2),(5,3),42,函数,m(i,j),是由函数,m(i+1,j),与函数,m(i+1,j-,wi,)+vi,作,max,运算得到的。因此，函数,m(i,j),的全部跳跃点包含于函数,m(i+1,，,j),的跳跃点集,pi+1,与函数,m(i+1,，,j-,wi,)+vi,的跳跃点集,qi+1,的并集中。易知，,(s,t),qi+1,当且仅当,wi,s,c,且,(s-,wi,t-vi),pi+1,。因此，容易由,pi+1,确定跳跃点集,qi+1,如下,qi+1=pi+1,(,wi,vi)=(j+,wi,m(i,j)+vi)|(j,m(i,j),pi+1,另一方面，设,(a,，,b),和,(c,，,d),是,pi+1,qi+1,中的,2,个跳跃点，则当,c,a,且,db,时，,(c,，,d),受控于,(a,，,b),，从而,(c,，,d),不是,pi,中的跳跃点。除受控跳跃点外，,pi+1,qi+1,中的其它跳跃点均为,pi,中的跳跃点。,由此可见，在递归地由表,pi+1,计算表,pi,时，可先由,pi+1,计算出,qi+1,，然后合并表,pi+1,和表,qi+1,，并清除其中的受控跳跃点得到表,pi,。,算法,改进,43,一个例子,n=5,，,c=10,，,w=2,，,2,，,6,，,5,，,4,，,v=6,，,3,，,5,，,4,，,6,。,初始时,p6=(0,0),，,(w5,v5)=(4,6),。因此，,q6=p6,(w5,v5)=(4,6),。,p5=(0,0),(4,6),。,q5=p5,(w4,v4)=(5,4),(9,10),。从跳跃点集,p5,与,q5,的并集,p5,q5=(0,0),(4,6),(5,4),(9,10),中看到跳跃点,(5,4),受控于跳跃点,(4,6),。将受控跳跃点,(5,4),清除后，得到,p4=(0,0),(4,6),(9,10),q4=p4,(6,，,5)=(6,，,5),，,(10,，,11),p3=(0,，,0),，,(4,，,6),，,(9,，,10),，,(10,，,11),q3=p3,(2,，,3)=(2,，,3),，,(6,，,9),p2=(0,，,0),，,(2,，,3),，,(4,，,6),，,(6,，,9),，,(9,，,10),，,(10,，,11),q2=p2,(2,，,6)=(2,，,6),，,(4,，,9),，,(6,，,12),，,(8,，,15),p1=(0,，,0),，,(2,，,6),，,(4,，,9),，,(6,，,12),，,(8,，,15),p1,的最后的那个跳跃点,(8,15),给出所求的最优值为,m(1,c)=15,。,44,上述算法的主要计算量在于计算跳跃点集,pi(1in),。由于,qi+1=pi+1,(,w,i,，,v,i,),，故计算,qi+1,需要,O(|pi+1|),计算时间。合并,pi+1,和,qi+1,并清除受控跳跃点也需要,O(|pi+1|),计算时间。从跳跃点集,pi,的定义可以看出，,pi,中的跳跃点相应于,x,i,x,n,的,0/1,赋值。因此，,pi,中跳跃点个数不超过,2,n-i+1,。由此可见，算法计算跳跃点集,pi,所花费的计算时间为,从而，改进后算法的计算时间复杂性为,O(2,n,),。当所给物品的重量,w,i,(1in),是整数时，,|pi|c+1,，,(1in),。在这种情况下，改进后算法的计算时间复杂性为,O(min,nc,2,n,),。,算法,复杂,度,分析,45,最优二叉搜索树,二叉搜索树,（,1,）若它的左子树不空，则左子树上,所有,节点的值,均小于,它的根节点的值；,（,2,）若它的右子树不空，则右子树上,所有,节点的值,均大于,它的根节点的值；,（,3,它的左,、,右子树也分别为二叉排序树,45,12,53,3,37,24,100,61,90,78,在随机的情况下，二叉查找树的平均查找长度,和 是等数量级的,46,搜索成功与不成功的概率,二搜索树的期望耗费,有 个节点的二叉树的个数为：,穷举搜索法的时间复杂度为指数级,二叉,搜索树的期望耗费,47,二叉,搜索树的期望耗费示例,48,最优二叉搜索树,最优二叉搜索树,T,ij,的平均路长为,p,ij,，则所求的最优值为,p,1,n,。由最优二叉搜索树问题的最优子结构性质可建立计算,p,ij,的递归式如下,记,w,i,j,p,i,j,为,m(i,j),，则,m(1,n)=w,1,n,p,1,n,=p,1,n,为所求的最优值。计算,m(i,j),的递归式为,注意到，,可以得到,O(n,2,),的算法,49,50,