计算机算法设计和分析引论PDF电子书下载

目录 1

0 数据结构和数学基础知识 1

0.1　各种记号和公式 1

0.2　若干数学基础知识 1

对数 2

概率 3

置换 3

若干和式 4

0.3　数据结构 5

注解和参考文献 9

1 算法分析：原理和实例 10

1.1　引言 10

1.2　算法语言 12

1.3　算法分析 15

正确性 16

工作量 19

平均情况和最坏情况分析 22

占用空间 30

简单性 30

最优性 31

算法实现和程序设计 34

1.4　搜索有序表 36

最坏情况分析 39

平均性态分析 41

最优性 43

1.5　寻找表中的最大项和次大项 45

锦标赛法 46

寻找S的下界 47

寻找M和S的锦标赛法的实现 51

1.6　习题 53

时间和空间需要量 53

程序 56

注解和参考文献 56

2 整序法 58

2.1　引言 58

2.2 冒泡整序（BUBBLESORT） 59

最坏情况分析 61

平均性态 62

2.3　快速整序（QUICKSORT） 64

算法 64

最环情况 65

平均性态 66

占用空间 67

基本快速整序算法的改进 68

评论 70

2.4　键比较整序法的下界 70

2.5　堆整序（HEAPSORT） 78

从堆中删除 78

堆的构造法 80

堆的实现和堆整序算法 81

最坏情况分析 83

评论 84

2.6　谢尔整序（SHELLSORT） 85

分析 89

2.7　桶整序 90

基数整序 93

分析 97

2.8　合并已整序的表 98

最坏情况 98

n=m时的最优性 99

占用空间 99

二分合并 100

二分合并的最坏情况分析 104

合并已整序文件的下界 106

2.9　外整序 107

多遍合并整序 108

三带多遍合并 112

顺串的安排 120

顺串的构造法 122

算法2.19的分析 131

一个应用：优先队列 132

2.10　习题 132

程序 140

注解和参考文献 141

3 图和有向图 143

3.1　定义和表示 143

图和有向图的计算机表示 151

3.2　最小支撑树算法 154

实现 158

分析（时间和空间） 164

下界 164

3.3　最短路算法 165

深度优先搜索和广度优先搜索 171

3.4　遍历图和有向图 171

深度优先搜索和递归 175

深度优先搜索的实现和分析：找一个图的连通分支 178

深度优先搜索树 181

3.5　图的双连通分支 183

双分支算法 185

分析 190

推广 191

3.6　有向图的强连通分支 191

实现，时间和占用空间 198

3.7　习题 199

程序 208

注解和参考文献 209

4 字符串匹配 210

4.1　问题和一种简单解法 210

分析 212

4.2　Knuth-Morris-Pratt算法 212

利用有限自动机进行模式匹配 212

Knuth-Morris-Pratt流程图 214

KMP流程图的构造法 216

流程图构造算法的分析 220

KMP扫描算法 221

评论和推广 222

4.3　习题 223

程序 224

注解和参考文献 224

5 多项式和矩阵 225

5.1　简介 225

5.2　多项式函数的求值 225

Horner方法 226

多项式求值的下界 227

系数的预处理 228

具有系数预处理的多项式求值方法的分析 232

5.3　向量与矩阵的乘法 233

Winograd矩阵乘法 234

Winograd算法的分析 236

矩阵乘法的下界 236

Strassen矩阵乘法 237

5.4　快速傅里叶变换和卷积 240

离散傅里叶变换 241

卷积 250

分析 252

附录：复数和单位根 253

5.5 习题 255

程序 258

注解和参考文献 259

6 传递闭包，布尔矩阵和等价关系 260

6.1　二元关系的传递闭包 260

用深度优先搜索法寻找可达矩阵 261

6.2　Warshall算法 262

Warshall算法的应用 265

6.3　用矩阵运算计算传递闭包 266

Kronrod算法 269

6.4 位矩阵相乘（bit matrics）一Kronrod算法 269

分析 274

下界 274

关于传递闭包算法的评论 277

6.5 动态等价关系和UNION-FIND算法 278

实现 279

UNION-FIND程序 280

等价程序 288

应用——一个最小支撑树算法 288

其他应用 290

算法6.6的分析 290

6.6　习题 292

程序 297

注解和参考文献 297

7 “难”的（NP-完全的）问题和近似算法 299

7.1 “难”的问题：定义，例子和某些性质 299

P类问题 302

NP类问题 303

NP-完全问题 307

是什么原因使得问题成为“难”的？ 311

近似的接近程度衡量 313

7.2　近似算法 313

7.3　背包问题 315

7.4　装箱问题 318

7.5　图的着色问题 323

7.6　习题 326

注解和参考文献 329

文献目录 331

英汉名词对照表 337

索引 346