佛山科学技术学院-期末总复习-学长整理-终极版-算法设计与分析

1、递归与分支策略Strassen矩阵乘法是利用分治法实现的算法。使用分治法求解不需要满足的条件是子问题必须是一样的线性时间选择算法：时间复杂度O(a)=n,时间复杂度O(11)=nlogn最接近点对问题算法：时间复杂度05=：递推公式求时间复杂度的：用主定理秒杀，见算法ppt第二章，简而言之就是a)n=logbacompaiewithf(n)i.nf(n),贝1O(n)=logbaii.n=f(n),贝1O(n)=logba*logn分治算法的基本步骤包括：分解、解决和合并动态规划最大子段和问题，时间复杂度为n动态规划法的4个步骤设计是什么？找出最优解的性质，并刻画其结构特征递归地定义最优值以自

2、底向上的方式计算出最优值根据计算最优值时得到的信息，构造矩阵连乘(M3),最长公共子序列(mn),(m+n),(minm,n),凸多边形最优三角剖分(n),多边形游戏(”3),图像压缩(11),电路布线(M2),(11),流水作业调度(nlogii),0-1背包问题(2An),(2An,nc),最优二叉搜索树(M3)。动态规划算法的两个基本要素最优子结构性质重叠子问题性质用动态规划策略求解最长公共子序列问题：给出计算最优值的递归方程。给定两个序列X=B,C.D,A,Y=A,E,UE,请采用动态规划策略求出其最长公共子序列，要求给出过程。ioiff=()”_/=0,0and,max(c/,J-I

3、,ci一I,J)iffJ0and.i01234JYABCB0X010001B001112C0013D001214A01121最长公共子序歹I1：n)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i近似算法九、算法优化策略十、在线算法设计十一、其他算法由若干条指令组成的又穷序列，且满足输入、输出、确定性、有限性四个特性。分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。直接或间接调用自身的方法叫递归算法以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法动态规划的子问题

4、重叠贪心算法的选择性质是贪心选择性质、动态规划法的选择性质是最优子结构性质。计算一个算法时间复杂度通常可以计算的循环次数、基本操作的频度或计算步数&快速排序算法的性能取决于划分的对称性O的定义：O(g(n)=f(n)|存在正常数c和110使得对所有n=nO有：0=f(n)=nO有：0=cg(n)2简单地说就是log底数为括号里面的倒数，真数为倍数21.22.23.24.25.26.27.有8个作业1,2,-,8要在由2台机器Ml和M2组成的流水线上完成加工。每个作业加工的顺序都是先在Ml上加工，然后在M2上加工。Ml和M2加工作业1所需的时间分别为：Ml102S1269414M25711516

5、31113作业12345678给出一个最优调度方案，使得从第一个作业在机器Ml上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少，并计算所需的最少时间。最优调度方案为(6分)27548163所需的最少时间为：73(4分在前一问正确的前提下方可得分)28.29根据优先队列式分支限界法，求下图中从vl点到，9点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用X标记，获得中间解的结点用单圆30.十二、程序题合并排序mergeSoil(inta,hitleft,iiitright)if(leftright)iiiti=(left+right)/2;mergeSort(a,l

6、eft,I);mergeSort(a,i+1,light);merge(a,b,left,i,right);copv(a,b,left,light);快速排序qSoil(iiita,intp,iiiti)iiitq=parition(a,p,r);qSort(a,p,q-1);qSort(a,q+1,r)；iiitparition(inta,intp,intr)iiitstart=p,end=q;while(stailend)while(stailend&astart=aend)end;returnstart;贪心算法：背包问题voidKnapsack(intn,floatM,floatv,f

7、loatw,floatx)Sort(ii,v,w)Ult1;for(i=l;i=n;i+)xi=0;floatc=M;fbr(i=l;ic)break;xi=l；C-=W1；if(i二fj)Ai=true;Jzi：elseAi二false;动态规划：最大子段和intMaxSum(intn,inta)intsum=0,b=0;for(intj=l;j0)b+=aj;elseb=ai;if(bsum)sum=b;returnsum;intMaxSum(inta,intleft,intright)intsum=0;if(left=right)/序列长度为1if(aleft0)sum二aleft:el

8、seintcenter二(left+right)/2;leftsum二MaxSum(a,left,center);rightsum二MaxSum(a,center+1,right);si=0,lefts=0;for(I二center;i=left:-i)lefts+二ai:if(leftssi)si=lefts;s2=0,rights=0;for(j二center+1;j二right;+j)rights+二aj;if(rightss2)s2二rights;sum=si+s2;if(sumleftSum)sum二leftsum;if(sumrightSum)sum二rightsum;returnsum;I递归：全排列voidperm(Typelist,intk,intm)产生listk：m的所有排列if(k二二m)只剩下一个