第一部分 基础知识

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

1.1算法

1.2作为一种技术的算法

思考题

本章注记

第2章 算法基础

2.1插入排序

2.2分析算法

2.3设计算法

2.3.1分治法

2.3.2分析分治算法

思考题

本章注记

第3章 函数的增长

3.1渐近记号

3.2标准记号与常用函数

思考题

本章注记

第4章 分治策略

4.1最大子数组问题

4.2矩阵乘法的Strassen算法

4.3用代入法求解递归式

4.4用递归树方法求解递归式

4.5用主方法求解递归式

4.6证明主定理

4.6.1对b的幂证明主定理

4.6.2向下取整和向上取整

思考题

本章注记

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

5.1雇用问题

5.2指示器随机变量

5.3随机算法

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

5.4.1生日悖论

5.4.2球与箱子

5.4.3特征序列

5.4.4在线雇用问题

思考题

本章注记

第二部分 排序和顺序统计量

第6章 堆排序

6.1堆

6.2维护堆的性质

6.3建堆

6.4堆排序算法

6.5优先队列

思考题

本章注记

第7章 快速排序

7.1快速排序的描述

7.2快速排序的性能

7.3快速排序的随机化版本

7.4快速排序分析

7.4.1最坏情况分析

7.4.2期望运行时间

思考题

本章注记

第8章 线性时间排序

8.1排序算法的下界

8.2计数排序

8.3基数排序

8.4桶排序

思考题

本章注记

第9章 中位数和顺序统计量

9.1最小值和最大值

9.2期望为线性时间的选择算法

9.3最坏情况为线性时间的选择算法

思考题

本章注记

第三部分 数据结构

第10章 基本数据结构

10.1栈和队列

10.2链表

10.3指针和对象的实现

10.4有根树的表示

思考题

本章注记

第11章 散列表

11.1直接寻址表

11.2散列表

11.3散列函数

11.3.1除法散列法

11.3.2乘法散列法

11.3.3全域散列法

11.4开放寻址法

11.5完全散列

思考题

本章注记

第12章 二叉搜索树

12.1什么是二叉搜索树

12.2查询二叉搜索树

12.3插入和删除

12.4随机构建二叉搜索树

思考题

本章注记

第13章 红黑树

13.1红黑树的性质

13.2旋转

13.3插入

13.4删除

思考题

本章注记

第14章 数据结构的扩张

14.1动态顺序统计

14.2如何扩张数据结构

14.3区间树

思考题

本章注记

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

第15章 动态规划

15.1钢条切割

15.2矩阵链乘法

15.3动态规划原理

15.4最长公共子序列

15.5最优二叉搜索树

思考题

本章注记

第16章 贪心算法

16.1活动选择问题

16.2贪心算法原理

16.3赫夫曼编码

16.4拟阵和贪心算法

16.5用拟阵求解任务调度问题

思考题

本章注记

第17章 摊还分析

17.1聚合分析

17.2核算法

17.3势能法

17.4动态表

17.4.1表扩张

17.4.2表扩张和收缩

思考题

本章注记

第五部分 高级数据结构

第18章 B树

18.1 B树的定义

18.2 B树上的基本操作

18.3从B树中删除关键字

思考题

本章注记

第19章 斐波那契堆

19.1斐波那契堆结构

19.2可合并堆操作

19.3关键字减值和删除一个结点

19.4最大度数的界

思考题

本章注记

第20章van EmdeBoas树

20.1基本方法

20.2递归结构

20.2.1原型van Emde Boas结构

20.2.2原型van Emde Boas结构上的操作

20.3 van Emde Boas树及其操作

20.3.1 van Emde Boas树

20.3.2 van Emde Boas树的操作

思考题

本章注记

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

21.1不相交集合的操作

21.2不相交集合的链表表示

21.3不相交集合森林

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

思考题

本章注记

第六部分 图算法

第22章 基本的图算法

22.1图的表示

22.2广度优先搜索

22.3深度优先搜索

22.4拓扑排序

22.5强连通分量

思考题

本章注记

第23章 最小生成树

23.1最小生成树的形成

23.2 Kruskal算法和Prim算法

思考题

本章注记

第24章 单源最短路径

24.1 Bellman-Ford算法

24.2有向无环图中的单源最短路径问题

24.3 Dijkstra算法

24.4差分约束和最短路径

24.5最短路径性质的证明

思考题

本章注记

第25章 所有结点对的最短路径问题

25.1最短路径和矩阵乘法

25.2 Floyd-Warshall算法

25.3用于稀疏图的Johnson算法

思考题

本章注记

第26章 最大流

26.1流网络

26.2 Ford-Fulkerson方法

26.3最大二分匹配

26.4推送-重贴标签算法

26.5前置重贴标签算法

思考题

本章注记

第七部分 算法问题选编

第27章 多线程算法

27.1动态多线程基础

27.2多线程矩阵乘法

27.3多线程归并排序

思考题

本章注记

第28章 矩阵运算

28.1求解线性方程组

28.2矩阵求逆

28.3对称正定矩阵和最小二乘逼近

思考题

本章注记

第29章 线性规划

29.1标准型和松弛型

29.2将问题表达为线性规划

29.3单纯形算法

29.4对偶性

29.5初始基本可行解

思考题

本章注记

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

30.1多项式的表示

30.2 DFT与FFT

30.3高效FFT实现

思考题

本章注记

第31章 数论算法

31.1基础数论概念

31.2最大公约数

31.3模运算

31.4求解模线性方程

31.5中国余数定理

31.6元素的幂

31.7 RSA公钥加密系统

31.8素数的测试

31.9整数的因子分解

思考题

本章注记

第32章 字符串匹配

32.1朴素字符串匹配算法

32.2 Rabin-Karp算法

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

32.4 Knuth-Morris-Pratt算法

思考题

本章注记

第33章 计算几何学

33.1线段的性质

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

33.3寻找凸包

33.4寻找最近点对

思考题

本章注记

第34章NP完全性

34.1多项式时间

34.2多项式时间的验证

34.3 NP完全性与可归约性

34.4 NP完全性的证明

34.5 NP完全问题

34.5.1团问题

34.5.2顶点覆盖问题

34.5.3哈密顿回路问题

34.5.4旅行商问题

34.5.5子集和问题

思考题

本章注记

第35章 近似算法

35.1顶点覆盖问题

35.2旅行商问题

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

35.2.2一般旅行商问题

35.3集合覆盖问题

35.4随机化和线性规划

35.5子集和问题

思考题

本章注记

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

附录A求和

A.1求和公式及其性质

A.2确定求和时间的界

思考题

附录注记

附录B 集合等离散数学内容

B.1集合

B.2关系

B.3函数

B.4图

B.5树

B.5.1自由树

B.5.2有根树和有序树

B.5.3二叉树和位置树

思考题

附录注记

附录C计数与概率

C.1计数

C.2概率

C.3离散随机变量

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

C.5二项分布的尾部

思考题

附录注记

附录D矩阵

D.1矩阵与矩阵运算

D.2矩阵的基本性质

思考题

附录注记

参考文献

索引