《算法基础》复习提纲

1 引言(ch1)

1.什么是算法及其特征

2.问题实例和问题规模

2 算法初步(ch2)

1.插入排序算法

2.算法复杂性及其度量

(1)时间复杂性和空间复杂性；  (2)最坏、最好和平均情形复杂性；

3.插入排序的最坏、最好和平均时间

4.归并排序算法及其时间复杂性

3 函数增长率(ch3)

1.渐近记号 O、Ω、θ的定义及其使用

2.标准复杂性函数及其大小关系

3.和式界的证明方法

4 递归关系式(ch4)

1.替换法

(1)猜测解→数学归纳法证明；

(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.计数排序适应的排序对象、算法和时间

3.基数排序适应的排序对象、算法和时间

4.桶排序适应的排序对象、算法和时间

9 中位数和顺序统计(ch9)

1.最大和最小值的求解方法

2.期望时间为线性的选择算法

3.最坏时间为线性的选择算法及其时间分析

10 红黑树(ch13)

1.红黑树的定义和节点结构

2.黑高概念

3.一棵 n 个内点的红黑树的高度至多是 2log(n+1)

4.左旋算法

5.插入算法、时间、至多使用 2 次旋转

6.删除算法、时间、至多使用 3 次旋转

11 数据结构的扩张(ch14)

1.动态顺序统计：

扩展红黑树，支持①选择问题(给定 Rank 求相应的元素)，②Rank 问题(求元素 x 在集合中的 Rank)

(1)节点结构的扩展；

(2)选择问题的算法；

(3) Rank 问题的算法；

(4)维护树的成本分析；

2.如何扩张一个数据结构：扩张的步骤；扩张红黑树的定理(略)；

3.区间树的扩张和查找算法(略)

12 递归与分治法(sch1)

1. 递归设计技术

2. 递归程序的非递归化

3. 算法设计

(1) 最近点对； (2) 生成全排列；

(3) 大整数乘法； (4) Stranssen 矩阵乘法；

13 动态规划(ch15)

1.方法的基本思想和基本步骤

2.动态规划和分治法求解问题的区别

3.最优性原理及其问题满足最优性原理的证明方法

4.算法设计

(1) 多段图规划； (2) 矩阵链乘法；

(3) 最大子段和； (4) 最长公共子序列；

(5) 0-1 问题求解； (6) 凸多边形最优三角剖分问题；

14 贪心算法(ch16)

1.方法的基本思想和基本步骤

2.贪心算法的正确性保证：满足贪心选择性质

3.贪心算法与动态规划的比较

4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质

5.算法设计

(1)小数背包； (2) 活动安排；

(3)找钱问题； (4) 最优装载问题；

(5)单源最短路径；

15 回溯法(sch2)

1.方法的基本思想和基本步骤

2.回溯法是一种深度遍历的搜索

3.术语: 三种搜索空间, 活结点, 死结点, 扩展结点, 开始结点, 终端结点

4.两种解空间树和相应的算法框架