目录

第 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 

目录 IX 

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 

目录 XI 

9 5小结                                                                                                     179 课后习题                                                                                                      180

第 10章最大流算法应用                                                                                  182 

10 1引言                                                                                                   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