清华大学算法课13课件

算法与数据结构

AlgorithmsandDataStructures

第十三章算法分析与设计技术

AlgorithmAnalysisandDesignTechniques

13.1递归算法的分析13.2递归式求解13.3大递归式的一般解13.4分而治之法13.5动态规划法13.6贪心法13.7搜索算法13.1递归算法的分析考虑一个归并排序算法：Listmergesort(List

L,intn){if(n==1)returnL;breakLinto2halves,L1andL2,eachoflengthn/2;returnmerge(mergesort(l1,n/2),mergesort(l2,n/2));}//设T(n)是最坏情况下的时间复杂度。显然：

T(n)=1ifn=1;T(n)<=2T(n/2)+cnifn>1我们前面已做过很多递归算法的分析，给出了相应的递归式；例如：Hanoi塔：T(0)=0T(n)=2T(n-1)+1折半查找：T(0)=0;T(1)=1;T(n)=T(n/2)+1;最复杂的是快速排序。13.2递归式求解有三种方法：(1).猜一个解f(n)，代入递归式，对n归纳证明T(n)<=f(n)，同时确定F(n)中的不定系数，使对所有的n有T(n)<=f(n)。(2).展开递归式，直到式子的右边的T(m)均为初试递归式（如T(0),T(1)）.(3).一般求法。1猜解：

T(n)=1ifn=1;T(n)<=2T(n/2)+cnifn>1设T(n)=a.n.logn+b

归纳基础：当n=1时b>=1设对所有的k<n有a.k.logk+b>=T(k)当k=n时：T(n)<=2T(n/2)+cn2.展开递归式13.3大递归式的一般解考虑递归算法：T(1)=1把大小为n的问题，分解为a个大小为n/b的子问题，划分问题和合并子问题的解所做工作量是d(n).则：T(1)=1T(n)=aT(n/b)+d(n)d(n)成为驱动函数对上一个递归式，a=b=2,d(n)=cn展开递归式：特解ParticularSolution通解HomogeneousSolution下面考虑特解：如果d(n)是积的形式，如(xy)k=xkyk

则特解所以考虑3种情况下的特解：若：a>d(b)2.若：a<d(b),3若：a=d(b)，特别当例1：

T(1)=1T(n)=4T(n/2)+nT(n)=4T(n/2)+n2T(n)=4T(n/4)+n3由于三个式中：a=4,b=2,它们的通解都是n2;d(n)=n,所以d(b)=2,因a=4>d(b)(2)d(n)=n2,所以d(b)=4,因a=4=d(b)(3)T(n)=4T(n/4)+n3d(n)=n3,所以d(b)=8,因a=4<d(b)

特解是：O(d(n))=n3以上讨论的是d(n)是n的积的形式，下面考虑非积形式。例2：

T(1)=1T(n)=3T(n/2)+2n1.5

2n1.5不是n的积的形式，但n1.5是，令U(n)=T(n)/2U(1)=1/2U(n)=3U(n/2)+n1.5如果U（1）=1，则通解是：nlog3=n1.59因U(1)=1/2，所以通解是：n1.59/2a=3,b=2,d(n)=n1.5

，d(b)=21.5=2.82,a>d(b)所以特解是：n1.59所以T(n)=O(n1.59)例3：

T(1)=1T(n)=2T(n/2)+nlogn显然通解是n。a=b=2,d(n)=nlogn

不是n的积。特解：13.4分而治之法分而治之就是将大的问题分解小的子问题分别解决，最常用的办法是递归算法。在前面我们已设计了许多递归算法，诸如：Hanoi塔，快速排序，归并排序，二叉树遍历，dfs，等等。下面在看几个例子，它们比较特殊例4：两个n位正整数相乘，这两个数很大，大到计算机内部无法表示。为简化问题，设n是2的幂。X=ABY=CDX=A10n/2+BY=C10n/2+DXY=AC10n+(AD+BC)10n/2+BD算法分析：位乘次数T(1)=1T(n)=4T(n/2)+cnT(n)=O(n2)改进：XY=AC10n+[(A-B)(D-C)+AC+BD)]10n/2+BDT(1)=1T(n)=3T(n/2)+cnT(n)=O(n1.59)

以上公式已说明了递归算法的三要素。算法Voidmult-Big-Num(&c[],x[],y[],n){bytem1[],m2[],m3[];byteA[n/2],B[n/2],C[n/2],D[n/2];c[]=newbyte[2*n];if(n==1)if(x!=0&&y!=0)c[]=multy(x,y,1);elsec[]=0;else{

A=leftn/2digitsofx[];B=rightn/2digitsofx[];C=leftn/2digitsofy[];D=rightn/2digitsofy[];mult-big-num(&m1,A,C,n/2);mult-big-num(&m2,A-B,D-C,n/2);mult-big-num(&m3,B,D,n/2);c=m1;c=left-shift(c,n/2);c+=m1+m2+m3;c=left-shift(c,n/2);c+=m3;

//m1*10n+(m1+m2+m3)*10n/2+m3}}

例5：网球循环赛的安排，每个选手每天只能参赛一场，如有n个选手，需要进n-1天。为简单起见，设n是2的幂。（1）最简问题及其解：n=2,（2）问题的划分：将n个分成两组，每组n/2人，进行循环比赛。（3）解的合成：21121天

21121天23414341232112341232143+212213443加第1行：12第2行：第1行左循环位移23414341232167858785676556786785785685671234234134124123加第1行：1234第2行：第1行左循环位移第3行：第2行左循环位移第4行：第3行左循环位移+413.5动态规划法(DynamicProgramming)在本节中我们通过一些列子说明什么是动态规划法。例6：斐波拿契数列：

f(0)=0,f(1)=1f(n)=f(n-1)+f(n-2);510211010433221问题分解解的合成递归子问题图递归求解如图：其中f(3)重复计2次，f(2)重复计算3次当n增大时，这样的重复计算会按指数级增长。如果我们把子问题的解记录下来，当需要时，直接引用，就可避免重复计算。当求一个子问题P的解时,它可能用到子问题P1，P2，…，Pk的解，在递归算法中P1，P2，…，

Pk的解是递归调用算法计算出来的，我们现在希望能从表中找到他们的解，而不是再计算。这样就需要搞清楚所有子问题间的依赖关系。我们用一个有向图表示这种关系。称此图为子问题图（Subproblem

Garph）012345从最简单问题开始，我们由底向上逐层把子问题的解添在一个表中，在合成解时，从表中查找所需要的下层的子问题的解即可。这样的方法是最基本的动态规划法。规划的另一个含义是在多个候选者中选择最好的。Fibonacci数列问题的子问题图：012345求子问题解的顺序是按逆拓扑序进行的。例7：我们已熟悉的一个问题：求组合数：4,23,23,12,22,12,12,01,11,01,11,0递归求解过程递归算法的动态规划版递归算法:Int

comb(int

m,intn){if(m==0||m==n)return1;return(comb(m-1,n-1)+comb(m,n-1));}//ADTDictionaryis

//设一个ADTDictionary

Data:Setofsubproblem’sresults;

Operations:

store(sbp,rslt);//存储子问题sbp的解rslt

member(sbp);//检查sbp的解是否已在字典中

retrieve(sbp);//取出sbp的解ENDADTDictionary动态规划算法:dic是ADTDictionaryInt

comb(int

m,intn){if(m==0||m==n)rslt=1;else{if(!dic.member((m-1,n-1)))rslt1=comb(m-1,n-1);elserslt1=dic.retrieve((m-1,n-1));if(!dic.member((m,n-1)))rslt2=comb(m,n-1);elserslt2=dic.retrieve((m,n-1));

rslt=rslt1+rslt2;}

dic.store((m,n),rslt);}//如果问题图很清楚，可以直接按该图的逆拓扑序遍历求解各子问题。通常dic是一个数组（一维或二维）1,02,03,04,01,12,13,14,12,23,24,2子问题图4,23,23,12,12,21,11,04,03,02,0拓扑序列之一nm1234564321011111111112345636101541020515For(j=1;j<=n;j++)c[0][j]=1;For(i=0;i<=m;i++)c[i][j]=1;For(i=1;i<=m;i++)For(j=i+1;j<=n;j++)c[i][j]=c[i][j-1]+c[i-1][j-1]算法分析：梯形计算mn012345543211111111111233464510试一试，只用一维数组如何计算105最优二查查找树二叉查找树ringhasthingcabbagetalkofwalrusandsaidkingtimecomethepigwing平均查找长度：其中：pi

是查找第i个对象的概率，ci

是比较次数。

例：Key pi

比较ci piciAnd .150 4 .600Cabbage .025 3 .075Come .050 4 .200Has .025 2 .050King .050 4 .200Of .125 3 .375Pig .025 4 .100Ring .075 1 .075Said .075 4 .300Talk .050 3 .150Key pi

比较ci piciThe .150 4 .600Thing .075 2 .150Time .050 2 .100Walrus .025 3 .075Wing .050 4 .200平均查找长度：total=3.250显然这不是一个最优二叉查找树。关键字集：k1,k2,k3,…..,kn,[ki<ki+1:i=1,2,…,n-1]查找概率：p1,p2,p3,…..,pn

[权]子问题（low,high）:

构造klow,klow+1,...,khigh的最优二叉查找树。我们采用以下表示：1A(low,high,r)是以kr为根的子问题（low,high）的最小平均查找长度。2A(low,high)是子问题（low,high）的最小平均查找长度。3p(low,high)=plow+plow+1+…+phigh,被查找key在klow,klow+1,...,khigh的概率。A(l,h,r)=A(l,r-1)+A(r+1,h)+p(l,r)r=l,l+1,…,hA(l,h)=min{A(l,h,r)|l<=r<=h}根据这两个式子我们可以设计一个递归算法计算A(1,n),但其中有许多的A(s,t)需要重复计算。KrKl,…,Kr-1Kr+1,…,Kh平均查找长度：A(l,r-1)=cost[l][r-1]平均查找长度：A(r1,h)=cost[r-1][h]lhA(l,r-1)A(r+1,h)0n+1(1,n)最终结果lowhigh下三角部分：l>h,对应的子问题是空树。只需要计算上三角。Cost[k][k]=pkCost[k][k-1]=000p10p20P30P40P50P60P70p80

0123456780123456789子问题的求解次序For(i=n-1;i>0;i--)For(j=i+1;j<=n;j++)CalculatesA(i,j)设cost[][]数组（存放A(l,h),(n+2)*(n+1)）和root[][]数组（记录子问题(l,h)的根(n+2)*(n+1)）,prob[](n,存放pi)。动态规划算法：VoidoptimalBST(prob,n,cost,root){for(low=n+1;low>=1;low--)for(high=low-1;high<=n;high++)

destChoice(prob,cost,root,low,high);}VoiddestChoice(prob,cost,root,low,high){if(low>high)

bestCost=0;bestRoot=-1;//空

elsebestCost=MAX;for(r=low;r<=high;r++){

rCost=p(low,high)+cost[low][r-1]+cost[r+1][high];if(rCost<bestCost){

bestCost=rCost;bestRoot=r;}}cost[low][high]=bestCost;root[low][high]=bestRoot;}算法分析：bestChoice():T(l,h)=h-l<noptimalBST

调用n*n次bestChoice()

所以T(n)=O(n3)根据root[][]，很容易构造出最优二叉查找树（递归算法）。子问题（l,h）

1.若l>h:空树；

2.问题划分：构造子树（l,h），root[l][h]=k,=>

构造子树

(l,k-1)[LT]和子树(k+1,h)[RT]3.解的合成：构造根Kk

，LT做为左子树，RT作为右子树。

13.6贪心法(GreedyAlgorithms)

我们已经接触过的贪心算法有Dijkstra[单源最短路径]算法和Kruscal算法[最小生成树]。贪心法在当前步骤，只考虑当前的最优解，而不考虑以后的情况。例8：找币问题：有硬币1角，6分，1分3种，如何找出1角8分？硬币数越少越好。贪心法：步骤1：1个1角，差8分步骤2：1个6分，差2分步骤3：2个1分，结束；共用4个硬币。最优解是：

3个6分。例9：用贪心算法解决构造最优二叉查找树问题。对子问题（l,h），选取kl,kl+1,…kh,中权最大的kr(l<=r<=h)为根.递归算法：递归出口：l>h,空树；问题划分：在kl,kl+1,…kh,中找出权最大的kr

，分为子问题（l,r-1）和（r+1,h）;解的合成：kr做根，T(l,r-1)做左子树，T(r+1,h)做右子树；数组key[1…n],p[1…n](key的权)算法：BTNode

bestBST(int

low,inthigh){if(low>high)returnNULL;r=low;for(i=low+1;i<=high;i++)//找最大权的位置

if(p[i]>p[r])r=i;root=newBTNode(key[r]);//新根

root.lchid=bestBST(low,r-1);

root.rchild=bestBST(r+1,high);returnroot;}例10：Key:ABCDEP2/155/154/151/153/15贪心算法构造的二叉查找树动态规划算法构造的BACEDA(n)=5/15+(2/15+4/15)*2+3/15*3+1/15*4=5/15+12/15+9/15+4/15=2CBEDAA(n)=4/15+(5/15+3/15)*2+(2/15+1/15)*3=4/15+16/15+9/15=1.93313.7搜索算法状态（Status）:问题在某一时刻的状态(属性值集合)。列11：将A,B放在该网格中，有12种状态。状态空间（StatusSpace）:所有状态的集合。状态变迁（产生式）：有一个状态变为另一个状态的规则。开始状态（InitialStatus）：问题的初始状态。终止状态(EndStatus)：问题的目标状态。例12：4皇后问题：ABABABABABBABABABABABAAB4*4网格状态：状态空间：16*15*14*12个状态开始状态：空网格。终止状态：状态变迁：状态可达树：从初始状态开始，按状态变迁产生下层状态，构成的树，叶结点是终止状态或祖先出现过的状态。例13：

4皇后问题：问题的求解从根开始，在可达树中搜索终止状态。深度优先搜索算法思想：BooleandfsSearch(S){

if(SisinF)returntrue;//F:终止状态集

setStobeVisited;for(eachS’snextstatueS’){S’=generateNext(S);if(S’isnotVisited){rslt=dfsSearch(S’);

if(rslt)break;}//去掉此句就是详尽搜索

}returnrslt;}算法是一边搜索一边创建后继状态，而不是先创建状态可达树，然后再搜索。开始时只有一个初始状态。广度优先搜索算法思想：BooleanbfsSearch(S0){

//S0是初始状态

Q=newQ(n);Q.entre(S0);while(!Q.empty()){S=Q.out();

if(SisinF)returntrue;//F:终止状态集

setStobeVisited;for(eachS’snextstatueS’){S’=generateNext(S);if(S’isnotVisited)Q.entre(S’);}//while

returnfalse;}有界深度优先搜索算法思想：如果弧上有权（默认为1），在搜索中从S0到当前状态S的路径长度为length(S).给定一个len，搜索到S，其路径长度大于len，就不再向前搜索，退回上一状态。BooleandfsSearch(S，len){

if(SisinF)returntrue;//F:终止状态集

setStobeVisited;for(eachS’snextstatueS’){S’=generateNext(S);if(S’isnotVisited&&length(S’)<len)returndfsSearch(S’);}returnfalse;}例14：迷宫问题：已知从入口到出口至少有一条路径的路径长度不超过len。