算法设计技巧与分析【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

算法设计技巧与分析PDF格式电子书版下载

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

第一部分 基本概念和算法导引1

第1章 算法分析基本概念2

1.1 引言2

1.2 历史背景2

1.3 二分搜索3

1.4 合并两个已排序的表6

1.5 选择排序7

1.6 插入排序8

1.7 自底向上合并排序9

1.8 时间复杂性12

1.9 空间复杂性19

1.10 最优算法20

1.11 如何估计算法运行时间21

1.12 最坏情况和平均情况的分析26

1.13 平摊分析29

1.14 输入大小和问题实例31

1.15 练习32

1.16 参考注释38

第2章 数学预备知识39

2.1 集合、关系和函数39

2.2 证明方法41

2.3 对数44

2.4 底函数和顶函数45

2.5 阶乘和二项式系数45

2.6 鸽巢原理48

2.7 和式48

2.8 递推关系52

2.9 练习63

第3章 数据结构67

3.1 引言67

3.2 链表67

3.3 图68

3.4 树69

3.5 根树70

3.6 二叉树71

3.7 练习72

3.8 参考注释73

第4章 堆和不相交集数据结构74

4.1 引言74

4.2 堆74

4.3 不相交集数据结构80

4.4 练习85

4.5 参考注释88

第二部分 基于递归的技术89

第5章 归纳法90

5.1 引言90

5.2 两个简单的例子90

5.3 基数排序92

5.4 整数幂93

5.5 多项式求值（Horner规则）94

5.6 生成排列95

5.7 寻找多数元素98

5.8 练习99

5.9 参考注释101

第6章 分治102

6.1 引言102

6.2 二分搜索103

6.3 合并排序105

6.4 分治范式107

6.5 寻找中项和第k小元素109

6.6 快速排序112

6.7 大整数乘法118

6.8 矩阵乘法119

6.9 最近点对问题121

6.10 练习124

6.11 参考注释128

第7章 动态规划129

7.1 引言129

7.2 最长公共子序列问题130

7.3 矩阵链相乘132

7.4 动态规划范式136

7.5 所有点对的最短路径问题136

7.6 背包问题138

7.7 练习140

7.8 参考注释144

第三部分 最先割技术145

第8章 贪心算法146

8.1 引言146

8.2 最短路径问题146

8.3 最小耗费生成树（Kruskal算法）151

8.4 最小耗费生成树（Prim算法）153

8.5 文件压缩157

8.6 练习159

8.7 参考注释161

第9章 图的遍历162

9.1 引言162

9.2 深度优先搜索162

9.3 深度优先搜索的应用165

9.4 广度优先搜索169

9.5 广度优先搜索的应用170

9.6 练习170

9.7 参考注释172

第四部分 问题的复杂性173

第10章 NP完全问题174

10.1 引言174

10.2 P类176

10.3 NP类176

10.4 NP完全问题177

10.5 co-NP类182

10.6 NPI类183

10.7 四种类之间的关系184

10.8 练习184

10.9 参考注释186

第11章 计算复杂性引论187

11.1 引言187

11.2 计算模型：图灵机187

11.3 k带图灵机和时间复杂性187

11.4 离线图灵机和空间复杂性189

11.5 带压缩和线性增速191

11.6 复杂性类之间的关系191

11.7 归约196

11.8 完全性198

11.9 多项式时间层次203

11.10 练习205

11.11 参考注释208

第12章 下界209

12.1 引言209

12.2 平凡下界209

12.3 决策树模型209

12.4 代数决策树模型211

12.5 线性时间归约213

12.6 练习214

12.7 参考注释216

第五部分 克服困难性217

第13章 回溯法218

13.1 引言218

13.2 3着色问题218

13.3 8皇后问题221

13.4 一般回溯方法223

13.5 分支限界法225

13.6 练习227

13.7 参考注释228

第14章 随机算法229

14.1 引言229

14.2 Las Vegas和Monte Carlo算法229

14.3 随机化快速排序230

14.4 随机化的选择算法231

14.5 测试串的相等性232

14.6 模式匹配234

14.7 随机取样235

14.8 素数性测试237

14.9 练习241

14.10 参考注释242

第15章 近似算法244

15.1 引言244

15.2 基本定义244

15.3 差界245

15.4 相对性能界246

15.5 多项式近似方案250

15.6 完全多项式近似方案253

15.7 练习255

15.8 参考注释257

第六部分 域指定问题的迭代改进259

第16章 网络流260

16.1 引言260

16.2 预备知识260

16.3 Ford-Fulkerson方法262

16.4 最大容量增值263

16.5 最短路径增值264

16.6 Dimc算法266

16.7 MPM算法269

16.8 练习270

16.9 参考注释271

第17章 匹配272

17.1 引言272

17.2 预备知识272

17.3 网络流方法274

17.4 二分图的匈牙利树方法274

17.5 一般图中的最大匹配276

17.6 二分图的O（n2.5）算法281

17.7 练习284

17.8 参考注释286

第七部分 计算几何技术287

第18章 几何扫描288

18.1 引言288

18.2 几何预备知识289

18.3 计算线段的交点290

18.4 凸包问题292

18.5 计算点集的直径295

18.6 练习297

18.7 参考注释299

第19章 Voronoi图解300

19.1 引言300

19.2 最近点Voronoi图解300

19.3 Voronoi图解的应用304

19.4 最远点Voronoi图解306

19.5 最远点Voronoi图解的应用308

19.6 练习309

19.7 参考注释310

参考文献311