第一部分 基本概念和算法导引

第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.5阶乘和二项式系数

2.4底函数和顶函数

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.1引言

5.2两个简单的例子

第5章 归纳法

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.1引言

第10章 NP完全问题

10.2P类

10.3NP类

10.4NP完全问题

10.5co-NP类

10.6NP类

10.7四种类之间的关系

10.8练习

10.9参考注释

11.2计算模型：图灵机

11.3k带图灵机和时间复杂性

11.1引言

第11章 计算复杂性引论

11.4离线图灵机和空间复杂性

11.5带压缩和线性增速

11.6复杂性类之间的关系

11.7归约

11.8完全性

11.9多项式时间层次

11.10练习

11.11参考注释

12.3决策树模型

12.2平凡下界

12.1引言

第12章 下界

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.6Dinic算法

16.7MPM算法

16.8练习

16.9参考注释

17.1引言

17.2预备知识

第17章 匹配

17.3网络流方法

17.4二分图的匈牙利树方法

17.5一般图中的最大匹配

17.6二分图的0（n2.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参考注释

参考文献