算法设计技巧与分析PDF|Epub|txt|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.5阶乘和二项式系数45

2.4底函数和顶函数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.1引言90

5.2两个简单的例子90

第5章 归纳法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.1引言174

第10章 NP完全问题174

10.2P类176

10.3NP类176

10.4NP完全问题177

10.5co-NP类182

10.6NP类183

10.7四种类之间的关系184

10.8练习184

10.9参考注释186

11.2计算模型：图灵机187

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

11.1引言187

第11章 计算复杂性引论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.3决策树模型209

12.2平凡下界209

12.1引言209

第12章 下界209

12.4代数决策树模型211

12.5线性时间归约213

12.6练习214

12.7参考注释216

第五部分 克服困难性217

第13章 回溯法218

13.1引言218

13.23着色问题218

13.38皇后问题221

13.4一般回溯方法223

13.5分支限界法225

13.6练习227

13.7参考注释228

第14章 随机算法229

14.1引言229

14.2Las 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.3Ford～Fulkerson方法262

16.4最大容量增值263

16.5最短路径增值264

16.6Dinic算法266

16.7MPM算法269

16.8练习270

16.9参考注释271

17.1引言272

17.2预备知识272

第17章 匹配272

17.3网络流方法274

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

17.5一般图中的最大匹配276

17.6二分图的0（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.3Voronoi图解的应用304

19.4最远点Voronoi图解306

19.5最远点Voronoi图解的应用308

19.6练习309

19.7参考注释310

参考文献311