《电子计算机算法设计与分析》

目录1

第一章 算法和初等数据结构1

1.1 算法及其复杂度1

1.2 初等数据结构和递归16

1.3 图和树25

1.4 算法分析技术42

第二章 分类算法的复杂度分析52

2.1 分类的概念52

2.2 基数分类54

2.3 比较分类及其下界63

2.4 快速分类71

2.5 堆分类77

2.6 shell分类81

第三章 算法设计技术（一）——分治法85

3.1 概述85

3.2 找第k个最小元素90

3.3 矩阵乘法及其应用95

3.4 快速傅里叶变换102

3.5 SCHONHAGE—STRASSEN整数乘算法117

第四章 算法设计技术（二）128

4.1 贪心法128

4.2 动态规划142

4.3 回溯法153

4.4 分枝限界法165

4.5 局部搜索法178

5.1 集合的表示和基本运算188

第五章 集合运算188

5.2 二叉搜索树197

5.3 最优二叉搜索树202

5.4 UNION—FIND算法207

5.5 UNION—FIND问题的树结构212

5.6 平衡树228

5.7 字典和优先队列230

5.8 可连接队列234

第六章 关于图的算法241

6.1 最小耗费生成树241

6.2 双连通性246

6.3 有向图的深度优先搜索255

6.4 强连通性257

6.5 找寻路径和最短路径问题265

6.6 路径问题与矩阵乘法271

6.7 单源问题278

第七章 串匹配286

7.1 概述286

7.2 Knuth—Morris—Pratt算法288

7.3 Boyer—Moore算法294

7.4 Rabin—Karp算法296

第八章 NP完全问题299

8.1 图灵机299

8.2 不确定图灵机307

8.3 P与NP类318

8.4 COOK定理—可满足性问题的NP完全性328

8.5 证明NP完全性的几种技术333

8.6 NP完全问题的近似算法344