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

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

为了拿大学的那悲剧的学分，好好弄懂以下所有知识点吧。把老师的复习的提纲，特意汇总了所有考点，方便童鞋们复习。不喜勿喷！！！

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

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

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

考点：

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