vii

.............................................................................. 1
1

....................................... 7
1.1 理解问题 ...........................................................................................................7
1.2 简单解法 ...........................................................................................................8

1.3 高明做法 ...........................................................................................................9
1.3.1 贪心算法.................................................................................................9
1.3.2 分治算法...............................................................................................10
1.3.3 并行算法............................................................................................... 11
1.3.4 近似算法............................................................................................... 11
1.3.5 融会贯通...............................................................................................12
1.4 总结 ................................................................................................................13
1.5 参考文献 .........................................................................................................13
2

............................................... 14
2.1 问题样本的规模 .............................................................................................14
2.2 函数的增长率 .................................................................................................15
2.3 最好

2.3.1 最坏情况...............................................................................................20
2.3.2 平均情况...............................................................................................21
viii

2.3.3 最好情况 ...............................................................................................22
2.3.4 上下界 ..................................................................................................22
2.4 性能指标 .........................................................................................................23
2.4.1 常数级算法的性能 ................................................................................23
2.4.2 对数级算法的性能 ................................................................................24
2.4.3 次线性级算法
O
(
n
d
)(
d
<1) 的性能 ........................................................26
2.4.4 线性算法的性能 ...................................................................................26
2.4.5 线性对数算法的性能 ............................................................................ 29
2.4.6 二次方的算法性能 ................................................................................30
2.4.7 性能不明显的计算 ................................................................................31
2.4.8 指数级算法性能 ...................................................................................34
2.4.9 渐进增长小结 .......................................................................................34
2.5 基准测试 .........................................................................................................34
2.6 参考文献 .........................................................................................................36
3

.......................................................... 37
3.1 算法模板的格式 .............................................................................................37
3.1.1 名称 ...................................................................................................... 37
3.1.2 输入 / 输出 ............................................................................................38
3.1.3 使用环境...............................................................................................38
3.1.4 决方案...............................................................................................38
3.1.5 算法分析...............................................................................................38
3.1.6 衍生算法...............................................................................................38
3.2 伪代码模板的格式 ..........................................................................................38

3.3 实验评估的格式 .............................................................................................39
3.4 浮点计算 .........................................................................................................39
3.4.1 性能 ...................................................................................................... 40
3.4.2 舍入误差...............................................................................................40
3.4.3 浮点值的比较 .......................................................................................41
3.4.4 特殊值 ..................................................................................................42
3.5 算法举例 .........................................................................................................43

ix
3.5.1 算法名称和摘要 ...................................................................................43
3.5.2 输入 / 输出 ............................................................................................43
3.5.3 使用环境...............................................................................................43
Graham 扫描算法小结 ...................................................................................44
3.5.4 决方案...............................................................................................44
3.5.5 算法分析...............................................................................................46
3.6 常用方法 .........................................................................................................47
3.6.1 贪心 ......................................................................................................47
3.6.2 分治 ......................................................................................................47
3.6.3 动态规划...............................................................................................48
3.7 参考文献 .........................................................................................................53
4

......................................................... 54
4.1 概述 ................................................................................................................54
4.1.1 术语 ......................................................................................................54
4.1.2 表示方式...............................................................................................54
4.1.3 可比较的元素 .......................................................................................56
4.1.4 稳定排序...............................................................................................56
4.1.5 选择排序算法的标准 ............................................................................ 57
4.2 移位排序 .........................................................................................................58
4.2.1 插入排序...............................................................................................58

4.2.2 使用环境...............................................................................................59
4.2.3 决方案...............................................................................................59
4.2.4 算法分析...............................................................................................60
4.3 选择排序 .........................................................................................................61
4.4 堆排序 ............................................................................................................62

4.4.1 使用环境...............................................................................................65
4.4.2 决方案...............................................................................................65
4.4.3 算法分析...............................................................................................67
4.4.4 衍生算法...............................................................................................67
x

4.5 基于分区的排序算法 ......................................................................................68

4.5.1 使用环境...............................................................................................70
4.5.2 决方案...............................................................................................71
4.5.3 算法分析...............................................................................................72
4.5.4 衍生算法...............................................................................................72
4.6 不基于比较的排序算法 ..................................................................................74
4.7 桶排序 ...........................................................................................................74

4.7.1 决方案...............................................................................................76
4.7.2 算法分析...............................................................................................78
4.7.3 衍生算法...............................................................................................79
4.8 使用额外存储空间的排序算法 .......................................................................80
4.8.1 归并排序...............................................................................................80
4.8.2 输入 / 输出 ............................................................................................81

4.8.3 决方案...............................................................................................82
4.8.4 算法分析...............................................................................................83
4.8.5 衍生算法...............................................................................................83
4.9 字符串基准测试结果 ......................................................................................84
4.10 分析技术 ....................................................................................................... 86
4.11 参考文献 ....................................................................................................... 88
5

.......................................................... 89
5.1 顺序搜索 .........................................................................................................90
5.1.1 输入 / 输出 ............................................................................................90

5.1.2 使用环境...............................................................................................91
5.1.3 决方案...............................................................................................91
5.1.4 算法分析...............................................................................................92
5.2 二分搜索 .........................................................................................................93
5.2.1 输入 / 输出 ............................................................................................93

xi
5.2.2 使用环境...............................................................................................93

5.2.3 决方案...............................................................................................94
5.2.4 算法分析...............................................................................................95
5.2.5 衍生算法...............................................................................................96
5.3 散列搜索 .........................................................................................................97
5.3.1 输入 / 输出 ............................................................................................98
5.3.2 使用环境...............................................................................................99

5.3.3 决方案 ............................................................................................ 102
5.3.4 算法分析............................................................................................. 103
5.3.5 衍生算法............................................................................................. 106
5.4 布隆过滤器 ................................................................................................... 111

5.4.1 输入 / 输出 .......................................................................................... 112
5.4.2 使用环境............................................................................................. 112
5.4.3 决方案............................................................................................. 112
5.4.4 算法分析............................................................................................. 113
5.5 二叉搜索树 ................................................................................................... 114
5.5.1 输入 / 输出 .......................................................................................... 115
5.5.2 使用环境............................................................................................. 115
5.5.3 决方案............................................................................................. 116
5.5.4 算法分析............................................................................................. 125
5.5.5 衍生算法............................................................................................. 126
5.6 参考文献 ....................................................................................................... 126
6

........................................................... 127
6.1 .................................................................................................................. 127
6.2 深度优先搜索 ............................................................................................... 131

6.2.1 输入 / 输出 ..........................................................................................134
6.2.2 使用环境............................................................................................. 134

Get 算法技术手册（原书第2 版） now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.