算法设计技巧与分析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