第1章 算法与性能 1
1.1 算法的概念 1
1.2 算法的表达 1
1.2.1 自然语言 1
1.2.2 结构化图形工具 2
1.2.3 计算机高级语言 3
1.3 算法的评价 3
1.3.1 算法的正确性 4
1.3.2 算法的空间复杂性 5
1.3.3 算法的时间复杂性 5
1.4 最差时间复杂性和平均时间复杂性 6
1.5 函数的阶与渐进性分析 7
1.5.1 复杂性函数的阶 7
1.5.2 函数的渐进性阶的比较 8
1.5.3 函数的渐进性阶的运算 8
1.5.4 函数的渐进性表示与函数集合 9
1.6 本章习题 9
第2章 递推与递归 10
2.1 递推关系与递推算法 10
2.2 递归函数 21
2.3 递归函数的执行过程 22
2.4 递归函数的时间复杂性与递归树 24
2.5 估计递归函数的复杂度的主方法 26
2.6 本章习题 27
第3章 分治法 29
3.1 二分搜索算法 29
3.1.1 问题分析与算法设计 29
3.1.2 时间复杂性分析 30
3.2 合并排序算法 30
3.2.1 问题分析与算法设计 31
3.2.2 Merge函数 31
3.2.3 时间复杂性分析 32
3.3 快速排序算法 32
3.3.1 固定主元的快速排序 32
3.3.2 随机选主元的快速排序 34
3.4 搜索第k元 35
3.4.1 平均时间为线性 36
3.4.2 最差时间为线性 37
3.5 最近点对 39
3.5.1 一维空间中的最近点对 39
3.5.2 二维空间中的最近点对 40
3.6 本章习题 44
第4章 动态规划 45
4.1 递归方法中的重复计算 45
4.2 最长公共子序列 47
4.2.1 问题描述 47
4.2.2 递推关系分析 47
4.2.3 算法实现 48
4.3 最大子段和 49
4.3.1 问题描述 49
4.3.2 递推分析 49
4.3.3 算法实现 50
4.4 矩阵连乘问题 51
4.4.1 问题描述 51
4.4.2 递推分析 52
4.4.3 算法实现 52
4.5 数据压缩问题 53
4.5.1 问题描述 53
4.5.2 递推分析 54
4.5.3 算法实现 55
4.6 0-1背包问题 56
4.6.1 问题描述 56
4.6.2 递推分析 56
4.6.3 算法描述 56
4.7 消费和储蓄问题 57
4.7.1 问题描述 57
4.7.2 递推分析 58
4.7.3 算法实现 58
4.8 最优二叉搜索树问题 59
4.8.1 问题描述 59
4.8.2 递推分析 60
4.8.3 算法实现 60
4.9 本章习题 61
第5章 贪心算法 63
5.1 活动安排问题 64
5.1.1 问题描述 64
5.1.2 问题分析 64
5.1.3 算法实现 64
5.2 服务调度问题 65
5.2.1 问题描述 65
5.2.2 问题分析 66
5.2.3 算法实现 66
5.3 最迟时间限制服务调度问题 67
5.3.1 问题描述 67
5.3.2 问题分析 67
5.3.3 算法实现 69
5.4 ε-背包问题 70
5.4.1 问题描述 70
5.4.2 问题分析 70
5.4.3 算法实现 70
5.5 最小生成树问题 72
5.5.1 问题描述 72
5.5.2 Prim算法原理 72
5.5.3 Prim算法实现 72
5.5.4 Kruskal算法原理 74
5.5.5 Kruskal算法实现 75
5.6 单源最短路径问题 77
5.6.1 问题描述 77
5.6.2 Dijkstra算法原理 77
5.6.3 Dijkstra算法实现 78
5.7 本章习题 80
第6章 深度优先搜索 81
6.1 树的搜索 81
6.1.1 解空间、子集树与排列树 81
6.1.2 深度优先搜索 82
6.1.3 0-1背包问题的回溯算法 84
6.1.4 n皇后问题 86
6.1.5 旅行推销员问题 88
6.1.6 最大团问题 90
6.1.7 图着色问题 91
6.1.8 连续邮资问题 92
6.2 图的搜索 94
6.2.1 狼羊过河问题 95
6.2.2 分油问题 98
6.3 本章习题 100
第7章 宽度优先搜索 102
7.1 宽度优先搜索一般形式 102
7.1.1 基本算法 102
7.1.2 算法性能 103
7.1.3 算法设计要素 104
7.2 树的分支定界法 104
7.2.1 0-1背包问题 104
7.2.2 旅行推销员问题 107
7.3 图的分支定界法 109
7.3.1 狼羊过河问题 109
7.3.2 分油问题 112
7.4 本章习题 115
第8章 近似算法 116
8.1 近似算法的概念 116
8.2 0-1背包问题的0.5 -近似算法 117
8.2.1 贪心算法 117
8.2.2 0.5 -近似算法 118
8.3 0-1背包问题的（1-ε）-近似算法 118
8.3.1 一种动态规划算法 118
8.3.2 （1-ε）-近似算法 120
8.4 旅行推销员问题的2-近似算法 121
8.5 本章习题 124
第9章 随机算法 126
9.1 数值型随机算法 126
9.1.1 数值积分随机算法 126
9.1.2 随机计数器 127
9.2 蒙特卡洛算法 128
9.2.1 矩阵乘法验证 128
9.2.2 质数检测 129
9.3 Las Vegas算法 132
9.3.1 n皇后问题 132
9.3.2 通用散列算法 134
9.4 本章习题 135
第10章 高级数据结构（一） 136
10.1 线段树 136
10.1.1 线段树的应用背景 136
10.1.2 线段树的结构 136
10.1.3 线段树的性质 137
10.1.4 线段树的基本存储结构 138
10.1.5 线段树的基本操作 138
10.1.6 线段树的应用举例 140
10.2 树状数组 142
10.2.1 树状数组的应用背景 142
10.2.2 树状数组的定义 142
10.2.3 树状数组的实现 143
10.2.4 树状数组的应用 143
10.3 伸展树 144
10.3.1 伸展树的应用背景 144
10.3.2 伸展树的定义及特点 144
10.3.3 伸展树的主要操作 145
10.4 Treap 151
10.4.1 概述 151
10.4.2 Treap基本操作 151
10.4.3 Treap的其他操作 153
10.4.4 总结 155
10.5 本章习题 156
第11章 高级数据结构（二） 157
11.1 块状链表 157
11.1.1 块状链表基本思想 157
11.1.2 块状链表基本操作 157
11.1.3 块状链表的应用 162
11.2 后缀树 163
11.2.1 模式匹配问题 163
11.2.2 后缀树简介 163
11.2.3 后缀树定义 163
11.2.4 后缀树的构建 164
11.2.5 后缀树的应用 166
11.3 树链剖分 168
11.3.1 树链剖分的思想和性质 168
11.3.2 树链剖分的实现及应用 169
11.4 本章习题 177
参考文献 178