《计算机算法：设计和分析引论》求取 ⇩

目录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

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

最优性？90

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

2.10　习题132

一个应用：优先队列132

程序140

注解和参考文献141

3　图和有向图143

3.1　定义和表示143

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

3.2　最小支撑树算法154

实现158

分析（时间和空间）164

下界164

3.3　最短路算法165

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

3.4　遍历图和有向图171

深度优先搜索和递归175

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

分支178

深度优先搜索树181

3.5　图的双连通分支183

双分支算法185

分析190

3.6　有向图的强连通分支191

推广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

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

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

Kronrod算法269

分析274

下界274

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

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

实现279

UNION-FIND程序280

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

等价程序288

算法6.6的分析290

其他应用290

6.6 习题292

程序297

注解和参考文献297

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

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

P类问题302

NP类问题303

NP-完全问题307

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

7.2　近似算法313

近似的接近程度衡量313

7.3　背包问题315

7.4　装箱问题318

7.5　图的着色问题323

7.6　习题326

注解和参考文献329

文献目录331

英汉名词对照表337

索引346