《算法设计与分析》复习提纲.pdf
算法设计与分析复习提纲 2021.1.4 1 引言(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)-递归设计技术 -递归程序的非递归化 -算法设计 (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.桶排序适应的排序对象、算法和时间 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.如何扩张一个数据结构：扩张的步骤；扩张红黑树的定理(略)；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.回溯法是一种深度遍历的搜索 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.二项堆应用（尤其是在哪些图论算法上有应用）16 不相交集数据结构(ch21)1.不相交数据集概念 2.两种实现方式：链表表示和森林表示 3.两种表示具体实现和其上操作的时间复杂性 4.不相交集数据结构应用（尤其是在哪些图论算法上有应用）17 图论算法(ch22-ch25)1.BFS 和 DFS 算法-白色、灰色和黑色结点概念和作用-计算过程及其时间复杂度 2.最小生成树-安全边概念和一般算法（Generic algorithm）-Kruskal 算法和 Prim 算法的计算过程和计算复杂性-两种贪心算法的贪心策略和贪心选择性质 3.单源最短路径（略）-单源最短路径(s,v)和短路径上界 dv概念 -边松弛技术及其一些性质 -三种问题算法的计算过程及其时间复杂度：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 归约
