本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术。内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。

前言

教学建议

部分计算模型

章抽象的算法设计与分析........... 2

1.1 RAM 模型的引入................... 2

1.1.1 计算的基本概念................... 2

1.1.2计算模型的基本概念. . . . . . . .. .. . . . . 3

1.1.3RAM 模型........................ 3

1.1.4计算模型的选择：易用性与性........................... 5

1.2 抽象算法设计...................... 6

1.2.1 算法问题规约..................... 6

1.2.2 算法正确性证明：数学归纳法....... 7

1.3 抽象算法分析...................... 8

1.3.1 抽象算法的性能指标. . . . . . . .. .. . . . . 8

1.3.2 坏情况时间复杂度分析.......... 9

1.3.3 平均情况时间复杂度分析......... 10

1.4 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 11

第2 章从算法的视角重新审视数学的概念. . . . . . . . . . .. .. .. .. . . . . 14

2.1 数学运算背后的算法操作......... 14

2.1.1 取整. x . 和. x . . . . . . . . . . .. .. .. .. . 14

2.1.2 对数log n . . . . .. .. .. . . . . . . . . . .. .. . 14

2.1.3 阶乘n!. . . . .. .. .. .. . . . . . . . . . .. .. . 15

2.1.4 常用级数求和.f (i). . . . . . .. .. .. .. 16

2.1.5 期望E ....................... 18

2.2 函数的渐近增长率................ 19

2.3 “分治递归”求解................. 21

2.3.1 替换法. .. .. . . . . . . . . . .. .. .. .. . . . . 21

2.3.2 分治递归与递归树.. . . . . . . . . . .. .. .21

2.3.3 Master 定理. .. .. .. . . . . . . . . . .. .. .. 22

2.4 习题. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 23

第二部分从蛮力到分治

第3 章蛮力算法设计................... 31

3.1 蛮力选择与查找. . . . . . .. .. .. . . . . . . . 31

3.2 蛮力排序.. . . . . . .. .. .. .. . . . . . . . . . .. 32

3.2.1选择排序. . . .. .. .. .. . . . . . . . . . .. .. 32

3.2.2插入排序. . . .. .. .. .. . . . . . . . . . .. .. 33

3.3 习题. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 35

第4 章分治排序.. .. .. .. . . . . . .. .. .. .. . . . 37

4.1 快速排序. . . . . . . .. .. .. .. . . . . . . . . . .. 37

4.1.1插入排序的不足. .. .. . . . . . . . . . .. .. 37

4.1.2快速排序的改进. .. .. . . . . . . . . . .. .. 38

4.1.3坏情况时间复杂度分析......... 39

4.1.4基于递归方程的平均情况时间复杂度分析. . . . . . .. .. .. . . . . . . . . . . 40

4.1.5基于指标变量的平均情况时间复杂度分析. . . . . . .. .. .. . . . . . . . . . . 41

4.2 合并排序.. . . . . . .. .. .. .. . . . . . . . . . .. 43

4.3 基于比较的排序的下界. .. .. .. . . . . . 44

4.3.1决策树的引入. . . . . . .. .. .. . . . . . . . . 45

4.3.2比较排序的坏情况时间复杂度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 45

4.3.3比较排序的平均情况时间复杂度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 46

4.4 习题. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 48

第5 章线性时间选择................... 50

5.1 期望线性时间选择................ 50

5.1.1选择算法设计. . . . . . .. .. .. . . . . . . . . 50

5.1.2选择算法分析. . . . . . .. .. .. . . . . . . . . 51

5.2 坏情况线性时间选择. .. .. .. . . . . . 52

5.2.1选择算法设计. . . . . . .. .. .. . . . . . . . . 52

5.2.2选择算法分析. .. . . . . . . . . . .. .. . . . . 53

5.3 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 54

第6 章对数时间查找................... 57

6.1 折半查找.. .. . . . . . . . .. .. .. .. . . . . . . . 57

6.1.1经典折半查找. .. . . . . . . . .. .. .. . . . . 57

6.1.2查找峰值. . . . . . . .. .. .. . . . . . . . . . .. 58

6.1.3计算√N ........................ 59

6.2 平衡二叉搜索树. . . . . . . . .. .. .. . . . . . 59

6.2.1二叉搜索树及其平衡性........... 59

6.2.2红黑树的定义. .. . . . . . . . . . .. .. . . . . 60

6.2.3红黑树的平衡性. .. .. .. .. . . . . . . . . . 62

6.3 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 62

第7 章分治算法设计要素. . . . . . . . . . .. .. .65

7.1 分治算法的关键特征. . . . . . . .. .. .. . 65

7.2 计算逆序对的个数................ 66

7.2.1依托于合并排序的逆序对计数.. .. . 66

7.2.2原地的逆序对计数.. .. . . . . . . . . . .. .67

7.3 整数乘法.. .. . . . . . . . .. .. .. .. . . . . . . . 68

7.3.1简单分治. . . . . . . .. .. .. . . . . . . . . . .. 69

7.3.2更精细的分治.