《算法设计与分析》

第一章绪言1

第二章 算法设计的步骤及算法分析的基本概念5

2-1 算法的定义5

2-2 算法设计的步骤5

2-3 算法的复杂性11

2-4 最佳算法17

2-5 拟ALGOL高级语言20

习题22

第三章基础数学23

3-1 数学归纳法——算法正确性证明23

3-2 良序原则——算法终止性证明25

3-3 整数函数27

3-4 递归方程及其求解28

3-5 算法分析示例36

习题39

第四章算法设计的基本方法41

4-1 穷举法41

4-2 登山法（贪心法）41

4-3 分枝与限界46

4-4 分治法55

4-5 动态规划68

4-6 递归80

4-7 探索法83

4-8 倒推法87

4-9 回溯法91

4-10 模拟95

习题103

第五章分类106

5-1 气泡分类法106

5-2 快速分类法109

5-3 归并分类法113

5-4 线性选择分类法117

5-5 堆分类法119

5-6 二叉合并分类法122

5-7 顺序统计126

5-8 优先队列128

习题129

第六章集合上的基本操作及其适应的数据结构131

6-1 集合上的基本操作131

6-2 二叉检索133

6-3 最优二叉检索树135

习题139

7-1 基本概念140

第七章图和网络的算法140

7-2 树的算法142

7-3 路的算法147

7-4 流的算法161

7-5 有向图的先深搜索与强连通性172

习题176

第八章几何问题与代数问题的算法179

8-1 几何问题的算法179

8-2 代数问题的算法202

习题233

9-1 简单算法236

第九章串匹配算法236

9-2 KMP算法238

9-3 BM算法241

9-4 RK算法243

9-5 Z算法245

习题246

第十章NP完全性理论及近似算法247

10-1 问题、算法、复杂性和难解性247

10-2 关于NP完全性理论的基本概念249

10-3 若干NP完全问题及其证明和分析方法259

10-4 NP难度268

10-5 近似算法270

10-6 复杂性谱系278

习题280

第十一章下界理论282

11-1 关于分类和搜索的比较树282

11-2 猜测和选手对抗赛（争论）方法287

11-3 关于代数问题下界的技术293

习题299

12-1 概率算法300

第十二章概率算法和算法的概率分析简介300

12-2 算法的概率分析305

习题307

第十三章并行算法308

13-1 并行性PRAM及其它模型308

13-2 某些PRAM算法和写冲突的处理311

13-3 合并与分类315

13-4 一个并行连通成分算法317

13-5 下界325

习题329

参考文献329