大学算法分析与设计复习总结.docx

大学算法分析与设计复习总结

为了拿大学的那悲剧的学分，好好弄懂以下所有知识点吧。把老师的复习的提纲，特意汇总了所有考点，方便童鞋们复习。不喜勿喷！！！这本书是《算法设计与分析》王红梅编著

一共有以下12章，我们学了1、3、4、5、6、7、8、9

分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法

第1章绪论考点：

1、 算法的5个重要特性。（P3）

答：输入、输出、有穷性、确定性、可行性

2、 描述算法的四种方法分别是什么，有什么优缺点。（P4）答：

自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。

流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。

程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。

伪代码 优点：表达能力强，抽象性强，容易理解

3、 了解非递归算法的时间复杂性分析。(P13)

要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。

非递归算法分析的一般步骤是：

决定用哪个（或哪些）参数作为算法问题规模的度量。

找出算法的基本语句。

检查基本语句的执行次数是否只依赖问题规模。

通用分支递归式：（

通用分支递归式：

（4）

（5）

建立基本语句执行次数的求和表达式。

用渐进符号表示这个求和表达式。

[例1.4]：求数组最小值算法

intArrayMin(inta[],intn)

{

min=a[0];

for(i=1;in;i++)

if(a[i]min)min=a[i];returnmin;

}

问题规模：n

基本语句：a[i]minT(n)=n-1=O(n)

4、 掌握扩展递归技术和通用分治递推式的使用。（P15）

扩展递归技术：

5、 习题1-4，习题1-7

设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求给出伪代码描述，并用一组例子进行跟踪验证，写出验证过程。

伪代码

令最小距离min等于数组头两个元素R[0]和R[1]的差的绝对值；

从i=0循环至in-1，对于每个R[i]

分别求其与j=i+1至jn的数的差的绝对值；

如果此值小于最小距离，则令新的最小距离为此值；

输出最小距离。

用实例进行跟踪验证

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|=1min;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;

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=1

7、使用扩展递归技术求解下列递推关系式

7、使用扩展递归技术求解下列递推关系式

（1）

（2）

第

第3章蛮力法

1、 掌握蛮力法的设计思想：

蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;

关键——依次处理所有元素。

2、 蛮力法的代表算法及其时间复杂度：顺序查找，O(n)

串匹配（BFO(n*m)，KMPO(n+m)，BMO(n*m)）选择排序，O(n2)

冒泡排序，O(n2)

生成排列对象（排列问题），O(n!)生成子集（组合问题），O(2n)

0/1背包属于组合问题。

任务分配，哈密顿回路，TSP问题属于排列问题。最近对问题O(n2)，凸包问题O(n3)

3、掌握BF和KMP算法的原理，能够画出比较过程。P71习题3的4。要求给出一串字符串，能够求出对应的next数组，