《算法基础》复习提纲

《《算法基础》复习提纲》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法基础》复习提纲1引言(chi)1.什么是算法及其特征2.问题实例和问题规模2算法初步(ch2)1.插入排序算法2.算法复杂性及其度量(1)吋间复杂性和空间复杂性；(2)最坏、最好和平均情形复杂性;3.插入排序的最坏、最好和平均时间4.归并排序算法及其时间复杂性3函数增长率(ch3)1.渐近记号O、Q、0的定义及其使用2.标准复杂性函数及其大小关系3.和式界的证明方法4递归关系式(ch4)1.替换法(1)猜测解9数学归纳法证明；(2)变量变换法；2.迭代法(1)展开法；(2)递归树法；3.主定理5概率分析(c

2、h5)1•雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性3.在线雇佣问题及其概率分析(略)《算法基础》复习提纲1引言(chi)1.什么是算法及其特征2.问题实例和问题规模2算法初步(ch2)1.插入排序算法2.算法复杂性及其度量(1)吋间复杂性和空间复杂性；(2)最坏、最好和平均情形复杂性;3.插入排序的最坏、最好和平均时间4.归并排序算法及其时间复杂性3函数增长率(ch3)1.渐近记号O、Q、0的定义及其使用2.标准复杂性函数及其大小关系3.和式界的证明方法4递归关系式(ch4)1.替换法(1)

3、猜测解9数学归纳法证明；(2)变量变换法；2.迭代法(1)展开法；(2)递归树法；3.主定理5概率分析(ch5)1•雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性3.在线雇佣问题及其概率分析(略)6堆排序(ch6)1堆的概念和存储结构2.堆的性质和种类3.堆的操作：建堆；整堆；4.堆排序算法和时间复朵性5.优先队列及其维护操作7快速排序(ch7)1.快速排序算法及其最好、最坏时间和平均时间2.随机快速排序算法及其期望时间8线性时间排序(ch8)1•基于比较的排序算法下界：□(nlogn)2.计数排

4、序适应的排序对象、算法和时间3.基数排序适应的排序对彖、算法和时间4.桶排序适应的排序对象、算法和时间9中位数和顺序统计(ch9)1.最人和最小值的求解方法2.期望时间为线性的选择算法3.最坏时间为线性的选择算法及其时间分析10红黑树(chl3)1.红黑树的定义和节点结构2.黑高概念3.—棵n个内点的红黑树的高度至多是21og(n+l)4.左旋算法5.插入算法、时间、至多使用2次旋转6.删除算法、时间、至多使用3次旋转11数据结构的扩张(chl4)1.动态顺序统计：扩展红黑树，支持①选择问题(给定Rank求相应的

5、元素)，②Rank问题(求元素x在集合中的Rank)(1)节点结构的扩展；(2)选择问题的算法；(3)Rank问题的算法；(4)维护树的成本分析；1.如何扩张一个数据结构：扩张的步骤；扩张红黑树的定理(略)；2.区间树的扩张和查找算法(略)12递归与分治法1.递归设计技术2.递归程序的非递归化3.算法设计(2)生成全排列；⑷Stranssen矩阵乘法;(1)最近点对；(1)大整数乘法；13动态规划(chl5)1.方法的基本思想和基木步骤2.动态规划和分治法求解问题的区别3.最优性原理及其问题满足最优性原理的证明方

6、法4.算法设计(1)多段图规划；(3)最大了段和；(5)0-1问题求解;(2)矩阵链乘法；(2)最长公共了序列；(6)凸多边形最优三角剖分问题;14贪心算法(chl6)1.方法的基本思想和基本步骤2.贪心算法的止确性保证：满足贪心选择性质3.贪心算法与动态规划的比较4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质5•算法设计(1)小数背包；(2)活动安排；(3)找钱问题；(4)最优装载问题；(3)单源最短路径；15回溯法1・方法的基本思想和基本步骤2.回溯法是一种深度遍历的搜索3.术语：三种搜索空间，活

7、结点，死结点，扩展结点，开始结点，终端结点4.两种解空间树和和应的算法框架5.算法设计：⑴n后问题；(3)排列生成问题；符号三角形问题;(2)0-1背包；(4)TSP问题；⑹图的m着色问题;16分支限界法1方法的基本思想和基本步骤2.与冋溯法的区别3•活结点的两种扩展方式4.0-1背包问题的搜索:FIFO队列和优先队列2.算法设计(1)0-1背包问题；⑵装载问题(略)；(1)单源最短路径问题；17数论算法(ch31)1-gcd(a,b)及其表示成a,b线性组合方法2.Euclid,sAlg.的运行时间3.线性模方

8、程的求解方法4.中国余数定理及线性同余方程组的求解18排序网络(ch27)1.比较网络2.0・1原理3.双调排序网络4.合并网络5.排序网络算法基础考试题型一、填空题(选择题)1.给定一个由11个活动组成的活动集合，各个活动的起始时间和结束时间如下表所示,则该活动集合中最大兼容活动了集的元素个数为:•11234567891011Si130535688212fi456789