算法分析与设计复习大纲

算法分析与设计复习大纲第1章绪论考点.P八\、♦1、算法的5个重要特性。答：输入、输出、有穷性、确定性、可行性2、掌握扩展递归技术和通用分治递推式的使用。扩展递归技术：T(n)=7T(n)=72T(n/2)+5n2n=vz?>1r(//)=2T(n/2)=2(2T(«/4)4-5(/f/2)2)+为亍=2(2(2T(n/8)+5(n/l)2)+5(m/z/)+5n2=2Ar(l)+2^-15^^)2+…+2X5(S+5n2地）二地）二7"5斗日=10/;2-3«〈10/二0(/)通用分支递归式:r（/zr（/z）aT(〃/Z>)+cnk71>1。(我3)«>bk7"(?z)=VO(Z«Alogz,M)«=bkO(n*)abk5、使用扩展递归技术求解下列递推关系式(1)假定的—t响=3T(n-l)=3(^r(n-2))=3f5(3T(?i-3)))==3^T(1)=4x芋T=-^=0(^):分治递归式'(")2T(m/3)4-nm>1va=2^ft=3,t=1j.a<bk根据通用递妇式的定理徐T(M)—O(m^)—O(M)第3章蛮力法1、掌握蛮力法的设计思想：蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解；关键——依次处理所有元素。2、蛮力法的代表算法及其时间复杂度：顺序查找，O(n)串匹配(BFO(n*m)，KMPO(n+m)选择排序，O(n2)冒泡排序，O(n2)生成排列对象(排列问题)，O(n!)生成子集(组合问题)，O(2n)0/1背包属于组合问题。任务分配，哈密顿回路，TSP问题属于排列问题。

3、掌握BF和KMP算法的原理，能够画出比较过程。要求给出一串字符串，能够求出对应的next数组，并能使用KMP算法进行比较匹配。4、掌握选择排序和冒泡排序算法描述和时间复杂性，要求能够写出伪代码。选择排序算法描述：选择排序开始的时候，扫描整个序列，找到整个序列的最小记录和序列中的第一记录交换，从而将最小记录放到它在有序区的最终位置上，然后再从第二个记录开始扫描序列，找到n-1个序列中的最小记录，再和第二个记录交换位置。一般地，第i趟排序从第i个记录开始扫描序列，在n-i+1个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。时间复杂性：O(n2)伪代码：voidSelectSort(intr[]tin(ti)算法3,—选择排序〃数组下标从1并始|forvoidSelectSort(intr[]tin(ti)算法3,—选择排序〃数组下标从1并始|for(i=l;研)!in(1ex=i;；f°r(j=i+lij<=n;j++)；if(r[j|<r[indexl)index=j;|if(index!=i)r[i]-吁[ind瑚;。对B个记录进行!H趟简单选择排序〃在无序区中我最小记录J偌最小记录不在最终位置则交换冒泡排序，O(n2)；算法3.7——起痼排序ivoidBubbhSort(intr[]Tintn)。数组下标从1开始|far(i=l;i<=irl;i++)//i循坏用来实现比较的趟数，共需比n-1趟“-for(j=l;]++■)"j循环用来在-趟中两两相比『并换位』iifO1jP『[j+l]}r[j]JT[j+lh。如果反序，则交换元素:}i5、算法设计题：假设在文本“ababcabccabccacbab”中查找模式"abccac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。解；BF算法…第一泡IIIIahwb*ocabccabccacb岂b+jh-ffiabKa>Vtabcabccabccacbabi-1第二范ahabIIIIabC'beeabccacb岂b+J第四趟ababKau■A>cabeeabccacbab*第五越ababi21-TTabeeabccacbab第六憩ababcabeeIIIIIIabccaII*-cbab+J由此可知，用BF算法一共要进行3+1+4+1+1+6+1+1+1+6=25次比较方能匹配出KMP算法：next[]={,0,1,1,1,1,2};由此可知，用KMP算法一共要进行3+4+6+5=18次比较方能匹配出第4章分治法了解分治法的设计思想设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。步骤：(1)划分(2)求解子问题(3)合并分治法的代表算法及时间复杂度：归并排序，快速排序，最大子段和，最近对问题，这五种问题的分治算法的时间复杂度为O(nlog2n)棋盘覆盖为O(4k)掌握归并排序和快速排序算法的算法伪代码。归并排序：:京"航4.3二五赫诵^/voidMergeSoit(intr[].int],ints,intt)iifl==t)rl[s]=r[s]；Ielse{；m=:Merger"。*〃归并排序前半个子序歹I；Mergesort3",m+Lt);〃归并排序后半个子序|Merge(rl,r,m,t);〃合并两个已排序的子序I「・算法中数组r中存储原始数据，r1在中间过程中存储排序后的数据，s指需排序数组的起始下标，t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。I彰算法4.—合并有序子序列b/voidMerge(intr[intrlf]fints,intm,intt)k{..ii=s;j=m+l;k=s;|while(i<=m&&j<=t)iif(r[i]<=rUPrl[k++]=r[i++R〃取科i]和叩]中较小者放入以1【ielserl[k++]=i*U++];；if(i<=m)while(i〈=m)!〃若第一个子序列没处理完，则进行收尾处理:11Jk++]=!*[!++]；；ekewhile(j<=t)；〃若第二个子序列没处理完，则进行收尾处理Ii'l[k++]=r[j++];快速排序朝算法4.一次划分\/intPartition(intr[],intfirst,intend)i=first;j=end;〃初始化while(i<j)while(i<j&&r[i]<=r[j])j一；〃右侧扫描if(i<j){i・[i]--r[j];〃将较小记录交换到前面i++;}while(i<j&&r[i]<=r[j])i++；〃左侧扫描if(ivj){r[j]-->r[i];〃将较大记录交换到后面}}retutni;〃i为轴值记录的最终位置土TOC\o"1-5"\h\z项疝二福希「Quicksort(intr[],intfirst,intend)；%；if(Iks心id){-phot=Partitiou(r,fiiwt,end);!|〃问题分解，piYOt是轴值在序列中的位置;QiiickSort(i\first,pivot-1);■I〃递归地对左侧子序列进行快速排序:QuickSoil1上ph顷+Lend;i;I〃递归地对右倒子序列进行快速排序I}Li对于待排序列(5,3,1,9,8,2,4,7)，画出快速排序的递归运行轨迹。按升序排列初始序列：5,3,1,9,8,2,4,7第一次划分：4,3,1,2,5,8,9,7第二次划分：2,3,1,4,5,8,9,7第三次划分：1,2,3,4,5,8,9,7第四次划分：1,2,3,4,5,7,8,9排序完成，红色字体为每次划分的轴值第5章减治法了解减治法的设计思想设计思想：原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。掌握使用减治法的代表问题及时间复杂度：折半查找，二叉树查找，堆排序，选择问题，淘汰赛冠军问题，假币问题；以上问题的时间复杂度，如果减治是每次减小为原来规模的1/2,则时间复杂度一般为O(log2n)掌握折半查找的算法伪代码描述及具体例子的查找过程，会根据折半查找的过程创建判定树。;段算法El——折半查找；LIqw-1：high=n：//设置初始查找区间:2•测试查找区间[low,high]是否存在，若不存在，则查找失败:否则；3,取中间点mid-(low-i-high)12;比较k与r[mid],有以卜三种情况:；3.1若k<r[ini(l],则high=niidT；查找在左半区进行,转、;3,2若k>r[niiil],则lo^-inid+1：母找在右半区进行丁转2：侦)按6390=5龊70,4240,45,83,67(b)按55,42,10,70,63,58,83,67.90^的顺序构造的二又排序树的顺序构造的二叉排序树掌握堆排序算法中的两种调整堆和新建堆的方法：筛选法堆调整问题：将一个无序序列调整为堆(1)筛选法调整堆关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？(时28与玷交换(b)28与32交换(c)将2瞬到叶子第6章动态规划法了解动态规划法的设计思想设计思想：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。步骤：将原始问题分解为相互重叠的子问题，确定动态规划函数；求解子问题，填表；根据表，自底向上计算出原问题的解。掌握可以用动态规划法解决的问题及时间复杂度：TSP，多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题；多段图的最短路径问题：O(n+m)0/1背包问题：O(nxC)掌握多段图的最短路径问题的动态规划算法y算法丘2——多段图的最短路径/1-初始也数组cost[n]初始化为最大值，数组网比回初始化为T；\2.for(i=ii-2;i>=0;i，-)；2.1对顶点i的每一个邻接点j,根据式6.7计算匚0河正!2.2根据式6.8计算pmh[i];；5・输出最短5&径长^cGstfO];，4•输出最短路径经过的顶点二；4J1=0i4.2循环直到path[i]=n-l-421输th|)«itli|ij；).-■.■.■>_.^,,2.—.——.——.—.I—.—I.■._*工、■'—11—••动态规划函数为：cost[i]中存储顶点动态规划函数为：cost[i]中存储顶点i到终点的最短路径长度cost[i]=min{C[i][j]+cost[j]}（i<j且顶点j是顶点i的邻接点）path[i]=使C[i][j]+cost[j撮小的j先构造cost数组和path数组一个多段图0!116:172：34tJi15：13：95\6aaaJa9：87；8；7：3_；354\5:8I8伦：Q\9\掌握0/1背包问题的动态规划算法及具体实现尹6：3二0万普菰嗣'mtKnapSackfuitn.mtw[].mt\[]jifor(1=0;i<=n;i++)//初始化W。列iVri][0]=0;；for(j=0;|<=C:J++)〃初始化答。行IV[0][]]=0;ifor(i=l;K=n;i-^)〃计算第I行’进行第秋送代|foT(j=l；J<=C；|H)iif0<w[l])算法6.3―/I背包问题rv[i][j]=V[Fl]O)；ielse，V[i][j]=mg(V[i・l][j],V[iT][jf[i]]+v[i]);|j-C;〃求装入背包的物品-for(i=n;i>0;i——)iehex[i]=O;-returnV[n][C]：〃返回背包取得的最大价值例题：用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为(3,2,1,4,5)，物品的价值分别为(25,20，15,40，50)，背包容量为6。写出求解过程。0/1背包问题的动态规划函数为:W)一叩-1J)J<叫max{7(z-l?/)?叩一拔-雄)+号V(i,j)表示把前i个物品放入容量为j的背包中的最大价值和。W)一填表过程：43^4^50山W0LOp25p25*22.W=2,v=20^—20p25p2d43/W=l,v=15^15-15p35-40#4W=4,v=40^Op15—15p35^40.b5村W=5,v=50.15.15p40,5放入背包中的物品的求解过程：则65表示把5个物品放入容量为6的背包中的最大价值和。i=5,j=6;v[5][6]>v[4][6],x[5]=1,j=6-w[5]=1i=4,j=1；v[4][1]=v[3][1],x[4]=0i=3,j=1；v[3][1]>v[2][1],x[3]=1,j=1-w[3]=0i=2,j=0；v[2][1]=v[1][0],x[2]=0i=1,j=0；v[1][0]=v[0][0],x[1]=0结果是把第3个和第5个放入了背包第7章贪心法了解贪心法的设计思想贪心法在解决问题的策略上目光短浅，只根据当前巳有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法的关键在于决定贪心策略。掌握可以用贪心法解决的问题：TSP问题中的两种解决方法：最近领点策略，最短链接策略最小生成树问题的两种算法：最近顶点策略（Prim算法），最短边策略（Kruskal算法）背包问题，活动安排问题，多机调度问题。

掌握最小生成树的两种贪心算法：prim算法和kruskal算法（P145-148），给出具体的例子，能够用两种方法画出树的生成过程。I印)连通网，掌握最小生成树的两种贪心算法：prim算法和kruskal算法（P145-148），给出具体的例子，能够用两种方法画出树的生成过程。(c)U={A^.C)C0St={(4,引26](c)U={A^.C)C0St={(4,引26](d)U=(4凡UD}(e)U={47,C\dE}(f)g{A.FCD,匹5>Eim算法构造最小生成树的过程示意Kiu^l方法构造最小生成树的过程掌握背包问题的贪心算法(P148-151)，给出一个具体的例子，能够写出解决问题的过程。习题7-2问题：求如下背包问题的最优解：有7个物品，价值P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量W=15.解决方法：先对物品物品重量的单位重量价值按照降序排列物品价值物品价值/物品重量16621054184.55153133351.67771依次把物品放入容量为15的背包，直到背包被装满1+2+4+5+1=13,前5个物品装入背包，还剩下容量为2,第6个物品只能装入2/3所以总价值为：6+10+18+15+3+5*2/3=55.3333第8章回溯法了解回溯法的设计思想设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。步骤：确定解向量和分量的取值范围，构造解空间树；确定剪枝函数；对解空间树按深度优先搜索，搜索过程中剪枝；从所有的可能解中确定最优解。了解可以用回溯法解决的问题：属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问题，