算法之道 第2版PDF|Epub|txt|kindle电子书版本网盘下载

算法之道 第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和NP273

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