算法之道 第2版PDF电子书下载

第一篇 算法基础篇 1

第1章 从无有到无穷 3

1.1意念与现实 4

1.2什么是算法 5

1.3算法的表示 7

1.4算法之魂 8

1.5如何比较速度 9

1.6算法与计算机的关系 10

1.7算法的范畴 11

1.8为什么学习算法 11

思考题 12

第2章 计数与渐近 13

2.1算法的分析 13

2.1.1正确性分析 14

2.1.2时空效率分析 15

2.1.3时空特性分析 15

2.2计数：算法分析的核心 15

2.3算法设计 16

2.4算法效率表示 17

2.5渐近分析 18

2.6 O、 Ω、 Θ表示 19

2.7最好、最坏、平均 20

2.8 O、Ω、 Θ的另一类定义 22

2.9 O、Ω、Θ的性质 23

2.10要更快的计算机还是要更快的算法 23

思考题 24

第3章 分治与递归 27

3.1分而治之为上策 28

3.2分治策略 30

3.3递归表达式求解 31

3.3.1递归树法 31

3.3.2替换解法 32

3.3.3大师解法 34

3.4分治策略举例1：乘方运算 37

3.5生命中不能承受之重：矩阵乘法 37

3.6魔鬼序列：斐波那契序列 40

3.6.1由底至上 42

3.6.2使用通式 42

3.6.3使用矩阵乘方 42

3.7 VLSI布线 43

3.8多项式乘法 44

3.9分治就在潜意识 44

思考题 45

第二篇 算法设计篇 49

第4章 动态规划思想 49

4.1什么是动态规划 51

4.2流水线问题 51

4.3最长公共子序列 55

4.3.1第一种解法：蛮力策略 56

4.3.2第二种解法：动态规划 57

4.4最长公共子序列变种 59

4.5记忆递归法 59

4.6空间效率改善 60

4.7最优二叉搜索树 60

4.7.1递归解法 63

4.7.2计算最优答案 64

4.8最优子结构与重叠子问题 66

4.8.1最优子结构 67

4.8.2重叠子问题 67

4.9动态规划与静态规划的关系 68

4.10动态规划与静态规划的相互转换 69

思考题 69

第5章 贪婪选择思想 71

5.1仅有动态规划是不够的 71

5.2什么是贪婪 72

5.3背包问题 72

5.4贪婪选择属性 75

5.5教室规划问题 75

5.6最小生成树 79

5.6.1 Kruskal算法的正确性 83

5.6.2 Kruskal算法的时间分析 83

5.7 Prim算法 84

5.8霍夫曼树和霍夫曼编码 87

5.8.1霍夫曼树 89

5.8.2霍夫曼编码 90

5.8.3霍夫曼编码的无前缀编码性质 91

5.9进程调度问题 92

5.10贪婪选择属性 92

5.11标准分治、动态规划和贪婪选择的比较 94

思考题 95

第6章 随机化思想 97

6.1为什么要随机化 98

6.2随机的平方 99

6.3什么是随机化算法 100

6.4拉斯维加斯算法 101

6.5蒙特卡罗算法 102

6.6素性测试 103

6.7矩阵乘积验证器 105

6.8随机化最小生成树算法 107

6.8.1 Karger-Klein-Tarjan算法 108

6.8.2结点降低算法 109

6.8.3线性时间最小生成树算法 109

6.8.4线性时间最小生成树算法的时间成本分析 109

6.9随机数的生成 110

6.10随机化算法的应用 111

思考题 111

第三篇 算法分析篇 115

第7章 概率分析 115

7.1一切都在概率中 116

7.2什么是概率分析 117

7.3梦幻情人的代价 117

7.3.1直接分析 119

7.3.2最坏情况分析 119

7.3.3最好情况分析 120

7.3.4平均情况分析 120

7.3.5平均情况下成本的概率分析 120

7.3.6概率分析结果的有效性 121

7.3.7正确概率分析的保障 122

7.4梦幻情人的概率 122

7.5随机排列问题 124

7.6跳转表问题 126

7.6.1跳转表插入操作 128

7.6.2随机化跳转表构建算法 128

7.7南柯一梦：从无穷到无有 130

7.8概率分析的其他应用 132

思考题 132

第8章 摊销分析 135

8.1什么是摊销分析 136

8.2摊销分析与数据结构 137

8.3摊销分析的几种方法 138

8.4聚类分析 138

8.4.1栈操作的聚类分析 139

8.4.2二进制计数器的聚类分析 140

8.5会计分析 141

8.6势能分析 143

8.6.1栈操作的势能分析 144

8.6.2二进制计数器的势能分析 144

8.7摊销分析应用：表格扩展的代价 145

8.7.1动态表插入操作的聚类分析 147

8.7.2动态表插入操作的会计分析 148

8.7.3动态表插入操作的势能分析 149

8.8运气不好就摊销 150

思考题 151

第9章 竞争分析 153

9.1什么是竞争分析 153

9.2在线算法和离线算法 154

9.3竞争力 156

9.4健忘对手和优良对手 156

9.5线性表更新问题 157

9.6前置移动算法的竞争分析 159

9.7聚类问题 161

9.7.1聚类问题的次优解算法 162

9.7.2 CLUSTERING-ALGORITHM算法的竞争分析 162

9.8竞争分析与普通算法分析 163

思考题 163

第四篇 经典算法篇 169

第10章 排序与次序 169

10.1排序无处不在 169

10.2插入排序 170

10.2.1插入排序的效率分析 172

10.2.2折半插入排序 172

10.3归并排序 173

10.4快速排序 175

10.4.1快速排序的过程 175

10.4.2快速排序的时间复杂性分析 177

10.4.3最坏情况分析 177

10.4.4最好情况分析 177

10.4.5平均情况分析 178

10.5随机化快速排序 179

10.6排序的下限 181

10.7线性排序 182

10.8计数排序 183

10.9基数排序 186

10.9.1基数排序的正确性 187

10.9.2基数排序的时间效率分析 187

10.10桶排序 189

10.10.1桶排序的定义 190

10.10.2桶排序的正确性 190

10.10.3桶排序的时间复杂性分析 191

10.11次序选择 192

10.12快速次序选择算法 193

10.13随机快速次序选择算法 195

10.14最坏情况下的线性选择算法 197

10.14.1杠杆点好坏分析 198

10.14.2算法时间复杂性分析 198

思考题 199

第11章 搜索与散列 201

11.1搜索问题 202

11.2顺序搜索 203

11.3折半搜索 204

11.4常数搜索 205

11.5散列搜索 206

11.6散列函数选择 207

11.6.1直接散列 208

11.6.2除法（模除法）散列 208

11.6.3乘法散列 209

11.6.4乘法散列的赌徒原理 210

11.6.5乘方取中法 211

11.7散列算法的碰撞问题 211

11.7.1开放寻址散列 212

11.7.2开放寻址散列的时间成本 212

11.7.3开放寻址下成功搜索的时间成本 213

11.7.4封闭寻址散列 214

11.7.5探寻序列的设计 215

11.7.6封闭寻址散列的效率分析 217

11.7.7搜索不成功的时间成本 217

11.7.8成功搜索的效率分析 219

11.8散列表元素删除 219

11.9随机化散列 220

11.10全域散列 221

11.11完美散列 224

思考题 227

第12章 最短路径 231

12.1剑指罗马 231

12.2最短路径问题 233

12.3单源单点最短路径问题 235

12.3.1深度优先与广度优先搜索 235

12.3.2深度优先解法 237

12.4单源多点最短路径问题 238

12.4.1最短路径的性质 239

12.4.2 Dijkstra最短路径算法 240

12.4.3 Dijkstra算法举例 241

12.4.4 Dijkstra算法与洪水泛滥 242

12.4.5 Dijkstra算法的正确性 243

12.4.6Dijkstra算法的时间复杂性 245

12.5 Bellman-Ford算法 246

12.5.1负权重的应对方式 247

12.5.2 Bellman-Ford算法的正确性 250

12.5.3负循环检查问题 251

12.5.4 Bellman-Ford算法的时间复杂性 252

12.6多源多点最短路径问题 252

12.6.1多源多点最短路径问题解决思路 252

12.6.2直接动态规划解法 253

12.6.3矩阵乘法解法 255

12.6.4 Floyd-Warshall算法 255

12.6.5 Johnson算法 256

12.6.6 Johnson等效变换 257

12.6.7差限问题解决 259

12.7天意难违 260

思考题 261

第五篇 难解与无解篇 265

第13章 易解与难解 265

13.1我们战无不胜吗 266

13.2易解与难解 266

13.3决策问题和优化问题 267

13.4决策问题 268

13.5 P类问题 269

13.6 NP类问题 269

13.7（确定性）图灵机 270

13.8非确定性图灵机 271

13.9非确定性算法 271

13.10回到NP类问题 272

13.11 P和NP 273

13.12搜索问题、决策问题和优化问题 274

13.13有没有解和是否可决定 275

思考题 276

第14章NP完全问题 277

14.1玉龙雪山下的审判 277

14.2 NP完全问题的定义 278

14.3 NP完全的重要性 279

14.4多项式时间规约 280

14.5如何证明一个问题S是NP完全问题 281

14.6第1个NP完全问题的证明 281

14.7库克定理 281

14.8 3-SAT问题 284

14.9证明NP难的技巧 285

14.10整数规划 286

14.11独立集问题 287

14.12汉密尔顿回路问题 289

14.13讨论：弱NP完全、强NP完全和中NP完全 293

思考题 293

第15章 无解与近似 295

15.1难解问题 296

15.2不可决定问题 296

15.3程序终结的判断 297

15.4难解之题的求解 298

15.5智能穷举、近似算法和本地搜索 299

15.6智能穷举之回溯策略 301

15.7智能穷举之分支限界 302

15.8贪婪近似策略 302

15.9启发式搜索策略 303

15.10模拟退火算法 305

15.10.1模拟退火算法的思想 306

15.10.2模拟退火算法的基本循环 306

15.10.3退火算法描述 307

15.11基因/遗传算法 308

15.11.1生物进化与遗传 309

15.11.2遗传算法的基本要义 309

15.11.3遗传算法的实现 310

15.11.4遗传算法的基本运算过程 313

15.11.5遗传算法的现状 314

15.12概率尽在一切中 314

思考题 315

结语 算法之道 317

附录 算法随想 321

参考文献 324