算法分析与设计复习大纲（全）.docx

算法分析与设计复习大纲（全）.docx、、•1、 算法的5个重要特性。答:输入、输出、有穷性、确定性、可行性2、 学握扩展递归技术和通用分治递推式的使用。扩展递归技术:72T(n/2)+5n2r(n)=2r(/z/2)+5zz2=2(2T(n/4)+5(///2)2)+5z?=2(2(27X〃/8)+5("/4)2)+5(〃/2)2)+5,/\2-7.=7/?+5/<(2 =10n:-3n<10/?2=0(n:)12丿 L=2kT(l)4-2^_156^1)2+・・・+2X5(#)2+5/i2Al丁(町二7”+5》i=0通川分支递归式:IckyaTQt/b)+cnka>bka=bkClvbk0(/3)=vO(wAlog„”)0(/)5、使用扩展递归技术求解下列递推关系式(1)假定"=kr(n)=3T(n-l)=X3T(«-2))=3(3(3T(n-3)))=■■■=3MT(l)=4x3t"1=-xr=0(^)3(2)使用通用分治递归式..[ 1 M=1f(町=q[2T(w/3)+nn>Iva=2^b=3^t=1a<bk根据通用递归式的定理 得二T(M)=O(>1*)=O(M)第3章蛮力法1>掌握蛮力法的设计思想:蛮力法依赖的基本技术——扫描技术,即釆用一定的策略将待求解问题的所有元素依次处理一次,从而找岀问题的解;关键一依次处理所冇元素。2、蛮力法的代表算法及H时间复杂度:顺序查找,0(n)串匹配(BFO(nFV,KMPO(n+m)选择排序,O(n2)冒泡排序,0(n2)生成排列对象(排列问题),O(n!)生成子集(组合问题),0(2T)0/1背包属于组合问题。任务分配,哈密顿回路,TSP问题属于排列问题。3、 掌握BF和KMP算法的原理,能够画出比较过程。要求给出一串字符串,能够求出对应的next数组,并能使用KMP算法进行比较匹配。4、 学握选择排序和冒泡排序算法描述和时间复杂性,要求能够写出伪代码。选择排序算法描述:选择排序开始的时候,扫描整个序列,找到整个序列的最小记录和序列中的第一记录交换,从而将最小记录放到它在冇序区的最终位置上,然后再从第二个记录开始扫描序列,找到个序列中的最小记录,再和笫二个记录交换位置。一般地,第i趟排序从第i个记录开始扫描序列,在n・i+1个记录屮找到关键码最小的记录,并和第i个记录交换作为冇序序列的第i个记录。时间复朵性:O(n2)伪代码:車, 'zvoidSelectSort(intr[|,intn)r{! for(i=l;i<=n-l;i++)1 {! in(lex=i;; for(j=i+l;j<=n;j++)i if(r|j|<r[index])in(lex=j;; if(index!=i)r[i]<-^r[index];一选择排序〃数组下标从1开始〃对n个记录进行nT趟简单选择排序〃在无序区中找最小记录〃若最小记录不在最终位置则交换冒泡排序算法描述:冒泡排序开始的时候扫描整个序列,在扫描过程中两两比较相邻记录,如果反序则交换,最终,最人记录就能被“沉到”了序列的最后一个位置,第二趟扫描将第二大记录“沉到”了倒数第二个位置,重复上述操作,直到趟扫描后,整个序列就排好序了。冒泡排序,O(n2)〃—起泡排序for(i=l;i<=n-l;i++)for(j=l;j<=n-i;j++)if(r[j]»[j+l])r[j]-Tjj+lh•voidBubbleSort(intr[],intn)〃i循坏用来实现比较的趟数,共需比nJ趟。〃j循环用来在一趟中两两相比,并换位。〃如果反序,则交换元素5、算法设讣题:假设在文本"acbab"ac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。BF算法’i第一趙abaII II %a b •.••.••.••.••.•••.••.••.••.•••••.A第四趙第五趙第六趙II II IIwa b cVSAAAAAAA Wcc•.••.••.••.••.•••.••.••.••.•••••.AII'aSAAAAAAA/^ 、-X"\AAAAAa*v*v*v*v*v*-••V*V*V*V*V*V*VXA/«/«/'■WWv*VWWv**a由此可知,用BF算法一共要进行3+1+4+1+1+6+1+1+1+6=25次比较方能匹配出KMP算法:next[]={,0,1,1,1,1,2};WvWWSAAA^*IkIIIIUabVSAAAAAA/^第三趙IIR1IIIIIIK第四趙IHIIIIIIIIaDWWS/WSA由此可知,用KMP算法一共要进行3+4+6+5=18次比较方能匹配出第4章分治法了解分治法的设计思想设计思想:将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如