算法设计与分析 - 总结0

这本书是《算法设计与分析》 王红梅 编著

一共有以下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

return min; }

问题规模：n 基本语句： a[i]

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

通用分支递归式：

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

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

（1）伪代码

1. 令最小距离min等于数组头两个元素R[0]和R[1]的差的绝对值； 2. 从i=0循环至i

2.1 分别求其与j=i+1至j

i=0,j=1, |R[i]-R[j]|=|10-5|=5;

j=2,|R[i]-R[j]|=|10-11|=1

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

（2）

第3章 蛮力法

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

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

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

串匹配（BF O(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数组，并能使用KMP算法进行比较匹配。

4、 掌握选择排序和冒泡排序算法描述和时间复杂性，要求能够写出伪代码。（P56-58） 选择排序

算法描述：选择排序开始的时候，扫描整个序列，找到整个序列的最小记录和序列中的第一记录交换，从而将最小记录放到它在有序区的最终位置上，然后再从第二个记录开始扫描序列，找到n-1个序列中的最小记录，再和第二个记录交换位置。一般地，第i趟排序从第i