算法设计与分析PDF电子书下载

第1章 算法引论 1

1.1 算法 1

1.2 算法描述 2

1.2.1 算法描述约定 2

1.2.2 一个简单问题的求解过程 5

1.3 算法分析基础 6

1.3.1 算法分析的评估体系 6

1.3.2 算法的时间复杂度 6

1.3.3 算法的空间复杂度 9

1.3.4 NP-完全问题 9

1.4 基本数据结构 10

1.4.1 栈和队列 10

1.4.2 树 14

1.4.3 图 19

1.5 迭代法 22

1.5.1 递推法 22

1.5.2 倒推法 22

1.5.3 迭代法解方程 23

1.6 递归和消除递归 25

1.6.1 递归 25

1.6.2 消除递归 26

本章小结 27

习题1 27

第2章 排序算法 29

2.1 排序 29

2.1.1 排序问题 29

2.1.2 冒泡排序 30

2.1.3 交换排序 31

2.1.4 选择排序 33

2.1.5 插入排序 34

2.2 堆排序 35

2.2.1 堆 35

2.2.2 建堆 35

2.2.3 堆排序算法 38

2.2.4 堆排序的应用 40

2.3 快速排序 41

2.3.1 快速排序的描述 41

2.3.2 快速排序的性能 42

2.3.3 随机化的快速排序算法 42

2.3.4 快速排序分析 43

2.4 线性时间排序 44

2.4.1 排序算法的下界 44

2.4.2 计数排序 45

2.4.3 基数排序 46

2.4.4 桶排序 47

2.5 中数排序 49

2.5.1 最大和最小元素 49

2.5.2 一般选择问题 49

本章小结 51

习题2 52

第3章 分治法 55

3.1 一般算法 55

3.2 二分检索 56

3.3 找最大值和最小值 59

3.4 归并分类 62

3.4.1 基本方法 62

3.4.2 改进的归并分类算法 66

3.5 快速分类 67

3.5.1 快速分类算法 67

3.5.2 快速分类分析 68

3.6 选择问题 70

3.6.1 选择问题算法 70

3.6.2 SELECT2的实现 70

本章小结 72

习题3 72

第4章 图的搜索算法 74

4.1 图的基本概念 74

4.1.1 图的定义 74

4.1.2 图的基本术语 75

4.2 图的检索与遍历 77

4.2.1 广度优先检索与遍历 77

4.2.2 深度优先检索与遍历 80

4.3 回溯法 82

4.3.1 回溯法的一般方法 82

4.3.2 回溯算法的抽象描述 85

4.3.3 n-皇后问题 86

4.3.4 子集和数问题 88

4.3.5 0/1背包问题 90

4.3.6 图的m-着色问题 98

4.3.7 哈密顿环 101

4.3.8 连续邮资问题 103

4.3.9 回溯法的效率估计 107

本章小结 111

习题4 111

第5章 贪心算法 114

5.1 算法概述 114

5.1.1 贪心选择性质 114

5.1.2 最优子结构性质 114

5.1.3 活动安排问题 115

5.2 背包问题 116

5.3 带有限期的作业排序 118

5.3.1 带有限期的作业排序算法 118

5.3.2 改进的带有限期的作业排序算法 121

5.4 最优归并模式 124

5.5 哈夫曼编码 126

5.5.1 前缀码 126

5.5.2 哈夫曼编码 127

5.6 最小生成树 129

5.6.1 Prim算法 130

5.6.2 Kruskal算法 133

5.7 单源点最短路径 136

本章小结 140

习题5 141

第6章 动态规划算法 145

6.1 一般方法 145

6.2 多段图 150

6.3 每对结点之间的最短路径 152

6.4 最优二分检索树 155

6.5 0/1背包问题 161

6.5.1 0/1背包问题的实例分析 161

6.5.2 DKP的实现 165

6.5.3 过程DKNAP的分析 167

6.6 可靠性设计 168

6.7 货郎担问题 170

6.8 流水线调度问题 172

本章小结 176

习题6 176

第7章 分支限界法 179

7.1 一般方法 179

7.1.1 FIFO和LIFO-检索 179

7.1.2 LC-检索 180

7.1.3 LC-检索的抽象化描述 184

7.1.4 分支限界法解最优化问题 185

7.2 0/1背包问题 190

7.2.1 LC-分支限界求解 191

7.2.2 FIFO-分支限界求解 195

7.3 货郎担问题 197

7.4 效率分析 204

本章小结 205

习题7 205

第8章 并行算法 208

8.1 并行计算机及并行模型 208

8.1.1 并行计算机 208

8.1.2 并行计算模型 211

8.1.3 并行计算机网络 212

8.1.4 并行算法的一般术语 214

8.2 SIMD共享存储模型的并行算法 215

8.2.1 播送算法 215

8.2.2 求和算法 216

8.2.3 并行k-选择算法 217

8.2.4 并行桶排序算法 218

8.2.5 有序表搜索并行算法 222

8.3 SIMD互联网络模型的并行算法 224

8.3.1 网孔上的随机序列搜索算法 224

8.3.2 树机上的矩阵和向量乘法 226

8.3.3 一维线性阵列上的奇偶转置排序算法 228

8.3.4 树机上求最小值算法 228

8.3.5 树机上的连通分量算法 232

8.4 MIMD共享存储模型的并行算法 234

8.4.1 异步枚举排序算法 234

8.4.2 单源点最短路径并行算法 235

8.4.3 最小生成树并行算法 238

8.4.4 Gauss-Seidel算法 240

8.4.5 牛顿求根并行算法 242

8.5 MIMD异步通信模型的并行算法 243

8.5.1 快速排序并行算法 243

8.5.2 二维网孔上的矩阵转置并行算法 244

8.5.3 矩阵并行分块乘法算法 246

8.5.4 分布式矩阵求逆的并行算法 247

8.5.5 分布式高斯消去并行算法 250

本章小结 255

习题8 255

第9章 NP-完全问题 257

9.1 计算模型 257

9.1.1 有限自动机 257

9.1.2 下推自动机 258

9.1.3 图灵机 259

9.2 P类与NP类问题 262

9.2.1 多项式时间界（Polynomial time） 262

9.2.2 P类问题 264

9.2.3 NP类问题 264

9.3 NP-完全问题 265

9.3.1 判定NP-完全问题的关键概念 265

9.3.2 NP-完全性 267

9.3.3 Cook定理 268

9.4 典型的NP-完全问题 272

9.4.1 NP-完全性的证明方法 272

9.4.2 典型的NP-完全问题 273

9.4.3 NP-完全问题的计算机实现 282

本章小结 283

习题9 285

第10章 近似算法 287

10.1 近似算法的性能 287

10.2 启发式算法 288

10.2.1 图着色问题 289

10.2.2 旅行商问题 290

10.3 任务安排的近似算法 291

10.4 覆盖问题的近似算法 295

10.4.1 顶点覆盖问题的近似算法 295

10.4.2 集合覆盖问题的近似算法 297

10.5 旅行售货员问题近似算法 299

10.5.1 具有三角不等式的旅行售货员问题 299

10.5.2 一般旅行售货员问题 302

10.6 背包问题 303

10.7 子集合问题的近似算法 305

10.7.1 解子集合问题的指数时间算法 305

10.7.2 子集合问题的完全多项式时间近似格式 306

本章小结 308

习题10 308

第11章 概率算法 311

11.1 概率算法概述 311

11.2 伪随机数 312

11.3 数值概率算法 313

11.3.1 用随机投点法计算π值 313

11.3.2 计算定积分 314

11.3.3 解非线性方程组 316

11.4 Sherwood算法 318

11.4.1 线性时间选择算法 319

11.4.2 搜索有序表 320

11.4.3 跳跃表 324

11.5 Las Vegas算法 329

11.5.1 n后问题 329

11.5.2 整数因子分解 333

11.6 Monte Carlo算法 335

11.6.1 Monte Carlo算法的基本思想 335

11.6.2 主元素问题 337

11.6.3 素数性测试 338

本章小结 339

习题11 340

主要参考文献 344