计算机算法 C++版 C++PDF电子书下载

目录 1

出版者的话 1

专家指导委员会 1

译者序 1

前言 1

第1章 导论 1

1.1　什么是算法 1

1.2　算法规范 3

1.2.1　引言 3

1.2.2　递归算法 4

2.4.1　堆 5

1.3.1　空间复杂度 7

1.3　性能分析 7

1.3.2　时间复杂度 8

1.3.3　渐近符号（O、Ω、？） 14

1.3.4　实际复杂度 19

1.3.5　性能度量 21

1.4　随机算法 28

1.4.1　概率论基础 28

1.4.2　随机算法：非形式化的描述 30

1.4.3　识别重复元素 31

1.4.4　素数测试 33

1.4.5　优点与缺点 35

1.5　参考文献和读物 36

第2章 基本数据结构 39

2.1　栈和队列 39

2.2　树 44

2.2.1　术语 44

2.2.2　二叉树 45

2.3　字典 47

2.3.1　二叉查找树 48

2.3.2　代价分摊 52

2.4　优先队列 53

2.4.2　堆排序 58

2.5　集合和不相交集合的并 59

2.5.1　概述 59

2.5.2　并和查找操作 60

2.6　图 66

2.6.1　概述 66

2.6.2　定义 66

2.6.3　图的表示方法 69

2.7　参考文献和读物 73

第3章　分治算法 75

3.1　一般方法 75

3.2　二叉查找 77

3.3　查找最大值和最小值 82

3.4　归并排序 85

3.5　快速排序 90

3.5.1　性能度量 93

3.5.2　随机排序算法 94

3.6　选择 96

3.6.1　最坏情况下的最优算法 99

3.6.2　Select2的实现 101

3.7 Strassen矩阵乘法 104

3.8　凸包 107

3.8.1　几种原始几何方法 108

3.8.2 QuickHull算法 108

3.8.3 Graham扫描算法 109

3.8.4　一个O（nlogn）的分治算法 111

3.10　附加习题 113

3.9　参考文献和读物 113

第4章　贪心算法 115

4.1　一般方法 115

4.2　背包问题 116

4.3　树节点分割 118

4.4　带有期限的作业顺序问题 121

4.5　最小代价生成树 126

4.5.1 Prim算法 127

4.5.2　Kruskal算法 129

4.5.3　一个最优随机算法（＊） 131

4.6　磁带的最优存储 133

4.7　最优归并模式 136

4.8　单源最短路径 140

4.9　参考文献和读物 144

4.10　附加习题 145

第5章　动态规划 147

5.1　一般方法 147

5.2　多部图 149

5.3　每一对顶点之间的最短路径 153

5.4　单源最短路径：普通权值 156

5.5　最优二叉查找树（＊） 158

5.6　串编辑 163

5.7 0/1背包 165

5.8　可靠性设计 170

5.9　旅行商问题 172

5.10　流水作业调度 174

5.11　参考文献和读物 177

5.12　附加习题 178

第6章 基本的查找和遍历技术 181

6.1　二叉树算法 181

6.2　图算法 184

6.2.1　广度优先搜索和遍历 184

6.2.2　深度优先搜索和遍历 186

6.3　连通分支和生成树 187

6.4　双连通分支和DFS算法 189

6.5　参考文献和读物 193

第7章 回溯 195

7.1　一般方法 195

7.2 8皇后问题 202

7.3　子集求和问题 204

7.4　图的着色 206

7.5　哈密顿回路 209

7.6　背包问题 210

7.7　参考文献和读物 213

7.8　附加习题 214

第8章 分支限界法 217

8.1　一般方法 217

8.1.1　最小代价查找 218

8.1.2　15拼板：一个例子 219

8.1.3 LC查找的控制抽象 221

8.1.4　限界 223

8.1.5 FIFO分支限界法 224

8.1.6　LC分支限界法 225

8.2 0/1背包问题 226

8.2.1 LC分支限界法求解 226

8.2.2 FIFO分支限界法求解 228

8.3　旅行商问题（＊） 230

8.4　效率因素 235

8.5　参考文献和读物 237

9.1　一般方法 239

第9章　代数问题 239

9.2　计算和插值 240

9.3　快速傅里叶变换 246

9.3.1 FFT的原地版本 250

9.3.2 一些保留问题 252

9.4　模运算 252

9.5　更快的计算和插值 257

9.6　参考文献和读物 262

第10章　下界理论 263

10.1　比较树 263

10.1.1　有序查找 264

10.1.2　排序 264

10.1.3　选择 268

10.2　喻示和对立论 269

10.2.1　归并 269

10.2.2　最大和次大 270

10.2.3　状态空间方法 271

10.2.4　选择 272

10.3　通过规约求下界 274

10.3.1　寻找凸包 274

10.3.2　不相交集合问题 275

10.3.3　即时中值查找 275

10.3.4　三角矩阵相乘 276

10.3.5　下三角矩阵求逆 277

10.3.6　计算传递闭包 278

10.4　解决代数问题的技术（＊） 280

10.5　参考文献和读物 286

第11章 NP难与NP完全问题 289

11.1　基本概念 289

11.1.1　非确定性算法 289

11.1.2　NP难和NP完全类 294

11.2　Cook定理（＊） 296

11.3　NP难的图问题 301

11.3.1　团判定问题 301

11.3.2　节点覆盖判定问题 302

11.3.3　色数判定问题 303

11.3.4　有向哈密顿回路（＊） 304

11.3.5　旅行商判定问题 306

11.3.6　与／或图判定问题 306

11.4　NP难的调度问题 310

11.4.1　调度相同的处理器 310

11.4.2　流水作业调度 311

11.4.3　作业安排调度 312

11.5　NP难的代码生成问题 314

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

11.5.2　实现并行赋值指令 318

11.6　一些简化的NP难问题 319

11.7　参考文献和读物 321

11.8　附加习题 322

第12章 近似算法 325

12.1　概述 325

12.2.2　最多程序存储问题 327

12.2　绝对近似 327

12.2.1　平面图着色 327

12.2.3　NP难的绝对近似 328

12.3　ε近似 330

12.3.1　独立任务的调度 330

12.3.2　装箱问题 332

12.3.3　NP难的ε近似问题 333

12.4　多项式时间近似方案 337

12.4.1　独立任务的调度 337

12.4.2　 0/1背包 338

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

12.5.1　舍入法 342

12.5.2　区间划分法 345

12.5.3　分割法 346

12.6　概率上的好算法（＊） 349

12.7　参考文献和读物 350

12.8　附加习题 351

13.1　概述 355

第13章 PRAM算法 355

13.2　计算模型 357

13.3　基本技术和算法 361

13.3.1　前缀计算 361

13.3.2　表排序 362

13.4　选择 367

13.4.1　使用n2个处理器选择最大值 367

13.4.2　使用n个处理器选择最大值 368

13.4.3　在整数中选择最大值 369

13.4.4　使用n2个处理器的一般选择问题 370

13.4.5　一个工作最优的随机算法（＊） 370

13.5　归并 372

13.5.1　对数时间算法 373

13.5.2　奇偶归并 373

13.5.3　工作最优的算法 374

13.5.4　 O（log logm）时间算法 375

13.6　排序 376

13.6.1　奇偶归并排序 377

13.6.2　随机选择算法 377

13.6.3　 Preparata算法 378

13.6.4 　Reischuk随机算法（＊） 379

13.7　图问题 381

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

13.7.2　每一对顶点之间的最短路径 383

13.8　计算凸包 383

13.9　下界 385

13.9.1　平均情况下排序的下界 386

13.9.2　寻找最大值 387

13.10　参考文献和读物 388

13.11　附加习题 389

第14章 网格算法 391

14.1　计算模型 391

14.2　分组路由 392

14.2.1　线性阵列中的分组路由 393

14.2.2　网格上PPR的贪心算法 394

14.2.3　具有小队列的随机算法 395

14.3　基本算法 397

14.3.1　广播 398

14.3.2　前缀计算 398

14.3.3　数据集中 400

14.3.4　稀疏枚举排序 401

14.4　选择 403

14.4.1 n=p（＊）时的随机算法 403

14.4.2 n>p（＊）时的随机选择 404

14.4.3　n>p时的确定性算法 404

14.5　归并 407

14.5.1　在线性阵列上的顺序号归并 407

14.5.2　线性阵列上的奇偶归并 408

14.5.3　在网格上的奇偶归并 408

14.6　排序 409

14.6.2　在网格上的排序 410

14.6.1　在线性阵列上的排序 410

14.7　图问题 413

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

14.7.2　每一对顶点之间的最短路径 415

14.8　计算凸包 416

14.9　参考文献和读物 418

14.10　附加习题 420

第15章 超立方体算法 423

15.1　计算模型 423

15.1.1　超立方体 423

15.1.2　蝶形网络 424

15.1.3　其他网络的嵌入 425

15.2 PPR路由 427

15.2.1　贪心算法 427

15.2.2　随机算法 428

15.3.1　广播 430

15.3.2　前缀计算 430

15.3　基本算法 430

15.3.3　数据集中 431

15.3.4　稀疏枚举排序 433

15.4　选择 434

15.4.1 n=p（＊）时的随机算法 434

15.4.2 n>p（＊）时的随机选择 435

15.4.3 n>p时的确定性算法 435

15.5.1　奇偶归并 437

15.5　归并 437

15.5.2　双调谐归并 438

15.6　排序　 439

15.6.1　奇偶归并排序 439

15.6.2　双调谐排序 439

15.7　图问题 440

15.8　计算凸包 441

15.9　参考文献和读物 442

15.10　附加习题 443

索引 445