第1章 引言 1
1.1 算法的定义 1
1.1.1 算法的属性 2
1.1.2 效率的定义 3
1.2 算法设计与分析举例 5
1.2.1 寻找局部高点-1D 5
1.2.2 图书管理 8
1.3 小结 10
课后习题 11
第2章 渐进分析与Python计算模型 13
2.1 引言 13
2.2 计算模型 13
2.3 算法的渐进分析 14
2.4 Python计算模型 17
2.4.1 控制流语句 17
2.4.2 数据结构 19
2.5 算法分析实例 21
2.5.1 求最大值 22
2.5.2 二分搜索 22
2.5.3 子集和问题 23
2.6 小结 24
课后习题 25
第3章 问题求解与代码优化 27
3.1 引言 27
3.2 文档比较 27
3.2.1 问题提出 27
3.2.2 算法设计 28
3.2.3 算法优化 31
3.3 拼写矫正 33
3.3.1 问题提出 33
3.3.2 算法设计 33
3.4 稳定匹配问题 36
3.4.1 问题提出 36
3.4.2 算法设计 38
3.5 小结 40
课后习题 41
第4章 递归算法与递归函数 42
4.1 引言 42
4.2 递归的组成结构 42
4.2.1 如何筹集巨款 42
4.2.2 上线与下线 44
4.3 递归算法的执行 45
4.3.1 跟踪函数的执行 47
4.4 利用递归算法求解问题 51
4.4.1 回文判断 51
4.4.2 全排列 53
4.4.3 汉诺塔问题 54
4.4.4 雪花曲线 57
4.5 递归函数的求解 58
4.5.1 替换法 59
4.5.2 主分析法 60
4.6 小结 62
课后习题 63
第5章 排序与树结构 64
5.1 引言 64
5.2 递归与排序 65
5.2.1 选择排序 65
5.2.2 插入排序 67
5.2.3 合并排序 69
5.3 二叉搜索树 72
5.3.1 BST的实现 74
5.3.2 插入新结点 75
5.3.3 BST上查找 77
5.3.4 二叉树修剪 78
5.4 堆 81
5.4.1 堆化操作 81
5.4.2 构造堆 83
5.4.3 堆排序 85
5.4.4 合并k个有序序列 86
5.5 小结 87
课后习题 88
第6章 分治算法 90
6.1 引言 90
6.2 股票的买卖 91
6.2.1 问题描述 91
6.2.2 算法设计 91
6.3 统计逆序 94
6.3.1 问题描述 94
6.3.2 算法设计 94
6.4 空间最小距离点对 97
6.4.1 问题描述 97
6.4.2 算法设计 98
6.5 寻找第k小的数 103
6.5.1 问题描述 103
6.5.2 算法设计 103
6.6 大整数乘法 107
6.6.1 问题描述 107
6.6.2 算法设计 108
6.7 小结 109
课后习题 109
第7章 图搜索算法 111
7.1 引言 111
7.2 图搜索的应用 112
7.3 图的表示 113
7.4 宽度优先搜索 114
7.4.1 宽度优先搜索算法 114
7.4.2 BFS算法分析 117
7.4.3 BFS算法应用举例 117
7.5 深度优先搜索 121
7.5.1 深度优先搜索算法 121
7.5.2 DFS算法分析 124
7.5.3 DFS应用举例 124
7.6 小结 126
课后习题 126
第8章 贪心算法 128
8.1 引言 128
8.2 硬币找零 128
8.2.1 问题描述 128
8.2.2 问题求解 129
8.2.3 最优解证明 130
8.3 间隔任务规划 130
8.3.1 问题描述 130
8.3.2 问题求解 131
8.3.3 最优解证明 133
8.4 单源最矩路径问题 134
8.4.1 Dijkstra问题 135
8.4.2 算法的正确性 136
8.4.3 算法的性能优化 137
8.5 最小生成树 139
8.5.1 Prim算法 140
8.5.2 算法实现 142
8.6 小结 145
课后习题 145
第9章 动态规划算法 147
9.1 引言 147
9.2 再遇斐波那契数 147
9.3 一维动态规划 151
9.3.1 拾捡硬币 152
9.3.2 连续子序列和的最大值 155
9.3.3 疯狂的8 157
9.3.4 文本排版 161
9.3.5 完全信息的21点 165
9.4 二维动态规划 169
9.4.1 矩阵的括号 169
9.4.2 字符串编辑距离 173
9.4.3 0-1背包问题 176
9.5 小结 179
课后习题 180
第10章 最大流算法应用 182
101 引言 182
10.2 最大流算法 182
10.2.1 Ford-Fulkerson算法 186
10.2.2 Edmond-Karp算法 187
10.3 最大流算法的应用 189
10.3.1 二向图最大匹配问题 189
10.3.2 文件传输中的不重合边问题 191
10.4 小结 193
课后习题 193
第11章 随机算法 195
11.1 引言 195
11.2 矩阵乘积结果验证 196
11.3 快速排序 198
11.3.1 根据支点数划分输入序列 199
11.3.2 选择支点数 200
11.3.3 随机快速排序 202
11.4 选择第k小的数 203
11.5 寻找最小割边 206
11.6 小结 209
课后习题 209
第12章 算法复杂度 210
12.1 引言 210
12.2 问题的分类 210
12.2.1 易解与难解 210
12.2.2 无解的问题 211
12.2.3 难解问题的证明 213
12.3 NPC问题应用 214
12.3.1 决策问题 214
12.3.2 问题的化约 215
12.3.3 NP问题 215
12.3.4 NPC问题 216
12.4 P等于NP吗 218
12.5 小结 219
课后习题 219
索引 221
代码列表 222
参考文献 226