《算法设计与分析》复习提纲.doc

《《算法设计与分析》复习提纲.doc》由会员分享，可在线阅读，更多相关《《算法设计与分析》复习提纲.doc（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法设计与分析复习提纲 2021.1.41 引言(ch1)1.什么是算法及其特征2.问题实例和问题规模2 算法初步(ch2)1.插入排序算法2.算法复杂性及其度量 (1)时间复杂性和空间复杂性； (2)最坏、最好和平均情形复杂性；3.插入排序的最坏、最好和平均时间4.归并排序算法及其时间复杂性 3函数增长率(ch3)1.渐近记号O、的定义及其使用2.标准复杂性函数及其大小关系3.和式界的证明方法4 递归关系式(ch4，Sch1)1.替换法(1)猜测解数学归纳法证明；(2)变量变换法；2.迭代法(1)展开法；(2)递归树法；3.主定理4.补充1：递归与分治法(sch1) - 递归设计技术 - 递

2、归程序的非递归化 - 算法设计 (1)Fibonacci数； (2)生成全排列；(3)二分查找； (4)大整数乘法；(5)Stranssen矩阵乘法； (6)导线和开关(略)；5 堆排序(ch6)1堆的概念和存储结构2.堆的性质和种类3.堆的操作：建堆；整堆；4.堆排序算法和时间复杂性5.优先队列及其维护操作6 快速排序(ch7)1.快速排序算法及其最好、最坏时间和平均时间2.随机快速排序算法及其期望时间3.Partition算法7 线性时间排序(ch8)1.基于比较的排序算法下界：(nlogn)2.计数排序适应的排序对象、算法和时间3.基数排序适应的排序对象、算法和时间4.桶排序适应的排序对

3、象、算法和时间8 中位数和顺序统计(ch9)1.最大和最小值的求解方法2.期望时间为线性的选择算法3.最坏时间为线性的选择算法及其时间分析9 红黑树(ch13)1.红黑树的定义和节点结构2.黑高概念3.一棵n个内点的红黑树的高度至多是2log(n+1)4.左旋算法5.插入算法的时间、至多使用2次旋转6.删除算法的时间、至多使用3次旋转10 数据结构的扩张(ch14)1.动态顺序统计：扩展红黑树，支持选择问题(给定Rank求相应的元素)，Rank问题(求元素x在集合中的Rank)(1)节点结构的扩展；(2)选择问题的算法；(3)Rank问题的算法；(4)维护树的成本分析；2.如何扩张一个数据结构

4、：扩张的步骤；扩张红黑树的定理(略)；3.区间树的扩张和查找算法11 动态规划(ch15)1.方法的基本思想和基本步骤2.动态规划和分治法求解问题的区别3.最优性原理及其问题满足最优性原理的证明方法4.算法设计 (1)多段图规划； (2)矩阵链乘法； (3)最大子段和； (4)最长公共子序列；12 贪心算法(ch16)1.方法的基本思想和基本步骤2.贪心算法的正确性保证：满足贪心选择性质3.贪心算法与动态规划的比较4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质5.算法设计 (1)小数背包； (2)活动安排； (3)找钱问题；13 回溯法(sch2)1.方法的基本思想和基本步骤2.回

5、溯法是一种深度遍历的搜索3.术语: 三种搜索空间, 活结点, 死结点, 扩展结点, 开始结点, 终端结点4.两种解空间树和相应的算法框架 5.算法设计 (1)图和树的遍历； (2)n后问题； (3)0-1背包； (4)排列生成问题； (5)TSP问题；14 平摊分析(ch17)1.平摊分析方法的作用和三种平摊分析方法各自特点2.聚集分析法及应用3.记账分析法及应用4.势能法及应用15 二项堆(ch19 in textbook version 2)1.为什么需要二项堆？二项堆和二叉堆上的几个基本操作时间复杂性2.二项堆定义和存储结构3.二项堆上合并操作及过程4.二项堆应用（尤其是在哪些图论算法上

6、有应用）16 不相交集数据结构(ch21)1.不相交数据集概念2.两种实现方式：链表表示和森林表示3.两种表示具体实现和其上操作的时间复杂性4.不相交集数据结构应用（尤其是在哪些图论算法上有应用）17 图论算法(ch22-ch25)1. BFS和DFS算法- 白色、灰色和黑色结点概念和作用- 计算过程及其时间复杂度2.最小生成树- 安全边概念和一般算法（Generic algorithm）- Kruskal算法和Prim算法的计算过程和计算复杂性- 两种贪心算法的贪心策略和贪心选择性质3.单源最短路径（略） - 单源最短路径(s, v)和短路径上界dv概念 - 边松弛技术及其一些性质 - 三种

7、问题算法的计算过程及其时间复杂度：Bellman-Ford算法、DAG算法和Dijkstra算法4. 所有点对最短路径（略） - 为什么能转换为矩阵乘法？ - 基于矩阵乘法的较慢和快速算法的时间复杂度 - Floyd-Warshall Algorithm的思路和时间复杂度 - Johnson Algorithm适应的问题及其时间复杂度（略）18 数论算法(ch31)1.gcd(a, b)及其表示成a, b线性组合方法2.Euclids Alg.的运行时间3.线性模方程的求解方法4.中国余数定理及其相应线性同余方程组的求解5.RSA算法过程及正确性基础6.简单素数测试算法和伪素数测试算法7.MR算法的改进措施和算法复杂性19 串匹配(ch32)1.朴素的串匹配算法及其时间复杂度2. Rabin-Karp串匹配算法及其时间复杂度3.有限自动机串匹配算法及其及其时间复杂度4.KMP串匹配算法及其时间复杂度20 模型和NPC(ch34)1.算法的严格定义2.几种计算模型的语言识别能力3.两类图灵机模型4.P问题、NP问题和NP完全问题的定义及P归约