算法导论 第2版PDF电子书下载

第一部分 基础知识 1

引言 1

第1章 算法在计算中的作用 3

1.1 算法 3

1.2 作为一种技术的算法 6

第2章 算法入门 9

2.1 插入排序 9

2.2 算法分析 12

2.3 算法设计 16

2.3.1 分治法 16

2.3.2 分治法分析 20

第3章 函数的增长 26

3.1 渐近记号 26

3.2 标准记号和常用函数 31

第4章 递归式 38

4.1 代换法 38

4.2 递归树方法 40

4.3 主方法 43

4.4 主定理的证明 45

4.4.1 取正合幂时的证明 45

4.4.2 上取整函数和下取整函数 48

第5章 概率分析和随机算法 54

5.1 雇用问题 54

5.2 指示器随机变量 56

5.3 随机算法 58

5.4 概率分析和指示器随机变量的进一步使用 62

5.4.1 生日悖论 62

5.4.2 球与盒子 64

5.4.3 序列 64

5.4.4 在线雇用问题 66

第二部分 排序和顺序统计学 71

引言 71

第6章 堆排序 73

6.1 堆 73

6.2 保持堆的性质 74

6.3 建堆 76

6.4 堆排序算法 78

6.5 优先级队列 80

第7章 快速排序 85

7.1 快速排序的描述 85

7.2 快速排序的性能 88

7.3 快速排序的随机化版本 90

7.4 快速排序分析 91

7.4.1 最坏情况分析 91

7.4.2 期望的运行时间 92

第8章 线性时间排序 97

8.1 排序算法时间的下界 97

8.2 计数排序 98

8.3 基数排序 100

8.4 桶排序 102

第9章 中位数和顺序统计学 108

9.1 最小值和最大值 108

9.2 以期望线性时间做选择 109

9.3 最坏情况线性时间的选择 112

第三部分 数据结构 117

引言 117

第10章 基本数据结构 119

10.1 栈和队列 119

10.2 链表 121

10.3 指针和对象的实现 124

10.4 有根树的表示 127

第11章 散列表 132

11.1 直接寻址表 132

11.2 散列表 133

11.3 散列函数 137

11.3.1 除法散列法 138

11.3.2 乘法散列法 138

11.3.3 全域散列 139

11.4 开放寻址法 142

11.5 完全散列 146

第12章 二叉查找树 151

12.1 二叉查找树 151

12.2 查询二叉查找树 153

12.3 插入和删除 155

12.4 随机构造的二叉查找树 158

第13章 红黑树 163

13.1 红黑树的性质 163

13.2 旋转 165

13.3 插入 167

13.4 删除 172

第14章 数据结构的扩张 181

14.1 动态顺序统计 181

14.2 如何扩张数据结构 184

14.3 区间树 186

第四部分 高级设计和分析技术 191

导论 191

第15章 动态规划 192

15.1 装配线调度 192

15.2 矩阵链乘法 197

15.3 动态规划基础 202

15.4 最长公共子序列 208

15.5 最优二叉查找树 212

第16章 贪心算法 222

16.1 活动选择问题 222

16.2 贪心策略的基本内容 228

16.3 赫夫曼编码 231

16.4 贪心法的理论基础 236

16.5 一个任务调度问题 239

第17章 平摊分析 244

17.1 聚集分析 244

17.2 记账方法 247

17.3 势能方法 249

17.4 动态表 251

17.4.1 表扩张 251

17.4.2 表扩张和收缩 253

第五部分 高级数据结构 261

概述 261

第18章 B树 263

18.1 B树的定义 265

18.2 对B树的基本操作 267

18.3 从B树中删除关键字 272

第19章 二项堆 277

19.1 二项树与二项堆 278

19.1.1 二项树 278

19.1.2 二项堆 279

19.2 对二项堆的操作 281

第20章 斐波那契堆 291

20.1 斐波那契堆的结构 291

20.2 可合并堆的操作 293

20.3 减小一个关键字与删除一个结点 299

20.4 最大度数的界 302

第21章 用于不相交集合的数据结构 305

21.1 不相交集合上的操作 305

21.2 不相交集合的链表表示 307

21.3 不相交集合森林 310

21.4 带路径压缩的按秩合并的分析 312

第六部分 图算法 321

引言 321

第22章 图的基本算法 322

22.1 图的表示 322

22.2 广度优先搜索 324

22.3 深度优先搜索 330

22.4 拓扑排序 336

22.5 强连通分支 338

第23章 最小生成树 344

23.1 最小生成树的形成 345

23.2 Kruskal算法和Prim算法 348

第24章 单源最短路径 357

24.1 Bellman-Ford算法 362

24.2 有向无回路图中的单源最短路径 364

24.3 Dijkstra算法 366

24.4 差分约束与最短路径 370

24.5 最短路径性质的证明 373

第25章 每对顶点间的最短路径 381

25.1 最短路径与矩阵乘法 382

25.2 Floyd-Warshall算法 386

25.3 稀疏图上的Johnson算法 391

第26章 最大流 396

26.1 流网络 396

26.2 Ford-Fulkerson方法 400

26.3 最大二分匹配 408

26.4 压入与重标记算法 411

26.5 重标记与前移算法 419

第七部分 算法研究问题选编 431

引言 431

第27章 排序网络 433

27.1 比较网络 433

27.2 0-1原理 436

27.3 双调排序网络 438

27.4 合并网络 440

27.5 排序网络 442

第28章 矩阵运算 446

28.1 矩阵的性质 446

28.2 矩阵乘法的Strassen算法 451

28.3 求解线性方程组 455

28.4 矩阵求逆 464

28.5 对称正定矩阵与最小二乘逼近 467

第29章 线性规划 473

29.1 标准型和松弛型 477

29.2 将问题表达为线性规划 482

29.3 单纯形算法 485

29.4 对偶性 495

29.5 初始基本可行解 498

第30章 多项式与快速傅里叶变换 506

30.1 多项式的表示 507

30.2 DFT与FFT 511

30.3 有效的FFT实现 516

第31章 有关数论的算法 522

31.1 初等数论概念 522

31.2 最大公约数 526

31.3 模运算 529

31.4 求解模线性方程 533

31.5 中国余数定理 535

31.6 元素的幂 538

31.7 RSA公钥加密系统 540

31.8 素数的测试 544

31.9 整数的因子分解 550

第32章 字符串匹配 557

32.1 朴素的字符串匹配算法 558

32.2 Rabin-Karp算法 560

32.3 利用有限自动机进行字符串匹配 563

32.4 Knuth-Morris-Pratt算法 568

第33章 计算几何学 575

33.1 线段的性质 575

33.2 确定任意一对线段是否相交 580

33.3 寻找凸包 584

33.4 寻找最近点对 591

第34章 NP完全性 597

34.1 多项式时间 600

34.2 多项式时间的验证 605

34.3 NP完全性与可归约性 608

34.4 NP完全性的证明 615

34.5 NP完全问题 620

34.5.1 团问题 620

34.5.2 顶点覆盖问题 622

34.5.3 哈密顿回路问题 623

34.5.4 旅行商问题 626

34.5.5 子集和问题 627

第35章 近似算法 633

35.1 顶点覆盖问题 634

35.2 旅行商问题 636

35.2.1 满足三角不等式的旅行商问题 636

35.2.2 一般旅行商问题 638

35.3 集合覆盖问题 640

35.4 随机化和线性规划 643

35.5 子集和问题 646

第八部分 附录：数学基础知识 653

引言 653

A 求和 654

A.1 求和公式及其性质 654

A.2 确定求和时间的界 656

B 集合等离散数学结构 661

B.1 集合 661

B.2 关系 664

B.3 函数 665

B.4 图 667

B.5 树 670

B.5.1 自由树 670

B.5.2 有根树和有序树 671

B.5.3 二叉树与位置树 672

C 计数和概率 676

C.1 计数 676

C.2 概率 679

C.3 离散随机变量 683

C.4 几何分布与二项分布 686

C.5 二项分布的尾 689

参考文献 694

索引 711