第1章 算法引论 1
1.1 算法 1
1.2 算法描述 2
1.2.1 算法描述约定 2
1.2.2 一个简单问题的求解过程 5
1.3 算法分析基础 6
1.3.1 算法分析的评估体系 6
1.3.2 算法的时间复杂度 6
1.3.3 算法的空间复杂度 9
1.3.4 NP-完全问题 9
1.4 基本数据结构 10
1.4.1 栈和队列 10
1.4.2 树 14
1.4.3 图 19
1.5 迭代法 22
1.5.1 递推法 22
1.5.2 倒推法 22
1.5.3 迭代法解方程 23
1.6 递归和消除递归 25
1.6.1 递归 25
1.6.2 消除递归 26
本章小结 27
习题1 27
第2章 排序算法 29
2.1 排序 29
2.1.1 排序问题 29
2.1.2 冒泡排序 30
2.1.3 交换排序 31
2.1.4 选择排序 33
2.1.5 插入排序 34
2.2 堆排序 35
2.2.1 堆 35
2.2.2 建堆 35
2.2.3 堆排序算法 38
2.2.4 堆排序的应用 40
2.3 快速排序 41
2.3.1 快速排序的描述 41
2.3.2 快速排序的性能 42
2.3.3 随机化的快速排序算法 42
2.3.4 快速排序分析 43
2.4 线性时间排序 44
2.4.1 排序算法的下界 44
2.4.2 计数排序 45
2.4.3 基数排序 46
2.4.4 桶排序 47
2.5 中数排序 49
2.5.1 最大和最小元素 49
2.5.2 一般选择问题 49
本章小结 51
习题2 52
第3章 分治法 55
3.1 一般算法 55
3.2 二分检索 56
3.3 找最大值和最小值 59
3.4 归并分类 62
3.4.1 基本方法 62
3.4.2 改进的归并分类算法 66
3.5 快速分类 67
3.5.1 快速分类算法 67
3.5.2 快速分类分析 68
3.6 选择问题 70
3.6.1 选择问题算法 70
3.6.2 SELECT2的实现 70
本章小结 72
习题3 72
第4章 图的搜索算法 74
4.1 图的基本概念 74
4.1.1 图的定义 74
4.1.2 图的基本术语 75
4.2 图的检索与遍历 77
4.2.1 广度优先检索与遍历 77
4.2.2 深度优先检索与遍历 80
4.3 回溯法 82
4.3.1 回溯法的一般方法 82
4.3.2 回溯算法的抽象描述 85
4.3.3 n-皇后问题 86
4.3.4 子集和数问题 88
4.3.5 0/1背包问题 90
4.3.6 图的m-着色问题 98
4.3.7 哈密顿环 101
4.3.8 连续邮资问题 103
4.3.9 回溯法的效率估计 107
本章小结 111
习题4 111
第5章 贪心算法 114
5.1 算法概述 114
5.1.1 贪心选择性质 114
5.1.2 最优子结构性质 114
5.1.3 活动安排问题 115
5.2 背包问题 116
5.3 带有限期的作业排序 118
5.3.1 带有限期的作业排序算法 118
5.3.2 改进的带有限期的作业排序算法 121
5.4 最优归并模式 124
5.5 哈夫曼编码 126
5.5.1 前缀码 126
5.5.2 哈夫曼编码 127
5.6 最小生成树 129
5.6.1 Prim算法 130
5.6.2 Kruskal算法 133
5.7 单源点最短路径 136
本章小结 140
习题5 141
第6章 动态规划算法 145
6.1 一般方法 145
6.2 多段图 150
6.3 每对结点之间的最短路径 152
6.4 最优二分检索树 155
6.5 0/1背包问题 161
6.5.1 0/1背包问题的实例分析 161
6.5.2 DKP的实现 165
6.5.3 过程DKNAP的分析 167
6.6 可靠性设计 168
6.7 货郎担问题 170
6.8 流水线调度问题 172
本章小结 176
习题6 176
第7章 分支限界法 179
7.1 一般方法 179
7.1.1 FIFO和LIFO-检索 179
7.1.2 LC-检索 180
7.1.3 LC-检索的抽象化描述 184
7.1.4 分支限界法解最优化问题 185
7.2 0/1背包问题 190
7.2.1 LC-分支限界求解 191
7.2.2 FIFO-分支限界求解 195
7.3 货郎担问题 197
7.4 效率分析 204
本章小结 205
习题7 205
第8章 并行算法 208
8.1 并行计算机及并行模型 208
8.1.1 并行计算机 208
8.1.2 并行计算模型 211
8.1.3 并行计算机网络 212
8.1.4 并行算法的一般术语 214
8.2 SIMD共享存储模型的并行算法 215
8.2.1 播送算法 215
8.2.2 求和算法 216
8.2.3 并行k-选择算法 217
8.2.4 并行桶排序算法 218
8.2.5 有序表搜索并行算法 222
8.3 SIMD互联网络模型的并行算法 224
8.3.1 网孔上的随机序列搜索算法 224
8.3.2 树机上的矩阵和向量乘法 226
8.3.3 一维线性阵列上的奇偶转置排序算法 228
8.3.4 树机上求最小值算法 228
8.3.5 树机上的连通分量算法 232
8.4 MIMD共享存储模型的并行算法 234
8.4.1 异步枚举排序算法 234
8.4.2 单源点最短路径并行算法 235
8.4.3 最小生成树并行算法 238
8.4.4 Gauss-Seidel算法 240
8.4.5 牛顿求根并行算法 242
8.5 MIMD异步通信模型的并行算法 243
8.5.1 快速排序并行算法 243
8.5.2 二维网孔上的矩阵转置并行算法 244
8.5.3 矩阵并行分块乘法算法 246
8.5.4 分布式矩阵求逆的并行算法 247
8.5.5 分布式高斯消去并行算法 250
本章小结 255
习题8 255
第9章 NP-完全问题 257
9.1 计算模型 257
9.1.1 有限自动机 257
9.1.2 下推自动机 258
9.1.3 图灵机 259
9.2 P类与NP类问题 262
9.2.1 多项式时间界（Polynomial time） 262
9.2.2 P类问题 264
9.2.3 NP类问题 264
9.3 NP-完全问题 265
9.3.1 判定NP-完全问题的关键概念 265
9.3.2 NP-完全性 267
9.3.3 Cook定理 268
9.4 典型的NP-完全问题 272
9.4.1 NP-完全性的证明方法 272
9.4.2 典型的NP-完全问题 273
9.4.3 NP-完全问题的计算机实现 282
本章小结 283
习题9 285
第10章 近似算法 287
10.1 近似算法的性能 287
10.2 启发式算法 288
10.2.1 图着色问题 289
10.2.2 旅行商问题 290
10.3 任务安排的近似算法 291
10.4 覆盖问题的近似算法 295
10.4.1 顶点覆盖问题的近似算法 295
10.4.2 集合覆盖问题的近似算法 297
10.5 旅行售货员问题近似算法 299
10.5.1 具有三角不等式的旅行售货员问题 299
10.5.2 一般旅行售货员问题 302
10.6 背包问题 303
10.7 子集合问题的近似算法 305
10.7.1 解子集合问题的指数时间算法 305
10.7.2 子集合问题的完全多项式时间近似格式 306
本章小结 308
习题10 308
第11章 概率算法 311
11.1 概率算法概述 311
11.2 伪随机数 312
11.3 数值概率算法 313
11.3.1 用随机投点法计算π值 313
11.3.2 计算定积分 314
11.3.3 解非线性方程组 316
11.4 Sherwood算法 318
11.4.1 线性时间选择算法 319
11.4.2 搜索有序表 320
11.4.3 跳跃表 324
11.5 Las Vegas算法 329
11.5.1 n后问题 329
11.5.2 整数因子分解 333
11.6 Monte Carlo算法 335
11.6.1 Monte Carlo算法的基本思想 335
11.6.2 主元素问题 337
11.6.3 素数性测试 338
本章小结 339
习题11 340
主要参考文献 344