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