计算机算法（C++语言描述） 第2版PDF电子书下载

第1章 导论 1

1.1 什么是算法 1

1.2 算法规范 3

1.2.1 导论 3

1.2.2 递归算法 5

1.3 性能分析 8

1.3.1 空间复杂度 8

1.3.2 时间复杂度 9

1.3.3 平摊复杂度 16

1.3.4 渐进符号（O，Ω，Θ） 23

1.3.5 实际复杂度 29

1.3.6 性能测量 31

1.4 概率算法 39

1.4.1 概率论基础 39

1.4.2 随机算法：正规描述 42

1.4.3 确认重复元素 43

1.4.4 素数测试 44

1.4.5 优缺点 47

1.5 参考文献及阅读 49

第2章 数据结构基础 50

2.1 栈与队列 50

2.2 树 56

2.2.1 术语 57

2.2.2 二叉树 58

2.3 字典 60

2.3.1 二叉搜索树 61

2.4 优先队列 66

2.4.1 堆 67

2.4.2 堆排序 71

2.5 集合与不相交集合的并集 73

2.5.1 导论 73

2.5.2 求并集及查找操作 74

2.6 图 80

2.6.1 导论 80

2.6.2 定义 81

2.6.3 图的表示 83

2.7 参考文献及阅读 89

第3章 分治策略 90

3.1 一般方法 90

3.2 残缺棋盘 93

3.3 二分搜索 96

3.4 找最大值和最小值 101

3.5 合并排序 105

3.6 快速排序 111

3.6.1 性能测量 114

3.6.2 随机排序算法 115

3.7 选择 117

3.7.1 最差情况下的最优算法 120

3.7.2 Select2的实现 122

3.8 矩阵相乘 127

3.9 凸包 130

3.9.1 几种几何基本 130

3.9.2 QuickHull算法 131

3.9.3 Graham扫描 132

3.9.4 O（nlogn）的分治算法 134

3.10 参考文献及阅读 136

3.11 附加习题 137

第4章 贪心法 139

4.1 一般方法 139

4.2 集装箱装船 142

4.3 背包问题 144

4.4 树节点分裂 147

4.5 有期限的工作序列化 150

4.6 最小生成树 156

4.6.1 Prim算法 157

4.6.2 Kruskal算法 159

4.6.3 最优的随机算法（＊） 162

4.7 磁带最优存储 164

4.8 最优合并模式 168

4.9 单源最短路径 172

4.10 参考文献及阅读 177

4.11 附加习题 178

第5章 动态规划 180

5.1 一般方法 180

5.2 多段图 183

5.3 每对顶点间最短路径 187

5.4 单源最短路径：一般权重 190

5.5 最优二叉搜索树（＊） 193

5.6 串编辑 198

5.7 0/1背包 201

5.8 可靠性设计 207

5.9 旅行商问题 209

5.10 流水车间调度 211

5.11 参考文献及阅读 215

5.12 附加习题 215

第6章 基本遍历及搜索技术 219

6.1 二叉树的遍历及搜索 219

6.2 图的遍历及搜索 222

6.2.1 广度优先搜索及遍历 223

6.2.2 深度优先搜索及遍历 225

6.3 连通分支及生成树 226

6.4 双连通分支 228

6.5 参考文献及阅读 234

第7章 回溯 235

7.1 一般方法 235

7.2 八皇后问题 243

7.3 子集求和 246

7.4 图着色 248

7.5 哈密尔顿回路 251

7.6 背包问题 253

7.7 参考文献及阅读 256

7.8 附加习题 257

第8章 分支定界 260

8.1 方法 260

8.1.1 最少代价（LC）搜索 260

8.1.2 15拼图：一个例子 262

8.1.3 最少代价搜索的控制抽象 265

8.1.4 定界 266

8.1.5 FIFO分支定界 268

8.1.6 LC分支定界 268

8.2 0/1背包问题 269

8.2.1 LC分支定界解法 270

8.2.2 FIFO分支定界解法 272

8.3 旅行商问题（＊） 275

8.4 效率 280

8.5 参考文献及阅读 282

第9章 代数问题 283

9.1 一般方法 283

9.2 求值与插值 284

9.3 快速傅里叶变换（FFT） 292

9.3.1 In-place版本的快速傅里叶变换 296

9.3.2 继续思考 298

9.4 模算术 299

9.5 更快的求值和插值 305

9.6 参考文献及阅读 310

第10章 下界理论 312

10.1 比较树 312

10.1.1 有序搜索 313

10.1.2 排序 314

10.1.3 选择 316

10.2 预言及对手论证 318

10.2.1 合并 318

10.2.2 最大和次大 319

10.2.3 状态空间法 320

10.2.4 选择 321

10.3 规约求下界 322

10.3.1 找凸包 323

10.3.2 不相交集合问题 324

10.3.3 在线中位数查找 324

10.3.4 三角形矩阵相乘 325

10.3.5 下三角形矩阵求逆 326

10.3.6 计算传递闭包 327

10.4 代数问题中的技巧（＊） 329

10.5 参考文献及阅读 335

第11章 NP难及NP完全问题 336

11.1 基本概念 336

11.1.1 非确定算法 336

11.1.2 NP难及NP完全 342

11.2 Cook定理（＊） 344

11.3 NP难的图问题 350

11.3.1 团判定问题（CDP） 350

11.3.2 点覆盖判定问题（NCDP） 351

11.3.3 色数判定问题（CNDP） 352

11.3.4 有向图哈密尔顿回路问题（DHC）（＊） 353

11.3.5 旅行商判定问题（TSP） 355

11.3.6 AND/OR图判定问题（AOG） 355

11.4 NP难的调度问题 360

11.4.1 调度相同处理器 360

11.4.2 流水车间调度 362

11.4.3 作业车间调度 363

11.5 NP难的代码生成问题 364

11.5.1 有公共子表达式的代码生成 366

11.5.2 实现并行赋值指令 369

11.6 简化的NP难问题 370

11.7 参考文献及阅读 372

11.8 附加习题 373

第12章 近似算法 375

12.1 导论 375

12.2 绝对近似 377

12.2.1 平面图着色 377

12.2.2 最大程序存储问题 378

12.2.3 NP难的绝对近似 379

12.3 ε近似 380

12.3.1 调度独立任务 380

12.3.2 装箱 382

12.3.3 NP难的ε近似问题 384

12.4 多项式时间近似方案 388

12.4.1 调度独立任务 388

12.4.2 0/1背包 389

12.5 完全多项式时间近似方案 393

12.5.1 舍入 394

12.5.2 区间划分 397

12.5.3 间隔 397

12.6 概率上好的近似方案（＊） 400

12.7 参考文献及阅读 402

12.8 附加习题 402

第13章 PRAM算法 406

13.1 介绍 406

13.2 计算模型 408

13.3 基本技巧和算法 412

13.3.1 前缀计算 413

13.3.2 表排列 414

13.4 选取 420

13.4.1 使用n2个处理器选取最大元 420

13.4.2 使用n个处理器选取最大元 421

13.4.3 整数范围内的最大元 421

13.4.4 使用n2个处理进行一般性选择 423

13.4.5 工作最优的随机化选择算法（＊） 423

13.5 归并 426

13.5.1 对数时间的算法 426

13.5.2 奇偶归并 426

13.5.3 工作最优的算法 428

13.5.4 一个运行时间为O（log log m）的算法 429

13.6 排序 430

13.6.1 奇偶归并排序 430

13.6.2 一个可供选择的随机化算法 431

13.6.3 Preparata算法 431

13.6.4 Reischuk随机化算法（＊） 432

13.7 图问题 434

13.7.1 传递闭包的另一种计算方法 436

13.7.2 全点对的最小路径问题 436

13.8 凸包计算 437

13.9 下界 439

13.9.1 排序的平均运行时间下界 440

13.9.2 寻找最大元 441

13.10 参考文献及阅读 442

13.11 附加习题 443

第14章 网格算法 445

14.1 计算模型 445

14.2 数据包路由 446

14.2.1 线性数组中的数据包路由 447

14.2.2 网格上PPR问题的贪心算法 450

14.2.3 使用小队列的随机化算法 450

14.3 基本算法 452

14.3.1 广播 453

14.3.2 前缀计算 454

14.3.3 数据聚集 455

14.3.4 稀疏列举排序 456

14.4 选取 459

14.4.1 n=p′情形下的随机化算法（＊） 459

14.4.2 n>p情形下的随机化算法（＊） 460

14.4.3 n>p情形下的确定性算法 460

14.5 归并 463

14.5.1 通过秩实现线性数组上的归并 463

14.5.2 线性数组上的奇偶归并 464

14.5.3 网格上的奇偶归并 465

14.6 排序 466

14.6.1 线性数组上的排序 466

14.6.2 网格上的排序 467

14.7 图问题 470

14.7.1 n×n网格上的传递闭包算法 471

14.7.2 全点对最短路径算法 472

14.8 凸包计算 472

14.9 参考文献及阅读 475

14.10 附加习题 477

第15章 超立方算法 479

15.1 计算模型 479

15.1.1 超立方 479

15.1.2 蝴蝶网络 480

15.1.3 其他网络的嵌入 482

15.2 偏转置路由 484

15.2.1 贪心算法 484

15.2.2 随机化算法 485

15.3 基本算法 487

15.3.1 广播 487

15.3.2 前缀计算 488

15.3.3 数据聚集 489

15.3.4 稀疏列举排序 491

15.4 选取 492

15.4.1 n=p情形下的随机化算法（＊） 492

15.4.2 n>p情形下的随机化选取算法（＊） 493

15.4.3 n>p情形下的确定性算法 493

15.5 归并 495

15.5.1 奇偶归并 495

15.5.2 双调归并 496

15.6 排序 498

15.6.1 奇偶归并排序 498

15.6.2 双调排序 498

15.7 图问题 499

15.8 凸包计算 500

15.9 参考文献及阅读 501

15.10 附加习题 502