《算法之道》勘误

本书甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。本书将算法的讨论分为五大部分：算法基本战略、算法设计战略、算法分析战略、经典算法讨论、难解与无解问题。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。本书既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。

封面图

目录

• 前言
• 第一篇算法基础篇
• 第1章从无有到无穷2
• 1.1意念与现实3
• 1.2什么是算法4
• 1.3算法的表示6
• 1.4算法之魂7
• 1.5如何比较速度8
• 1.6算法与计算机的关系9
• 1.7算法的范畴10
• 1.8为什么学习算法10
• 思考题11
• 第2章计数与渐近12
• 2.1算法的分析12
• 2.1.1正确性分析13
• 2.1.2时空效率分析14
• 2.1.3时空特性分析14
• 2.2计数：算法分析的核心14
• 2.3算法设计15
• 2.4算法效率表示16
• 2.5渐近分析17
• 2.6O、(、(表示18
• 2.7最好、最坏、平均19
• 2.8O、(、(的另一类定义21
• 2.9O、(、(的性质22
• 2.10要更快的计算机还是要更快的算法22
• 思考题23
• 第3章分治与递归25
• 3.1分而治之为上策26
• 3.2分治策略28
• 3.3递归表达式求解29
• 3.3.1递归树法29
• 3.3.2替换解法30
• 3.3.3大师解法32
• 3.4分治策略举例1：乘方运算35
• 3.5生命不能承受之重：矩阵乘法36
• 3.6魔鬼序列：斐波那契序列38
• 3.7VLSI 布线41
• 3.8多项式乘法43
• 3.9分治就在潜意识深处43
• 思考题43
•  
• 第二篇算法设计篇
• 第4章动态规划思想46
• 4.1什么是动态规划47
• 4.2流水装配线问题48
• 4.3最长公共子序列52
• 4.3.1第一种解法：蛮力策略52
• 4.3.2第二种解法：动态规划53
• 4.4最长公共子序列变种55
• 4.5记忆递归法55
• 4.6空间效率改善56
• 4.7最优二叉搜索树56
• 4.7.1递归解法59
• 4.7.2计算最优答案59
• 4.8最优子结构与重叠子问题62
• 4.8.1最优子结构62
• 4.8.2重叠子问题63
• 4.9动态规划与静态规划的关系63
• 4.10动态规划与静态规划的相互转换64
• 思考题65
• 第5章贪婪选择思想67
• 5.1仅有动态规划是不够的67
• 5.2什么是贪婪68
• 5.3背包问题68
• 5.4贪婪选择属性71
• 5.5教室规划问题72
• 5.6最小生成树76
• 5.6.1Kruskal算法的正确性79
• 5.6.2Kruskal算法的时间分析80
• 5.7Prim算法80
• 5.8霍夫曼树和霍夫曼编码83
• 5.8.1霍夫曼树85
• 5.8.2霍夫曼编码86
• 5.8.3霍夫曼编码的无前缀编码
• 性质87
• 5.9贪婪选择属性88
• 5.10标准分治、动态规划和贪婪选择的比较89
• 思考题90
• 第6章随机化思想92
• 6.1为什么要随机化93
• 6.2随机的平方94
• 6.3什么是随机化算法95
• 6.4拉斯维加斯算法96
• 6.5蒙特卡罗算法97
• 6.6素性测试97
• 6.7矩阵乘积验证器100
• 6.8随机化最小生成树算法102
• 6.8.1Karger-Klein-Tarjan算法103
• 6.8.2节点降低算法103
• 6.8.3线性时间最小生成树算法104
• 6.8.4线性时间最小生成树算法的时间成本分析104
• 6.9随机数的生成105
• 6.10随机化算法的应用105
• 思考题106
•  
• 第三篇算法分析篇
• 第7章概率分析108
• 7.1一切都在概率中109
• 7.2什么是概率分析109
• 7.3梦幻情人的代价110
• 7.3.1直接分析112
• 7.3.2最坏情况分析113
• 7.3.3最好情况分析113
• 7.3.4平均情况分析113
• 7.3.5平均情况下成本的概率分析113
• 7.4概率分析结果的有效性114
• 7.5正确概率分析的保障115
• 7.6梦幻情人的概率115
• 7.7随机排列问题117
• 7.8南柯一梦：从无穷到无有119
• 7.9概率分析的其他应用120
• 思考题121
• 第8章摊销分析122
• 8.1什么是摊销分析123
• 8.2摊销分析与数据结构124
• 8.3摊销分析的几种方法124
• 8.4聚类分析125
• 8.4.1栈操作的聚类分析125
• 8.4.2二进制计数器的聚类分析126
• 8.5会计分析128
• 8.6势能分析130
• 8.6.1栈操作的势能分析130
• 8.6.2二进制计数器的势能分析131
• 8.7摊销分析应用：表格扩展的代价131
• 8.7.1动态表插入操作的聚类分析134
• 8.7.2动态表插入操作的会计分析134
• 8.7.3动态表插入操作的势能分析136
• 8.8运气不好就摊销137
• 思考题138
• 第9章竞争分析139
• 9.1什么是竞争分析139
• 9.2在线算法和离线算法141
• 9.3竞争力142
• 9.4健忘对手和优良对手142
• 9.5线性表更新问题143
• 9.6前置移动算法的竞争分析145
• 9.7聚类问题147
• 9.7.1聚类问题的次优解算法148
• 9.7.2CLUSTERING-ALGORITHM算法的竞争分析148
• 9.8竞争分析与普通算法分析149
• 思考题149
• 第四篇经典算法篇
• 第10章排序和次序152
• 10.1排序无处不在152
• 10.2插入排序153
• 10.2.1插入排序的效率分析154
• 10.2.2折半插入排序155
• 10.3归并排序156
• 10.4快速排序158
• 10.4.1快速排序的过程158
• 10.4.2快速排序的时间复杂性分析159
• 10.4.3最坏情况分析160
• 10.4.4最好情况分析160
• 10.4.5平均情况分析161
• 10.5随机化快速排序162
• 10.6排序的下限164
• 10.7线性排序165
• 10.8计数排序166
• 10.9基数排序168
• 10.9.1基数排序的正确性169
• 10.9.2基数排序的时间效率分析170
• 10.10桶排序171
• 10.10.1桶排序的定义172
• 10.10.2桶排序的正确性173
• 10.10.3桶排序的时间复杂性分析173
• 10.11次序选择175
• 10.12快速次序选择算法176
• 10.13随机快速次序选择算法178
• 10.14最坏情况下的线性选择算法179
• 10.14.1杠杆点好坏分析180
• 10.14.2算法的时间复杂性分析181
• 思考题181
• 第11章搜索与哈希183
• 11.1搜索问题184
• 11.2顺序搜索184
• 11.3折半搜索185
• 11.4常数搜索186
• 11.5哈希搜索187
• 11.6哈希函数选择189
• 11.6.1直接哈希189
• 11.6.2除法（模除法）哈希190
• 11.6.3乘法哈希191
• 11.6.4乘法哈希的赌徒原理192
• 11.6.5乘方取中法193
• 11.7哈希算法的碰撞问题193
• 11.7.1开放寻址哈希193
• 11.7.2开放寻址哈希的时间成本194
• 11.7.3开放寻址下成功搜索的时间成本195
• 11.7.4封闭寻址哈希196
• 11.7.5探寻序列的设计197
• 11.7.6封闭寻址哈希的效率分析199
• 11.7.7搜索不成功的时间成本199
• 11.7.8成功搜索的效率分析201
• 11.8哈希表元素删除201
• 11.9随机化哈希202
• 11.10全域哈希203
• 11.11全域哈希构造204
• 11.12完美哈希206
• 思考题208
• 第12章最短路径211
• 12.1剑指罗马211
• 12.2最短路径问题213
• 12.3单源单点最短路径问题215
• 12.3.1深度优先搜索与广度优先搜索215
• 12.3.2深度优先解法217
• 12.4单源多点最短路径问题218
• 12.4.1最短路径的性质219
• 12.4.2Dijkstra最短路径算法220
• 12.4.3Dijkstra算法举例221
• 12.4.4Dijkstra算法与洪水泛滥222
• 12.4.5Dijkstra算法的正确性223
• 12.4.6Dijkstra算法的时间复杂性224
• 12.5Bellman-Ford算法226
• 12.5.1负权重的应对方式227
• 12.5.2Bellman-Ford算法的正确性230
• 12.5.3负循环检查问题231
• 12.5.4Bellman-Ford算法的时间复杂性231
• 12.6多源多点最短路径问题232
• 12.6.1多源多点最短路径问题解决思路232
• 12.6.2直接动态规划解法233
• 12.6.3矩阵乘法解法234
• 12.6.4Floyd-Warshall 算法235
• 12.6.5Johnson 算法236
• 12.6.6Johnson等效变换237
• 12.6.7差限问题解决238
• 12.7天意难违240
• 思考题240
•  
• 第五篇难解与无解篇
• 第13章可解与不可解244
• 13.1我们战无不胜吗245
• 13.2易解与难解245
• 13.3决策问题和优化问题246
• 13.4决策问题247
• 13.5P类问题247
• 13.6NP类问题248
• 13.7 （确定性）图灵机249
• 13.8非确定性图灵机249
• 13.9非确定性算法250
• 13.10回到NP类问题251
• 13.11P和NP252
• 13.12搜索问题、决策问题和优化问题253
• 13.13有没有解和是否可决定253
• 思考题254
• 第14章NP完全问题256
• 14.1玉龙雪山下的审判256
• 14.2NP完全问题的定义257
• 14.3NP完全的重要性258
• 14.4多项式时间规约259
• 14.5如何证明一个问题S是NP完全259
• 14.6第1个NP完全问题的证明260
• 14.7库克定理260
• 14.83-SAT问题263
• 14.9证明NP难的技巧264
• 14.10整数规划265
• 14.11独立集问题266
• 14.12汉密尔顿回路问题268
• 14.13讨论：弱NP完全、强NP完全和中NP完全271
• 思考题272
• 第15章无解与近似273
• 15.1难解问题274
• 15.2不可决定问题274
• 15.3程序终结的判断275
• 15.4难解之题的求解276
• 15.5智能穷举、近似算法和本地搜索277
• 15.6智能穷举之回溯策略279
• 15.7智能穷举之分支限界280
• 15.8贪婪近似策略280
• 15.9启发式搜索策略281
• 15.10模拟淬火算法282
• 15.10.1模拟淬火算法的思想284
• 15.10.2模拟淬火算法的基本循环284
• 15.10.3淬火算法描述284
• 思考题286
• 结语算法之道288
• 附录算法随想290
• 参考文献293