发布时间 : 星期五 文章大学算法分析与设计复习总结更新完毕开始阅读257cde0a172ded630a1cb698
大学算法分析与设计复习总结
第1章 绪论 考点：
1、算法的5个重要特性。（P3）
答：输入、输出、有穷性、确定性、可行性
2、 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答：
1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码 优点：表达能力强，抽象性强，容易理解
3、了解非递归算法的时间复杂性分析。(P13)
要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是：
（1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。
（3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。
[例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) {
min=a[0];
for (i=1; i if (a[i] 基本语句： a[i] 4、掌握扩展递归技术和通用分治递推式的使用。（P15） 扩展递归技术： 通用分支递归式： 使用扩展递归技术求解下列递推关系式 （1） （2） 第2章 分治法 了解分治法的设计思想 设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 步骤：（1）划分（2）求解子问题（3）合并 分治法的代表算法及时间复杂度： 归并排序，快速排序，最大子段和，最近对问题，凸包问题，这五种问题的分治算法的时间复杂度为O(nlog2n) 棋盘覆盖，循环赛日程安排为O(4) 掌握归并排序和快速排序算法的算法伪代码。（P78-83） k 归并排序： 算法中数组r中存储原始数据，r1在中间过程中存储排序后的数据，s指需排序数组的起始下标，t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。