算法设计与分析

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

〖1〗算法设计与分析目录[3]〖3〗3.2合并排序算法30

3.2.1问题分析与算法设计31

3.2.2Merge函数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.60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.2Prim算法原理72

5.5.3Prim算法实现72

5.5.4Kruskal算法原理74

5.5.5Kruskal算法实现75

5.6单源最短路径问题77

5.6.1问题描述77

5.6.2Dijkstra算法原理77

5.6.3Dijkstra算法实现78

5.7本章习题80

第6章深度优先搜索/81

6.1树的搜索81

6.1.1解空间、子集树与排列树81

6.1.2深度优先搜索82

6.1.301背包问题的回溯算法84

6.1.4n皇后问题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.10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.201背包问题的0.5近似算法117

8.2.1贪心算法117

8.2.20.5近似算法118

8.30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.3Las Vegas算法132

9.3.1n皇后问题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.4Treap151

10.4.1概述151

10.4.2Treap基本操作151

10.4.3Treap的其他操作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

本书涵盖了常见计算机算法设计和分析的思路和方法，内容包括算法概论、递推与递归、分治法、动态规划法、搜索方法、近似算法、随机算法等，最后提供一些高级数据结构的介绍，以帮助实现效率更高的算法。本书重视算法思路的总结以及方法的正确性证明，以深入浅出的方式引导学生学习教材内容，既具有严谨性，又具有简明性。全书为绝大多数算法提供了可以直接验证的C/C++代码。本书适合作为高等院校计算机相关专业的教材，也可作为编程竞赛的辅导用书。

（1）涵盖了常见计算机算法设计和分析的思路和方法，内容包括算法概论、递推与递归、分治法、动态规划法、搜索方法、近似算法、随机算法等
（2）重视算法思路的总结以及方法的正确性证明，以深入浅出的方式引导学生学习教材内容，既具有严谨性，又具有简明性。
（3）为绝大多数算法提供了C/C++代码实现。