算法设计技巧与分析

**部分 基本概念和算法导引
第1章 算法分析基本概念
1.1引言
1.2历史背景
1.3二分搜索
1.4合并两个已排序的表
1.5选择排序
1.6插入排序
1.7自底向上合并排序
1.8时间复杂性
1.9空间复杂性
1.10*优算法
1.11如何估计算法运行时间
1.12*坏情况和平均情况的分析**部分 基本概念和算法导引
第1章 算法分析基本概念
1.1引言
1.2历史背景
1.3二分搜索
1.4合并两个已排序的表
1.5选择排序
1.6插入排序
1.7自底向上合并排序
1.8时间复杂性
1.9空间复杂性
1.10*优算法
1.11如何估计算法运行时间
1.12*坏情况和平均情况的分析
1.13平摊分析
1.14输入大小和问题实例
1.15练习
1.16参考注释

第2章 数学预备知识
2.1集合、关系和函数
2.2证明方法
2.3对数
2.4底函数和顶函数
2.5阶乘和二项式系数
2.6鸽巢原理
2.7和式
2.8递推关系
2.9练习

第3章 数据结构
3.1引言
3.2链表
3.3图
3.4树
3.5根树
3.6二叉树
3.7练习
3.8参考注释

第4章 堆和不相交集数据结构
4.1引言
4.2堆
4.3不相交集数据结构
4.4练习
4.5参考注释

第二部分 基于递归的技术

第5章 归纳法
5.1引言
5.2两个简单的例子
5.3基数排序
5.4整数幂
5.5多项式求值（Horner规则）
5.6生成排列
5.7寻找多数元素
5.8练习
5.9参考注释

第6章 分治
6.1引言
6.2二分搜索
6.3合并排序
6.4分治范式
6.5寻找中项和第k小元素
6.6快速排序
6.7大整数乘法
6.8矩阵乘法
6.9*近点对问题
6.10练习
6.11参考注释

第7章 动态规划
7.1引言
7.2*长公共子序列问题
7.3矩阵链相乘
7.4动态规划范式
7.5所有点对的*短路径问题
7.6背包问题
7.7练习
7.8参考注释

第三部分*先割技术

第8章 贪心算法
8.1引言
8.2*短路径问题
8.3*小耗费生成树（Kruskal算法）
8.4*小耗费生成树(Prim算法)
8.5文件压缩
8.6练习
8.7参考注释

第9章 图的遍历
9.1引言
9.2深度优先搜索
9.3深度优先搜索的应用
9.4广度优先搜索
9.5广度优先搜索的应用
9.6练习
9.7参考注释第四部分问题的复杂性

第10章 NP完全问题
10.1引言
10.2P类
10.3NP类
10.4NP完全问题
10.5coNP类
10.6NPI类
10.7四种类之间的关系
10.8练习
10.9参考注释

第11章 计算复杂性引论
11.1引言
11.2计算模型：图灵机
11.3k带图灵机和时间复杂性
11.4离线图灵机和空间复杂性
11.5带压缩和线性增速
11.6复杂性类之间的关系
11.7归约
11.8完全性
11.9多项式时间层次
11.10练习
11.11参考注释

第12章 下界
12.1引言
12.2平凡下界
12.3决策树模型
12.4代数决策树模型
12.5线性时间归约
12.6练习
12.7参考注释第五部分克服困难性

第13章 回溯法
13.1引言
13.23着色问题
13.38皇后问题
13.4一般回溯方法
13.5分支限界法
13.6练习
13.7参考注释

第14章 随机算法
14.1引言
14.2Las Vegas和Monte Carlo算法
14.3随机化快速排序
14.4随机化的选择算法
14.5测试串的相等性
14.6模式匹配
14.7随机取样
14.8素数性测试
14.9练习
14.10参考注释

第15章 近似算法
15.1引言
15.2基本定义
15.3差界
15.4相对性能界
15.5多项式近似方案
15.6完全多项式近似方案
15.7练习
15.8参考注释第六部分域指定问题的迭代改进

第16章 网络流
16.1引言
16.2预备知识
16.3FordFulkerson方法
16.4*大容量增值
16.5*短路径增值
16.6 Dinic算法
16.7 MPM算法
16.8练习
16.9参考注释

第17章 匹配
17.1引言
17.2预备知识
17.3网络流方法
17.4二分图的匈牙利树方法
17.5一般图中的*大匹配
17.6二分图的On2.5算法
17.7练习
17.8参考注释第七部分计算几何技术

第18 章几何扫描
18.1引言
18.2几何预备知识
18.3计算线段的交点
18.4凸包问题
18.5计算点集的直径
18.6练习
18.7参考注释

第19章 Voronoi图解
19.1引言
19.2*近点Voronoi图解
19.3Voronoi图解的应用
19.4*远点Voronoi图解
19.5*远点Voronoi图解的应用
19.6练习
19.7参考注释参考文献信息