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

算法之道PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一篇 算法基础篇第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.6 O、Ω、Θ表示18

2.7 最好、最坏、平均19

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

2.9 O、Ω、Θ的性质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.7 VLSI布线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.1 Kruskal算法的正确性79

5.6.2 Kruskal算法的时间分析80

5.7 Prim算法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.1 Karger-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.2 CLUSTERING-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.2 Dijkstra最短路径算法220

12.4.3 Dijkstra算法举例221

12.4.4 Dijkstra算法与洪水泛滥222

12.4.5 Dijkstra算法的正确性223

12.4.6 Dijkstra算法的时间复杂性224

12.5 Bellman-Ford算法226

12.5.1 负权重的应对方式227

12.5.2 Bellman-Ford算法的正确性230

12.5.3 负循环检查问题231

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

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

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

12.6.2 直接动态规划解法233

12.6.3 矩阵乘法解法234

12.6.4 Floyd-Warshall算法235

12.6.5 Johnson算法236

12.6.6 Johnson等效变换237

12.6.7 差限问题解决238

12.7 天意难违240

思考题240

第五篇 难解与无解篇第13章 可解与不可解244

13.1 我们战无不胜吗245

13.2 易解与难解245

13.3 决策问题和优化问题246

13.4 决策问题247

13.5 P类问题247

13.6 NP类问题248

13.7 （确定性）图灵机249

13.8 非确定性图灵机249

13.9 非确定性算法250

13.10 回到NP类问题251

13.11 P和NP252

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

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

思考题254

第14章 NP完全问题256

14.1 玉龙雪山下的审判256

14.2 NP完全问题的定义257

14.3 NP完全的重要性258

14.4 多项式时间规约259

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

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

14.7 库克定理260

14.8 3-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