计算机算法（C++语言描述） 第2版PDF|Epub|txt|kindle电子书版本网盘下载

计算机算法（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