算法设计期末复习总结

分治法：计算方向：自顶向下；分为3个步骤：divide:整个问题划分为多个子问题；conquer求解每个子问题combine合并子问题的解，形成原问题的解设输入大小为n，T(n)为时间复杂性，当n<c,T(n)=(1);总之：(1) ifn<cT(n)=aT(n/b)+D(n)+C(n).1同阶。定义：e(f(n))={g(n)|ЭC1,C2>0,n0;当n>=n0,C1f(n)<=g(n)<=C2f(n)}称为与f(n)同阶。例题：证明,其中证:由于，，所以。2、高阶。定义：Ω（f（n））={g(n)|ЭC1,C2>0,n0;当n>=n0,0<=g(n)<=C2f(n)}称为比f(n)高阶。二分查找：BinarySearch(max,min,des)mid-<(max+min)/2while(min<=max)mid=(min+max)/2ifmid=desthenreturnmidelseifmid>desthenmax=mid-1elsemin=mid+1；returnmaxO(logn)归并算法（mergesort）：输入：Ap,r：欲排序数据在数组A中。输出：Ap,r：排序后的数据。方法： Merge-Sort(A,p,r)ifp<rthenq(p+r)/2Merge-Sort(A,p,q)Merge-Sort(A,q+1,r)Merge(A,p,q,r)。*Merge算法十分简单，需要O(n)次比较。*若要排序存储在数组A的n个数,只需调用Merge-Sort(A,1,n)。2.Merge-Sort的分析 ·Ifn=1,T(n)=(1) ·Divide阶段的时间复杂性:D(n)=(1) ·Conquer阶段的时间复杂性:2T() ·Combine阶段的时间复杂性:C(n)=(n)(1) ifn=1·T(n)=2T(n/2)+(n)+(1) ifn>1 ·使用循环展开法求解T(n)=(n)。快速排序算法(Quick-Sort):描述：有数组A[p….r]q=(p+r)/2;1).divide:把数组A[p…r]划分为两个非空数组A1[p…q],A2[q+1,r];使得A1中的每个数都小于A2中的；2).conquer:递归调用排序算法排序A1，A2；3).combine:将两个已经排好序的算法合并算法详细:Quick_sort(A[],p,r)Ifp<rThenq=partition(A[],p,r)Quick_sort(A[],p,q)Quick_sort(a[],q+1,r);Partition算法:Partition(a[],p,r)X=a[p]i=p-1;j=r+1;repaeatj--untila[j]<=x;repeati++untila[i]>=x;ifi<jthenexchangea[i]a[j]elsereturnj;将数组A有序排序,小的数放在前面A[i]>=X>=A[j];最坏时间复杂性:(n2)划分平衡时间复杂性:(nlgn)动态规划技术(DynamicProgramming):适用：当一个优化问题可以分为多个子问题，子问题的解被重复使用。满足条件：1.问题据有优化子结构(Optimalsubstructure)2.有重叠子问题(Overlappingsub-problems)优化结构：如果一个问题的优化解包含了他的子问题的优化解，则称该问题据具有优化子结构；特点：求解每个子问题仅一次，并保存结果，以后用到时直接存取，不重复计算，节省时间。计算方向：自底向上步骤：分析优化解的结构递归定义最优解的代价；自底向上的计算优化解的代价保存，并获取构造最优解的信息；根据构造最优解的信息构造优化解；矩阵链乘积(Matrix-chainMultiplication)(~)优化解的代价方程：假设：m[I,j]=计算Ai-j的最小乘法数=0；m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj,m[i,j]=0ifi=jminik<j{m[i,k]+m[k+1,j]+pI-1pkpj}ifi<j时间复杂性T(n)=0(n3)空间复杂性S(n)=0(n2)最长公共子序列问题步骤：1.问题定义2.建立求解LCS长度的递归方程3.LSC长度的计算4.构造最优解0-1背包最优子结构：问题分析：令f(i,j)表示在前i(0≤i<n)个物品中能够装入容量为j(0≤j≤W)的背包中的物品的最大价值，则可以得到如下的动态规划函数: f[i,j]=0(i=0ORj=0)f[i,j]=f[i-1,j]j<wi① f[i,j]=max{f[i-1,j],f[i-1,j-wi]+vi}j>wi②伪代码：f[0,j]=0Fori=1tonForj=0toWf[i,j]=max{f[i-1,j],f[i-1,j-wi]+vi}returnF[n,W]问题的解为f[n,W]Geedy算法基本思想：1.求解最优化问题的算法包含一些列步骤2.每一步都有一组选择3.做出在当前看来最好的选择；4.希望做出局部优化选择达到全局优化选择*Greedy算法不一定总产生优化解Greedy算法产生优化解的条件：1.问题具有优化子结构2.贪心选择性贪心选择性：若一个优化问题的全局优化解可以通过局部优化解选择得到。*Greedy算法与动态规划方法的不同动态规划：每一步作一个选择—依赖于子问题的解。Greedy方法:每一步作一个选择—不依赖于子问题的解。*一个问题是否具有Greedy选择性需要证明。活动任务安排GreedyAction(s,f，n)//s[1..n]、f[1..n]分别代表n项活动的起始时间和结束时间,并且满足f[1]≤f[2]≤…≤f[n]j:=1,solution:={1}//解向量初始化forifrom2tondoifsi≥fjthensolution:=solution∪{j};//将j加入解中j:=i;end{if}end{for}return(solution);end{GreedyAction}时间复杂度：T(n)=O(n)(排序时)T(n)=O(nlogn)(未排序时)3.优化子结构定义2若一个优化问题的优化解包括它的子问题的优化解，则称其具有优化子结构。4.与动态规划方法的比较·动态规划方法可用的条件优化子结构子问题相交性子问题空间小·Greedy方法可用的条件优化子结构Greedy选择性*可用Greedy方法时，动态规划方法可能不适用。*可用动态规划方法时，Greedy方法可能不适用。哈夫曼算法：基本思想：循环的选择具有最低频率的两个节点。生成一颗子树。直至生成一棵树；算法：Huffman(C，F)nC;QC;FORi1Ton-1DozAllocate-Node();xleft[z]Extract-MIN(Q);yright[E]Extract-MIN(Q);f(z)f(x)+f(y);insert(Q,z);ReturnExtract-MIN(Q).时间复杂度：T(n)=O(n)+O(nlogn)拟阵(Matriod)；Matroid是一个序对M=(S,I)，满足：S是一个有限非空集合;I是非空的S子集的集族，I中的子集合称为S的独立子集合;遗传性:如果BI，AB，则AI；交换性：如果AI，BI，A<B，则xB-A使得A{x}I。Matroid的性质.1设M=(S，I)是一个Matroid，AI。xA称为A的一个extension如果A{x}I。2设M=(S，I)是一个Matroid，AI（A称为M的独立子集合）。如果A没有extension，则称A为最大独立子集合。3一个Matroid的所有最大独立子集合都具有相同大小设M=(S，I)是一个Matroid。如果存在一个权函数W，使得xS,W(x)是一个正数，则称M是加权Matroid平摊分析平摊分析的基本思想在平摊分析中执行一系列数据结构所需要的时间是通过对执行的所有操作求平均值而得出的，即使单一操作具有较大的代价，通过对所有求平均后平均代价还是很小的；平摊分析的方法：聚集方法，势能方法，会计方法；聚集方法：首先证明n个操作序列在最坏情况下的总时间T(n)在最坏情况下每个操作的平均代价就是T(n)/n*聚集方法为每个操作都赋予相同的平摊代价，即使序列中存在不同类型操作时也一样。会计方法：·首先定义每个操作的平摊代价然后计算总的平摊代价·执行不同的操作需要付出不同的费用·某些操作的费用可能比它们的实际代价多或少·一个操作的平摊代价可看作为两部分：其实际代价与存款*会计方法不同于聚集方法，不同操作具有不同的平摊代价。势能方法:势能方法不是将已预付的费用作为存储在数据结构特定对象中的存款来表示，而是表示成一种“势能”，或“势”，它在需要时可释放出来以支付后面操作的代价。·势是与整个数据结构而不是其中的个别对象发生联系的。*每个操作的平摊代价为其实际代价加上由于该操作所增加的势。第七章近似算法求解NP-完全问题的两种方法：·如果问题的输入很小，可以使用指数级算法圆满地解决该问题·使用多项式算法求解问题的近似优化解点覆盖：输入输入：无向图G=（V，E）输出：，满足(1).，、或{u,v}V’(2).是满足条件(1)的最小集合APPROX-Vertex-Cover(G)1.2.3.whileDO4.任取5.E’←E’-{(u’,v’)|u’=u或v’=v}RoturnC时间复杂性T(G)=O(|E|).第八章用回溯法解题的三个步骤：针对所给的问题，定义问题的解空间确定易于搜索的解空间；以深度优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜