算法设计与应用PDF电子书下载

第1章 算法分析 1

1.1分析算法 2

1.1.1伪代码 2

1.1.2随机存取机模型 4

1.1.3基本操作数目的计算 4

1.1.4递归算法的分析 6

1.1.5渐近表示法 6

1.1.6渐近表示法的重要性 10

1.2相关数学知识复习 11

1.2.1求和 11

1.2.2对数和幂 12

1.2.3简单的证明技术 13

1.2.4概率基础 16

1.3算法分析案例 18

1.3.1最大子数组问题的第一个解 18

1.3.2一种改进的求最大子数组算法 19

1.3.3线性时间的最大子数组算法 20

1.4平摊分析 21

1.4.1平摊技术 22

1.4.2对一个可扩展数组实现的分析 24

1.5练习 26

本章注记 31

第一部分 数据结构 34

第2章 基本数据结构 34

2.1栈和队列 35

2.1.1栈 35

2.1.2队列 37

2.2列表 38

2.2.1基于索引的列表 39

2.2.2链表 40

2.3树 44

2.3.1树的定义 45

2.3.2树的遍历 46

2.3.3二叉树 49

2.3.4表示树的数据结构 53

2.4练习 55

本章注记 58

第3章 二叉搜索树 59

3.1搜索和更新 60

3.1.1二叉搜索树的定义 62

3.1.2二叉搜索树中的搜索 62

3.1.3二叉搜索树中的插入 64

3.1.4二叉搜索树中的删除 64

3.1.5二叉搜索树的性能 65

3.2范围查询 66

3.3基于索引的搜索 68

3.4随机构造二叉搜索树 70

3.5练习 72

本章注记 75

第4章 平衡二叉搜索树 76

4.1秩和旋转 77

4.2 AVL树 79

4.3红黑树 82

4.4弱AVL树 85

4.5伸展树 91

4.6练习 97

本章注记 101

第5章 优先队列和堆 102

5.1优先队列 103

5.2 PQ排序、选择排序和插入排序 103

5.2.1选择排序 104

5.2.2插入排序 106

5.3堆 107

5.3.1基于数组结构的二叉树 109

5.3.2堆中的插入 110

5.3.3堆中的删除 112

5.4堆排序 114

5.5扩展优先队列 118

5.6练习 119

本章注记 122

第6章 散列表 123

6.1映射 124

6.1.1映射的定义 124

6.1.2查找表 125

6.2散列函数 126

6.2.1分量求和 127

6.2.2多项式求值函数 127

6.2.3基于表格的散列 128

6.2.4取模 128

6.2.5随机线性和多项式函数 129

6.3碰撞处理与再散列 129

6.3.1拉链法 129

6.3.2开放寻址法 130

6.3.3线性探测 131

6.3.4平方探测 133

6.3.5双重散列 133

6.3.6再散列 134

6.4布谷鸟散列 134

6.5通用散列 138

6.6练习 140

本章注记 142

第7章 并查集结构 143

7.1并查集及其应用 144

7.1.1连通分支 144

7.1.2迷宫建筑和渗透理论 145

7.2基于列表的实现 146

7.3基于树的实现 148

7.4练习 153

本章注记 155

第二部分 排序和选择 158

第8章 归并排序和快速排序 158

8.1归并排序 159

8.1.1分而治之 159

8.1.2归并排序和递推方程 162

8.2快速排序 163

8.2.1随机快速排序 165

8.2.2原地快速排序 166

8.3基于比较的排序的下界 168

8.4练习 169

本章注记 172

第9章 快速排序和选择 173

9.1桶排序和基数排序 174

9.1.1桶排序 174

9.1.2基数排序 175

9.2选择 176

9.2.1随机快速选择 176

9.2.2确定性选择 178

9.3加权中位数 179

9.4练习 181

本章注记 183

第三部分 基本技术 186

第10章 贪心法 186

10.1分份背包问题 187

10.2任务调度 189

10.3文本压缩和哈夫曼编码 191

10.4练习 195

本章注记 197

第11章 分治法 198

11.1递推与主定理 199

11.2整数乘法 203

11.3矩阵乘法 204

11.4极大点集问题 205

11.5练习 206

本章注记 209

第12章 动态规划 210

12.1矩阵连乘 211

12.2通用技术 213

12.3望远镜调度 213

12.4博弈策略 216

12.4.1硬币行 216

12.4.2概率博弈策略与逆向归纳法 217

12.5最长公共子序列问题 219

12.5.1问题定义 219

12.5.2应用动态规划解LCS问题 219

12.6 0-1背包问题 221

12.7练习 223

本章注记 227

第13章 图及遍历 228

13.1图的术语和表示方法 228

13.1.1图的一些术语 229

13.1.2图的操作 231

13.1.3表示图的数据结构 232

13.2深度优先搜索 235

13.3广度优先搜索 237

13.4有向图 239

13.4.1遍历有向图 240

13.4.2传递闭包 242

13.4.3有向DFS和垃圾回收 244

13.4.4有向无环图 246

13.5双连通分量 249

13.6练习 252

本章注记 255

第四部分 图算法 258

第14章 最短路径 258

14.1单源最短路径 258

14.2 Dijkstra算法 259

14.3 Bellman-Ford算法 264

14.4有向无环图中的最短路径 266

14.5所有顶点对之间的最短路径 268

14.5.1动态规划最短路径算法 268

14.5.2通过矩阵乘法计算最短路径 269

14.6练习 272

本章注记 275

第15章 最小生成树 276

15.1最小生成树的性质 276

15.2 Kruskal算法 279

15.3 Prim-Jarnik算法 282

15.4 Baruvka算法 285

15.5练习 286

本章注记 288

第16章 网络流和匹配 290

16.1流与割 290

16.1.1割 292

16.1.2剩余容量和增流路径 293

16.2最大流算法 295

16.2.1 Ford-Fulkerson算法 295

16.2.2 Edmonds-Karp算法 297

16.3最大二分图匹配 300

16.4棒球赛的淘汰 301

16.5最低成本流 302

16.6练习 307

本章注记 309

第五部分 计算困难问题 312

第17章 NP完全性 312

17.1 P和NP 313

17.1.1定义复杂类P和NP 314

17.1.2一些有趣的NP问题 316

17.2 NP完全性 318

17.2.1多项式时间归约和NP难度 318

17.2.2 Cook-Levin定理 318

17.2.3如何证明一个问题是NP完全问题 319

17.3合取范式可满足问题和3可满足问题 321

17.4顶点覆盖、团和集合覆盖 324

17.5子集和与背包问题 326

17.6哈密顿回路和TSP 328

17.7练习 330

本章注记 333

第18章 近似算法 334

18.1几何旅行商问题 336

18.1.1 Metric-TSP的一个2近似算法 336

18.1.2 Christofides近似算法 337

18.2覆盖问题的近似 338

18.2.1顶点覆盖的2近似算法 338

18.2.2集合覆盖的对数近似 339

18.3多项式时间近似方法 340

18.4回溯和分支定界 342

18.4.1回溯法 342

19.4.2分支定界法 344

18.5练习 344

本章注记 346

第六部分 高级主题 350

第19章 随机算法 350

19.1随机排列的生成 351

19.2稳定婚姻和优惠券收集 352

19.2.1优惠券收集问题分析 353

19.2.2稳定婚姻问题 354

19.3最小割 356

19.3.1收缩边 357

19.3.2计算最小割 357

19.3.3更快的算法 359

19.4寻找素数 360

19.5切尔诺夫界 364

19.5.1马尔可夫不等式 364

19.5.2示性随机变量之和 364

19.5.3几何型随机变量之和 366

19.6跳跃表 367

19.6.1搜索 368

19.6.2更新操作 368

19.6.3跳跃表的概率分析 370

19.7练习 371

本章注记 374

第20章 B树和外部存储器 376

20.1外部存储器 377

20.2 （2，4）树和B树 379

20.2.1多叉搜索树 379

20.2.2（2，4）树 381

20.2.3 （a，b）树和B树 386

20.3外部存储器排序 389

20.4在线缓存算法 391

20.5练习 396

本章注记 398

第21章 多维搜索 399

21.1范围树 400

21.2优先搜索树 403

21.2.1构造优先搜索树 403

21.2.2在优先搜索树中搜索 404

21.2.3优先范围树 405

21.3四叉树和k-d树 406

21.3.1四叉树 406

21.3.2 k-d树 407

21.4练习 409

本章注记 411

第22章 计算几何 412

22.1几何对象上的操作 413

22.2凸壳 416

22.2.1礼品包装算法 417

22.2.2 Graham扫描算法 419

22.3线段相交 421

22.4求最近点对 423

22.5练习 425

本章注记 428

第23章 字符串算法 429

23.1字符串操作 430

23.2 Boyer-Moore算法 431

23.3 Knuth-Morris-Pratt算法 435

23.4基于散列的词典匹配 437

23.5字典树 441

23.5.1标准字典树 441

23.5.2压缩字典树 443

23.5.3后缀字典树 445

23.5.4搜索引擎 447

23.6练习 448

本章注记 450

第24章 密码学 451

24.1最大公约数 452

24.1.1一些初等数论知识 452

24.1.2欧几里得GCD算法 453

24.2模运算 454

24.2.1模幂运算 456

24.2.2模乘法逆 458

24.3加密操作 459

24.4 RSA密码系统 461

24.5 El Gamal密码系统 463

24.6练习 464

本章注记 465

第25章 快速傅里叶变换 466

25.1卷积 467

25.2原始单位根 468

25.3离散傅里叶变换 469

25.4快速傅里叶变换算法 471

25.5练习 475

本章注记 478

第26章 线性规划 479

26.1定义问题 480

26.2单纯形法 483

26.2.1松弛型 484

26.2.2扩展的例子 485

26.2.3单纯形算法 487

26.3对偶 488

26.4线性规划的应用 491

26.5练习 492

本章注记 497

附录A一些有用的数学知识 498

参考文献 501