第1部分 算法和算法分析 3
第1章 算法问题求解基础 3
1.1 算法概述 3
1.1.1 什么是算法 3
1.1.2 为什么学习算法 5
1.2 问题求解方法 5
1.2.1 问题和问题求解 6
1.2.2 问题求解过程 6
1.3.1 算法问题求解过程 7
1.3 算法设计与分析 7
1.2.3 系统生命周期 7
1.3.2 如何设计算法 8
1.3.3 如何表示算法 8
1.3.4 如何确认算法 9
1.3.5 如何分析算法 9
1.4 递归和归纳 9
1.4.1 递归 9
1.4.2 递归算法示例 11
1.4.3 归纳证明 14
习题1 15
本章小结 15
第2章 算法分析基础 17
2.1 算法复杂度 17
2.1.1 什么是好的算法 17
2.1.2 影响程序运行时间的因素 18
2.1.3 算法的时间复杂度 19
2.1.4 使用程序步分析算法 20
2.1.5 算法的空间复杂度 21
2.2 渐近表示法 22
2.2.1 大O记号 22
2.2.3 Θ记号 24
2.2.2 Ω记号 24
2.2.4 小o记号 25
2.2.5 算法按时间复杂度分类 25
2.3 递推关系 26
2.3.1 递推方程 26
2.3.2 替换方法 27
2.3.3 迭代方法 27
2.3.4 主方法 28
2.4 分摊分析 29
2.4.1 聚集方法 30
2.4.2 会计方法 30
2.4.3 势能方法 31
本章小结 32
习题2 32
第3章 伸展树与跳表 35
3.1 伸展树 35
3.1.1 二叉搜索树 35
3.1.2 自调节树和伸展树 36
3.1.3 伸展操作 36
3.1.4 伸展树类 38
3.1.6 插入运算的实现 39
3.1.5 旋转的实现 39
3.1.7 分摊分析 41
3.2 跳表 43
3.2.1 什么是跳表 43
3.2.2 跳表类 45
3.2.3 级数分配 46
3.2.4 插入运算的实现 47
3.2.5 性能分析 49
本章小结 49
习题3 49
第4章 基本搜索和遍历方法 53
4.1 基本概念 53
第2部分 算法设计策略 53
4.2 图的搜索和遍历 54
4.2.1 搜索方法 54
4.2.2 邻接表类 55
4.2.3 广度优先搜索 56
4.2.4 深度优先搜索 58
4.3 双连通分量 61
4.3.1 基本概念 61
4.3.2 发现关节点 62
4.4.1 问题分解 66
4.4 与或图 66
4.3.3 构造双连通图 66
4.4.2 判断与或树是否可解 68
4.4.3 构建解树 69
本章小结 71
习题4 71
第5章 分治法 73
5.1 一般方法 73
5.1.1 分治法的基本思想 73
5.1.2 算法分析 74
5.1.3 数据结构 75
5.2.1 分治法求解 76
5.2 求最大最小元 76
5.2.2 时间分析 77
5.3 二分搜索 78
5.3.1 分治法求解 78
5.3.2 对半搜索 79
5.3.3 二叉判定树 80
5.3.4 搜索算法的时间下界 82
5.4 排序问题 83
5.4.1 合并排序 83
5.4.2 快速排序 85
5.4.3 排序算法的时间下界 90
5.5 选择问题 91
5.5.1 分治法求解 92
5.5.2 随机选择主元 92
5.5.3 线性时间选择算法 94
5.5.4 时间分析 96
5.5.5 允许重复元素的选择算法 97
5.6 斯特拉森矩阵乘法 97
5.6.1 分治法求解 97
5.6.2 斯特拉森分治法 98
本章小结 98
习题5 99
第6章 贪心法 102
6.1 一般方法 102
6.2 背包问题 103
6.2.1 问题描述 103
6.2.2 贪心法求解 104
6.2.3 算法正确性 105
6.3 带时限的作业排序 107
6.3.1 问题描述 107
6.3.2 贪心法求解 107
6.3.3 算法正确性 108
6.3.4 可行性判定 109
6.3.5 作业排序贪心算法 110
6.3.6 一种改进算法 111
6.4 最佳合并模式 114
6.4.1 问题描述 114
6.4.2 贪心法求解 115
6.4.3 算法正确性 116
6.5 最小代价生成树 117
6.5.1 问题描述 117
6.5.2 贪心法求解 118
6.5.3 普里姆算法 119
6.5.4 克鲁斯卡尔算法 121
6.5.5 算法正确性 123
6.6 单源最短路径 124
6.6.1 问题描述 124
6.6.2 贪心法求解 124
6.6.3 迪杰斯特拉算法 125
6.6.4 算法正确性 127
6.7 磁带最优存储 129
6.7.1 单带最优存储 129
6.7.2 多带最优存储 130
6.8.1 最优量度标准 131
6.8 贪心法的基本要素 131
6.8.2 最优子结构 132
本章小结 132
习题6 132
第7章 动态规划法 135
7.1 一般方法和基本要素 135
7.1.1 一般方法 135
7.1.2 基本要素 136
7.1.3 多段图问题 136
7.1.4 资源分配问题 139
7.1.5 关键路径问题 140
7.2.1 问题描述 143
7.2.2 动态规划法求解 143
7.2 每对结点间的最短路径 143
7.2.3 弗洛伊德算法 144
7.2.4 算法正确性 145
7.3 矩阵连乘 146
7.3.1 问题描述 146
7.3.2 动态规划法求解 147
7.3.3 矩阵连乘算法 148
7.3.4 备忘录方法 150
7.4.2 动态规划法求解 151
7.4 最长公共子序列 151
7.4.1 问题描述 151
7.4.3 最长公共子序列算法 152
7.4.4 算法的改进 154
7.5 最优二叉搜索树 154
7.5.1 问题描述 154
7.5.2 动态规划法求解 155
7.5.3 最优二叉搜索树算法 157
7.6 0/1背包 158
7.6.1 问题描述 158
7.6.2 动态规划法求解 159
7.6.3 0/1背包算法框架 161
7.6.4 0/1背包算法 164
7.6.5 性能分析 167
7.6.6 使用启发式方法 167
7.7 流水作业调度 168
7.7.1 问题描述 168
7.7.2 动态规划法求解 170
7.7.3 Johnson算法 172
本章小结 173
习题7 173
8.1.1 基本概念 175
第8章 回溯法 175
8.1 一般方法 175
8.1.2 剪枝函数和回溯法 176
8.1.3 回溯法的效率分析 178
8.2 n-皇后 179
8.2.1 问题描述 179
8.2.2 回溯法求解 179
8.2.3 n-皇后算法 180
8.2.4 时间分析 182
8.3.2 回溯法求解 183
8.3 子集和数 183
8.3.1 问题描述 183
8.3.3 子集和数算法 185
8.4 图的着色 186
8.4.1 问题描述 186
8.4.2 回溯法求解 187
8.4.3 图着色算法 187
8.5.1 问题描述 189
8.5.2 哈密顿环算法 189
8.5 哈密顿环 189
8.4.4 时间分析 189
8.6 0/1背包 191
8.6.1 问题描述 191
8.6.2 回溯法求解 191
8.6.3 限界函数 192
8.6.4 0/1背包算法 193
8.7 批处理作业调度 195
8.7.1 问题描述 195
8.7.2 回溯法求解 195
8.7.3 批处理作业调度算法 195
习题8 197
本章小结 197
第9章 分枝限界法 199
9.1 一般方法 199
9.1.1 分枝限界法概述 199
9.1.2 LC分枝限界法 201
9.1.3 15谜问题 202
9.2 求最优解的分枝限界法 204
9.2.1 上下界函数 204
9.2.2 FIFO分枝限界法 205
9.2.3 LC分枝限界法 206
9.3.2 分枝限界法求解 207
9.3 带时限的作业排序 207
9.3.1 问题描述 207
9.3.3 带时限作业排序算法 208
9.4 0/1背包 211
9.4.1 问题描述 211
9.4.2 分枝限界法求解 211
9.4.3 0/1背包算法 212
9.5 旅行商问题 215
9.5.1 问题描述 215
9.5.2 分枝限界法求解 215
9.6.2 分枝限界法求解 220
9.6 批处理作业调度 220
9.6.1 问题描述 220
9.6.3 批处理作业调度算法 221
本章小结 224
习题9 224
第3部分 求解困难问题 229
第10章 NP完全问题 229
10.1 基本概念 229
10.1.1 不确定算法和不确定机 229
10.1.2 可满足性问题 232
10.1.4 NP难度和NP完全问题 233
10.1.3 P类和NP类问题 233
10.2 Cook定理和证明 234
10.2.1 Cook定理 234
10.2.2 简化的不确定机模型 234
10.2.3 证明Cook定理 235
10.3 一些典型的NP完全问题 240
10.3.1 最大集团 240
10.3.2 顶点覆盖 241
10.3.3 3元CNF可满足性 242
10.3.4 图的着色数 243
10.3.5 有向哈密顿环 244
10.3.6 恰切覆盖 246
10.3.7 子集和数 248
10.3.8 分划问题 248
本章小结 249
习题10 249
第11章 随机算法 251
11.1 基本概念 251
11.1.1 随机算法概述 251
11.1.2 随机数发生器 251
11.1.3 随机算法分类 251
11.2.1 标识重复元素算法 252
11.2 拉斯维加斯算法 252
11.2.2 性能分析 253
11.3 蒙特卡罗算法 254
11.3.1 素数测试问题 254
11.3.2 伪素数测试 254
11.3.3 米勒-拉宾算法 255
11.3.4 性能分析 256
11.4 舍伍德算法 257
11.4.1 随机快速排序算法 257
11.4.2 舍伍德算法的其他应用 257
习题11 258
本章小结 258
12.1 近似算法的性能 260
12.1.1 基本概念 260
12.1.2 绝对性能保证 260
第12章 近似算法 260
12.1.3 相对性能保证 261
12.1.4 近似方案 262
12.2 绝对近似算法 262
12.2.1 最多程序存储问题 262
12.2.2 NP难度绝对近似算法 263
12.3.1 顶点覆盖近似算法 264
12.3 ε-近似算法 264
12.3.2 旅行商问题 265
12.3.3 NP难度ε-近似旅行商问题 266
12.3.4 具有三角不等式性质的旅行商问题 267
12.3.5 任务调度近似算法 268
12.4 ε（n）-近似算法 271
12.4.1 集合覆盖问题 271
12.4.2 集合覆盖近似算法 272
12.4.3 ln(n)-近似算法 273
12.5.1 任务调度近似方案 274
12.5 多项式时间近似方案 274
12.5.2 多项式时间近似方案 275
12.6 子集和数的完全多项式时间近似方案 276
12.6.1 子集和数指数时间算法 276
12.6.2 完全多项式时间近似方案 277
本章小结 279
习题12 279
13.1.2 什么是密码 281
13.1.1 信息安全 281
13.1 信息安全和密码学 281
第13章 密码算法 281
13.1.3 密码体制 282
13.2 数论初步 283
13.3 背包密码算法 285
13.3.1 背包算法 285
13.3.2 超递增背包 285
13.3.3 由私人密钥产生公开密钥 286
13.3.4 加密方法 287
13.3.5 解密方法 287
13.3.6 背包安全性 287
13.4.1 RSA算法概述 288
13.4 RSA算法 288
13.4.2 RSA的安全性 289
13.5 散列函数和消息认证 289
13.5.1 散列函数 289
13.5.2 散列函数结构 290
13.5.3 消息认证 290
13.6 数字签名 291
13.6.1 RSA数字签名体制 291
13.6.2 需仲裁数字签名 291
本章小结 292
习题13 292
附录A 专有名词中英文对照表 293
附录B C＋＋程序设计概要 298
B.1 函数与参数传递 298
B.2 动态存储分配 301
B.3 类与对象 302
B.4 函数和运算符重载 303
B.5 继承性和派生类 304
B.6 多态性、虚函数和动态联编 305
B.7 纯虚函数和抽象类 306
B.8 模板函数和模板类 307
B.9 友元函数和友元类 310
参考文献 313