大学算法分析与设计复习总结为了拿大学的那悲剧的学分，好好弄懂以下所有知识点吧。
把老师的复习的提纲，特意汇总了所有考点，方便童鞋们复习。
不喜勿喷！！！这本书是《算法设计与分析》王红梅编著一共有以下12章，我们学了1、3、4、5、6、7、8、9分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法第1章绪论考点：1、算法的5个重要特性。
（P3）答：输入、输出、有穷性、确定性、可行性2、描述算法的四种方法分别是什么，有什么优缺点。
（P4）答：1. 自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。
2. 流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。
3. 程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。
伪代码优点：表达能力强，抽象性强，容易理解3、了解非递归算法的时间复杂性分析。
(P13)要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。
非递归算法分析的一般步骤是：（1）决定用哪个（或哪些）参数作为算法问题规模的度量。
（2）找出算法的基本语句。
（3）检查基本语句的执行次数是否只依赖问题规模。
（4）建立基本语句执行次数的求和表达式。
（5）用渐进符号表示这个求和表达式。
[例1.4]：求数组最小值算法int ArrayMin(int a[ ], int n){min=a[0];for (i=1; i<n; i++)if (a[i]<min) min=a[i];return min;}问题规模：n基本语句：a[i]<minT(n)= n-1=O(n)4、掌握扩展递归技术和通用分治递推式的使用。
（P15）扩展递归技术：通用分支递归式：5、习题1-4，习题1-7设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求给出伪代码描述，并用一组例子进行跟踪验证，写出验证过程。
（1）伪代码1. 令最小距离min等于数组头两个元素R[0]和R[1]的差的绝对值；2. 从i=0循环至i<n-1，对于每个R[i]2.1 分别求其与j=i+1至j<n的数的差的绝对值；2.2 如果此值小于最小距离，则令新的最小距离为此值；3. 输出最小距离。
（2）用实例进行跟踪验证R[6]={10,5,11,16,30,14},n=6;Min=|10-5|=5;i=0,j=1, |R[i]-R[j]|=|10-5|=5;j=2,|R[i]-R[j]|=|10-11|=1<min;min=1;j=3, |R[i]-R[j]|=|10-16|=6;j=4, |R[i]-R[j]|=|10-30|=20;j=5, |R[i]-R[j]|=|10-14|=4;i=1,j=2, |R[i]-R[j]|=|5-11|=6;j=3, |R[i]-R[j]|=|5-16|=11;j=4, |R[i]-R[j]|=|5-30|=15;j=5, |R[i]-R[j]|=|5-14|=9;i=2,j=3, |R[i]-R[j]|=|11-16|=5;j=4, |R[i]-R[j]|=|11-30|=19;j=5, |R[i]-R[j]|=|11-14|=3;i=3,j=4, |R[i]-R[j]|=|16-30|=14;j=5, |R[i]-R[j]|=|16-14|=2;i=4,j=5, |R[i]-R[j]|=|30-14|=16;最后输出min=17、使用扩展递归技术求解下列递推关系式（1）（2）第3章蛮力法1、掌握蛮力法的设计思想：蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键——依次处理所有元素。
2、蛮力法的代表算法及其时间复杂度：顺序查找，O(n)串匹配（BF O(n*m)，KMP O(n+m)，BM O(n*m)）选择排序，O(n2)冒泡排序，O(n2)生成排列对象（排列问题），O(n!)生成子集（组合问题），O(2n)0/1背包属于组合问题。
任务分配，哈密顿回路，TSP问题属于排列问题。
最近对问题O(n2)，凸包问题O(n3)3、掌握BF和KMP算法的原理，能够画出比较过程。
P71习题3的4。
要求给出一串字符串，能够求出对应的next数组，并能使用KMP算法进行比较匹配。
4、掌握选择排序和冒泡排序算法描述和时间复杂性，要求能够写出伪代码。
（P56-58）选择排序算法描述：选择排序开始的时候，扫描整个序列，找到整个序列的最小记录和序列中的第一记录交换，从而将最小记录放到它在有序区的最终位置上，然后再从第二个记录开始扫描序列，找到n-1个序列中的最小记录，再和第二个记录交换位置。
一般地，第i趟排序从第i 个记录开始扫描序列，在n-i+1个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。
时间复杂性：O(n2)伪代码：冒泡排序算法描述：冒泡排序开始的时候扫描整个序列，在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就能被“沉到”了序列的最后一个位置，第二趟扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1趟扫描后，整个序列就排好序了。
冒泡排序，O(n2)5、算法设计题：习题3-3，3-6，3-8，3-11，3-133-3 对于KMP算法中求next数组问题，设计一个蛮力算法，并分析其时间性能。
[cpp]view plaincopyprint?1.voidGetNext(char T[ ], int next[ ])2.{3. next[1]=0;4. next[2]=1;5. j=T[0],k=0;6.for(;j>2;j--){7.for(n=j-2;n>=1;n--){//n为要比较的前缀的最后一个字符的下标8. m=j-n;//m为要比较的后缀的第一个字符的下标9.for(i=1;i<=n;i++)10. {11.if(T[i]!=T[m+i-1])break;12. }13.if(i==n+1){next[j]=n+1;break;}14. }15.if(n==0)next[j]=1;16. }17.}3-4 假设在文本“ababcabccabccacbab”中查找模式“abccac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。
由此可知，用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次比较方能匹配出参考代码如下：排列最终存储在长度为n的阶乘，元素类型为指针的数组中，数组指向一个排列，具体的排列数据存储在数组中。
[cpp]view plaincopyprint?1.int fabs(int n)2.{3.int r=1;4.for(inti=n;i>1;i--)5. r=r*i;6.return r;7.8.}9.10.//排列存储在数组中11.void getArrangement(int**&s,int n)12.{13.int * p,*q;14.int * *s1;15.int i,j,k,l,m,o;16. s=new int *[1];17. s[0]=newint[1];18. s[0][0]=1;19.for(i=2;i<=n;i++)20. {21. j=0;22. o=0;23. m=fabs(i-1);24. s1=newint *[fabs(i)];25.while(o<m)26. {27. q=p=s[o];28.for(k=i-1;k>=0;k--)29. {30. s1[j]=newint[i];31.for(l=0;l<i;l++)32. {33.if(l==k){s1[j][l]=i;}34.else{35. s1[j][l]=*p;36. p++;}37. }38. j++;39. p=q;40. }41. o++;42.delete[] q;43. }44.delete[]s;45. s=s1;46. }47.}3-8对于一个平面上n个点的集合S，设计蛮力算法求集合S的凸包的一个极点。
点集合中最左边或者最右边的点一定是凸包的一个极点，则求凸包的极点的问题转化为求点的x坐标最大或最小的点[cpp]view plaincopyprint?1.int getPole(int x[],int y[],int n)2.{3.int r=0;4.for(inti=0;i<n;i++)5. {6.if(x[i]>x[r])r=i;7. }8.return r;9.}<span style="font-weight: bold; "> </span>3-11 设计算法生成在n个元素中包含k个元素的所有组合对象。
两种思路：1、生成所有的组合，在组合中找元素个数为k个的组合。
伪代码：1．初始化一个长度为n的比特串s=00…0并将对应的子集输出；2．for(i=1; i<2n; i++) //注意不能书写成i<=2n2.1 s++；2.2 判断s中1的个数，若为k，则将s对应的子集输出；2、使用k层嵌套循环生成元素个数为k个的组合。
设k=3；n个元素存储在数组a[]中；伪代码：for (i=1; i<n-2; i++)for(j=i+1; i<n-1; i++)for(k=j+1; i<n; i++)输出a[i]a[j]a[k]构成的组合。
3-13美国有个连锁店叫7-11这个连锁店以前是每天7点开门，晚上11点关门不过现在是全天24小时营业。
有一天，有个人来到这个连锁店，买了4件商品营业员拿起计算器敲了一下，说：总共是$7.11顾客开玩笑说：所以你们商店就叫7-11？营业员没有理她，说：当然不是，我是把它们的价格相乘之后得到的。
顾客说：相乘？你应该把他相加才对。
营业员说，我弄错了。
接着又算了一遍，结果让两个人吃惊的是：计算结果也是$7.11请问，这4件商品的价格是多少？参考代码：[cpp]view plaincopyprint?1.#include<iostream.h>2.#include <stdio.h>3.int main()4.{5.long i,j,k,m;6.7.for (i=1; i <=711/4 ; i++)8.{9.for (j=i; j <=711/3 ; j++)10.{11.for (k=j; k <=711/2 ; k++)12.{13.m=711-i-j-k;14.if (i*j*k*m==711*1000000)15.{16.cout<<i<<endl<<j<<endl<<k<<endl<<m<<endl;17. }18.}19.}20.}21.return 0;22.}输出结果为：价格分别是1.2 1.25 1.5 3.16第4章分治法了解分治法的设计思想设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。