算法设计与分析基础（第3版 详解版）

详细目录
第1章　导言 1
1.1　什么是算法 3
习题1.1 8
1.2　算法问题求解基础 9
1.2.1  理解问题 10
1.2.2  了解计算设备的性能 11
1.2.3  在精确和近似解法之间做出选择 12
1.2.4  算法的设计技术 12
1.2.5  设计算法和数据结构 12
1.2.6  算法描述方法 13
1.2.7  算法的正确性证明 14
1.2.8  分析算法 14
1.2.9  为算法写代码 16
习题1.2 17
1.3　重要的问题类型 19
1.3.1  排序 19
1.3.2  查找 21
1.3.3  字符串处理 21
1.3.4  图问题 22
1.3.5  组合问题 22
1.3.6  几何问题 23
1.3.7  数值问题 23
习题1.3 24
1.4　基本数据结构 26
1.4.1  线性数据结构 26
1.4.2  图 29
1.4.3  树 32
1.4.4  集合与字典 36
习题1.4 38
本章要点小结 39
第2章　算法效率分析基础 41
2.1　分析框架 42
2.1.1  度量输入规模 43
2.1.2  运行时间的度量单位 44
2.1.3  增长量级 45
2.1.4  算法的最差、最优和平均效率 47
2.1.5  分析框架概要 50
习题2.1 50
2.2　渐近符号和基本效率类型 52
2.2.1  非正式的介绍 53
2.2.2  符号O 53
2.2.3  符号Ω 54
2.2.4  符号Θ 55
2.2.5  渐近符号的有用特性 56
2.2.6  利用极限比较增长量级 57
2.2.7  基本效率类别 58
习题2.2 60
2.3  非递归算法的数学分析 61
习题2.3 67
2.4  递归算法的数学分析 70
习题2.4 77
2.5　例题：计算第n个斐波那契数 80
习题2.5 84
2.6　算法的经验分析 85
习题2.6 91
2.7　算法可视化 92
本章要点小结 95
第3章　蛮力法 97
3.1　选择排序和冒泡排序 98
3.1.1  选择排序 98
3.1.2  冒泡排序 100
习题3.1 102
3.2　顺序查找和蛮力字符串匹配 103
3.2.1  顺序查找 104
3.2.2  蛮力字符串匹配 104
习题3.2 106
3.3　最近对和凸包问题的蛮力算法 108
3.3.1  最近对问题 108
3.3.2  凸包问题 110
习题3.3 113
3.4　穷举查找 115
3.4.1  旅行商问题 116
3.4.2  背包问题 117
3.4.3  分配问题 119
习题3.4 120
3.5　深度优先查找和广度优先查找 122
3.5.1  深度优先查找 122
3.5.2  广度优先查找 125
习题3.5 128
本章要点小结 130
第4章　减治法 132
4.1　插入排序 135
习题4.1 137
4.2　拓扑排序 140
习题4.2 143
4.3  生成组合对象的算法 145
4.3.1  生成排列 145
4.3.2  生成子集 148
习题4.3 150
4.4  减常因子算法 151
4.4.1  折半查找 152
4.4.2  假币问题 154
4.4.3  俄式乘法 155
4.4.4  约瑟夫斯问题 156
习题4.4 158
4.5　减可变规模算法 160
4.5.1  计算中值和选择问题 160
4.5.2  插值查找 164
4.5.3  二叉查找树的查找和插入 165
4.5.4  尼姆游戏 166
习题4.5 168
本章要点小结 170
第5章　分治法 171
5.1　合并排序 173
习题5.1 176
5.2　快速排序 178
习题5.2 183
5.3　二叉树遍历及其相关特性 185
习题5.3 188
5.4　大整数乘法和Strassen矩阵乘法 189
5.4.1  大整数乘法 190
5.4.2  Strassen矩阵乘法 192
习题5.4 194
5.5　用分治法解最近对问题和凸包问题 195
5.5.1  最近对问题 195
5.5.2  凸包问题 198
习题5.5 200
本章要点小结 201
第6章　变治法 203
6.1　预排序 204
习题6.1 207
6.2　高斯消去法 210
6.2.1  LU分解 215
6.2.2  计算矩阵的逆 216
6.2.3  计算矩阵的行列式 217
习题6.2 218
6.3　平衡查找树 220
6.3.1  平衡二叉查找树 221
6.3.2  2-3树 225
习题6.3 228
6.4　堆和堆排序 229
6.4.1  堆的概念 229
6.4.2  堆排序 234
习题6.4 235
6.5　霍纳法则和二进制幂 236
6.5.1  霍纳法则 237
6.5.2  二进制幂 239
习题6.5 242
6.6　问题化简 243
6.6.1  求最小公倍数 244
6.6.2  计算图中的路径数量 245
6.6.3  最优化问题的化简 246
6.6.4  线性规划 247
6.6.5  简化为图问题 250
习题6.6 251
本章要点小结 253
第7章　时空权衡 255
7.1　计数排序 256
习题7.1 260
7.2　字符串匹配中的输入增强技术 261
7.2.1　Horspool算法 262
7.2.2　Boyer-Moore算法 265
习题7.2 270
7.3　散列法 271
7.3.1　开散列(分离链) 273
7.3.2　闭散列(开式寻址) 275
习题7.3 278
7.4　B树 279
习题7.4 283
本章要点小结 284
第8章　动态规划 285
8.1　三个基本例子 287
习题8.1 292
8.2　背包问题和记忆功能 295
8.2.1  背包问题 295
8.2.2　记忆功能 297
习题8.2 298
8.3　最优二叉查找树 299
习题8.3 304
8.4　Warshall算法和Floyd算法 305
8.4.1　Warshall算法 306
8.4.2　计算完全最短路径的Floyd算法 309
习题8.4 313
本章要点小结 314
第9章　贪婪技术 315
9.1　Prim算法 318
习题9.1 323
9.2　Kruskal算法 325
习题9.2 332
9.3　Dijkstra算法 334
习题9.3 338
9.4　哈夫曼树及编码 339
习题9.4 343
本章要点小结 344
第10章　迭代改进 346
10.1　单纯形法 347
10.1.1  线性规划的几何解释 348
10.1.2  单纯形法概述 352
10.1.3  单纯形法其他要点 358
习题10.1 360
10.2　最大流量问题 362
习题10.2 372
10.3　二分图的最大匹配 373
习题10.3 380
10.4　稳定婚姻问题 382
习题10.4 386
本章要点小结 387
第11章　算法能力的极限 388
11.1　如何求下界 389
11.1.1　平凡下界 390
11.1.2　信息论下界 391
11.1.3　敌手下界 391
11.1.4　问题化简 393
习题11.1 394
11.2　决策树 396
11.2.1　排序的决策树 397
11.2.2　查找有序数组的决策树 399
习题11.2 401
11.3　P、NP和NP完全问题 403
11.3.1　P和NP问题 403
11.3.2　NP完全问题 407
习题11.3 411
11.4　数值算法的挑战 414
习题11.4 421
本章要点小结 422
第12章　应对算法能力的极限 425
12.1　回溯法 426
12.1.1　n皇后问题 427
12.1.2　哈密顿回路问题 428
12.1.3　子集和问题 429
12.1.4　概括性说明 430
习题12.1 432
12.2　分支定界法 434
12.2.1　分配问题 435
12.2.2　背包问题 437
12.2.3　旅行商问题 440
习题12.2 442
12.3　NP难题的近似算法 443
12.3.1　旅行商问题的近似算法 445
12.3.2　背包问题的近似算法 454
习题12.3 459
12.4　解非线性方程的算法 460
12.4.1　对分法 462
12.4.2　试位法 465
12.4.3　牛顿法 466
习题12.4 468
本章要点小结 469
后记 472
附录A　算法分析的实用公式 477
附录B　递推关系简明指南 480
参考文献 494