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

第一部分　基础工具 2

第1章　算法分析 2

1.1　算法的分析方法学 2

1.1.1　伪代码 4

1.1.2　随机存取机（RAM）模型 5

1.1.3　统计基本操作的数量 6

1.1.4　递归算法分析 7

1.2　渐近符号 8

1.2.1　大O符号 8

1.2.2 与大“O”相关的渐近符号 10

1.2.3　渐近表示的重要性 12

1.3　数学概览 13

1.3.1 求和 13

1.3.2　对数和指数 14

1.3.3　简单证明技术 16

1.3.4　概率基础 18

1.4　算法分析案例研究 20

1.4.1 二次时间前缀平均值算法 21

1.4.2　线性时间前缀平均值算法 22

1.5 平摊方法 22

1.5.1 平摊技术 23

1.5.2　扩展数组实现分析 25

1.6　实验 28

1.6.1　实验组织 28

1.6.2　数据分析和可视化 29

1.7　习题 31

基础题 31

创新题 33

程序设计 35

1.8　本章注记 36

2.1.1 栈 37

2.1　栈和队列 37

第2章　基本数据结构 37

2.1.2 队列 40

2.2 向量、表和序列 43

2.2.1 向量 43

2.2.2　表 44

2.2.3 序列 48

2.3 树 49

2.3.1　树抽象数据类型 51

2.3.2　树的遍历 52

2.3.3　二叉树 55

2.3.4　表示树的数据结构 60

2.4　优先队列和堆 62

2.4.1　优先队列抽象数据类型 63

2.4.2　PQ排序、选择排序和插入排序 64

2.4.3 堆数据结构 66

2.4.4　堆排序 71

2.5　字典与散列表 76

2.5.1 无序字典ADT 76

2.5.2　散列表 77

2.5.3　散列函数 78

2.5.5　冲突处理模式 80

2.5.4　压缩映射 80

2.5.6 通用散列 83

2.6　Java示例：堆 85

2.7 习题 87

基础题 87

创新题 89

程序设计 91

2.8　本章注记 91

第3章　查找树和跳跃表 93

3.1　有序字典和二叉查找树 94

3.1.1　有序表 94

3.1.3　二叉查找树中的查找 96

3.1.2　二叉查找树 96

3.1.4　二叉查找树中的插入 98

3.1.5　二叉查找树中的删除 99

3.1.6　二叉查找树的性能 100

3.2　AVL树 101

3.2.1　更新操作 102

3.2.2　性能 105

3.3　深度有界查找树 106

3.3.1　多路查找树 106

3.3.2　（2,4）树 108

3.3.3 红黑树 113

3.4　伸展树 123

3.4.1　伸展 123

3.4.2　伸展过程的平摊分析 128

3.5　跳跃表 131

3.5.1 查找 132

3.5.2　更新操作 133

3.5.3　跳跃表的概率分析 135

3.6　Java示例：AVL树和红黑树 136

3.6.1　AVL树的Java实现 138

3.6.2　红黑树的Java实现 141

基础题 143

3.7　习题 143

创新题 144

程序设计 145

3.8　本章注记 146

第4章　排序、集合和选择 147

4.1 归并排序 147

4.1.1 分治法 148

4.1.2　归并排序和递归方程 151

4.2　集合抽象数据类型 152

4.2.1　简单的集合实现 152

4.2.2　具有union-find操作的划分 153

4.2.3　基于树的划分实现 154

4.3　快速排序 159

4.4　基于比较的排序下界 162

4.5　桶排序和基数排序 163

4.5.1 桶排序 163

4.5.2　基数排序 164

4.6　比较排序算法 165

4.7 选择 166

4.7.1　剪枝一查找法 166

4.7.2　随机化快速选择 166

4.7.3　随机化快速选择分析 167

4.8　Java示例：原位快速排序 168

4.9 习题 170

基础题 170

创新题 171

程序设计 172

4.10　本章注记 173

第5章　基本技术 174

5.1 贪心法 174

5.1.1 背包问题 175

5.1.2　任务调度 176

5.2.1　分治递归方程 177

5.2　分治法 177

5.2.2　整数相乘 182

5.2.3　矩阵相乘 183

5.3　动态规划 185

5.3.1 矩阵链乘 185

5.3.2　一般技术 187

5.3.3　0-1背包问题 188

5.4 习题 190

基础题 190

创新题 191

程序设计 191

5.5　本章注记 192

第二部分　图算法 194

第6章　图 194

6.1 图抽象数据类型 194

6.2　图的数据结构 199

6.2.1　边表结构 199

6.2.2　邻接表结构 201

6.2.3　邻接矩阵结构 203

6.3 图的遍历 204

6.3.1　深度优先查找 204

6.3.2　双连通分量 206

6.3.3　广度优先查找 211

6.4　有向图 213

6.4.1　遍历有向图 214

6.4.2　传递闭包 216

6.4.3　DFS和垃圾收集 218

6.4.4　有向无环图 219

6.5　Java示例：深度优先查找 222

6.5.1　修饰模式 222

6.5.2　DFS引擎 223

6.5.3　模板方法设计模式 224

基础题 227

6.6　习题 227

创新题 228

程序设计 229

6.7　本章注记 229

第7章　加权图 230

7.1　单源点最短路径 231

7.1.1　Dijkstra算法 231

7.1.2　Bellman-Ford最短路径算法 236

7.1.3　有向无环图中的最短路径 238

7.2　所有顶点对之间的最短路径 240

7.2.1　动态规划最短路径算法 240

7.2.2　利用矩阵相乘计算最短路径 241

7.3　最小生成树 244

7.3.1　Kruskal算法 245

7.3.2　Prim-Jarník算法 249

7.3.3　Bar？vka算法 251

7.3.4　MST算法比较 253

7.4　Java示例：Dijkstra算法 253

7.5 习题 256

基础题 256

创新题 256

程序设计 257

7.6　本章注记 258

第8章　网络流和匹配 259

8.1　流和割 260

8.1.1　流网络 260

8.1.2　割 261

8.2　最大流 262

8.2.1　剩余容量和增大路径 262

8.2.2　Ford-Fulkerson算法 264

8.2.3 Ford-Fulkerson算法分析 266

8.2.4　Edmonds-Karp算法 267

8.3　最大二分匹配 269

8.4　最小代价流 270

8.4.1　增大回路 271

8.4.2　连续最短路径 272

8.4.3　修改权值 273

8.5　Java示例：最小代价流 276

8.6　习题 281

基础题 281

创新题 281

程序设计 282

8.7　本章注记 282

第9章　文本处理 284

9.1 串和模式匹配算法 284

第三部分　因特网算法 284

9.1.1 串操作 285

9.1.2　蛮力模式匹配 286

9.1.3　Boyer-Moore算法 287

9.1.4　Knuth-Morris-Pratt算法 289

9.2　trie 292

9.2.1 标准trie 292

9.2.2　压缩trie 294

9.2.3 后缀trie 295

9.3 文本压缩 298

9.2.4　搜索引擎 298

9.3.1　赫夫曼编码算法 299

9.3.2　修正贪心法 300

9.4　文本相似性测试 301

9.4.1　最长公共子序列问题 301

9.4.2 应用动态规划求解LCS问题 301

9.5 习题 303

基础题 303

创新题 304

程序设计 305

9.6　本章注记 305

10.1　与数有关的基本算法 306

第10章　数论和密码学 306

10.1.1　基本数论的一些事实 307

10.1.2　欧几里得GCD算法 308

10.1.3　模运算 310

10.1.4　模指数运算 313

10.1.5　模乘法逆元 315

10.1.6　素性测试 316

10.2　密码计算 320

10.2.1 对称加密模式 321

10.2.2　公钥密码系统 322

10.2.3　RSA密码系统 323

10.2.4　El Gamal密码系统 325

10.3　信息安全算法和协议 326

10.3.1　单向散列函数 326

10.3.2　时间戳和认证字典 327

10.3.3 硬币抛掷和比特承诺 327

10.3.4　安全电子传输（SET）协议 328

10.3.5　密钥分发和交换 329

10.4　快速傅里叶变换 330

10.4.1　本原单位根 332

10.4.2　离散傅里叶变换 333

10.4.3　快速傅里叶变换算法 335

10.4.4　大整数相乘 337

10.5　Java示例：FFT 339

10.6　习题 345

基础题 345

创新题 345

程序设计 346

10.7　本章注记 346

第11章　网络算法 348

11.1.1　网络协议栈 349

11.1.2　消息传递模型 349

11.1 复杂性测度和模型 349

11.1.3　网络算法的复杂性测度 350

11.2　基本分布式算法 351

11.2.1 环网上的领导人选举 351

11.2.2　树网上的领导人选举 354

11.2.3　广度优先查找 356

11.2.4　最小生成树 359

11.3　广播路由和单播路由 360

11.3.1　广播路由的洪泛算法 360

11.3.2　单播路由的距离矢量算法 361

11.3.3　单播路由的链路-状态算法 362

11.4.1　逆向路径转发 363

11.4　多播路由 363

11.4.2　中心树 364

11.4.3　Steiner树 365

11.5　习题 367

基础题 367

创新题 367

程序设计 369

11.6　本章注记 369

12.1 范围树 372

第12章　计算几何 372

第四部分　其他主题 372

12.1.1　一维范围查找 373

12.1.2　二维范围查找 375

12.2　优先查找树 377

12.2.1　构造一棵优先查找树 378

12.2.2　优先查找树中的查找 378

12.2.3　优先范围树 380

12.3　四叉树和k-d树 380

12.3.1 四叉树 381

12.3.2　k-d树 382

12.4.1 正交线段相交 383

12.4　平面扫描技术 383

12.4.2　查找最近点对 385

12.5　凸包 388

12.5.1　几何对象表示 388

12.5.2　点方位测试 389

12.5.3 凸包的基本性质 390

12.5.4　礼品包扎算法 392

12.5.5　Graham扫描算法 393

12.6　Java示例：凸包 395

基础题 398

创新题 398

12.7　习题 398

程序设计 400

12.8　本章注记 400

第13章　NP完全性 401

13.1　P类和NP类 402

13.1.1　定义复杂类P和复杂类NP 402

13.1.2　NP中的一些有趣问题 404

13.2　NP完全性 406

13.2.1 多项式时间归约和NP困难度 406

13.2.2　Cook-Levin定理 407

13.3　重要的NP完全问题 408

13.3.1　CNF-SAT和3SAT 410

13.3.2 VERTEX-COVER 412

13.3.3 CLIQUE和SET-COVER 413

13.3.4　SUBSET-SUM和KNAPSACK 415

13.3.5　HAMILTONIAN-CYCLE和TSP 417

13.4　近似算法 419

13.4.1　多项式时间的近似模式 420

13.4.2　VERTEX-COVER的2-近似算法 422

13.4.3　TSP特例的2-近似算法 423

13.4.4　SET-COVER的对数近似算法 424

13.5　回溯法和分枝限界法 426

13.5.1　回溯法 426

13.5.2　分枝限界法 429

13.6　习题 433

基础题 433

创新题 434

程序设计 435

13.7　本章注记 435

第14章　算法框架 437

14.1　外存算法 437

14.1.1　分层的存储器管理 438

14.1.2　（a,b）树和B树 440

14.1.3　外存排序 443

14.2.1　并行计算模型 445

14.2　并行算法 445

14.2.2　简单并行分治法 446

14.2.3 串行子集和Brent定理 447

14.2.4　递归倍增 447

14.2.5　并行归并和排序 450

14.2.6　找出凸多边形的直径 450

14.3　在线算法 452

14.3.1　高速缓存算法 452

14.3.2　拍卖策略 457

14.3.3　竞争查找树 458

创新题 461

基础题 461

14.4 习题 461

程序设计 462

14.5　本章注记 462

附录A　有用的数学知识 464

A.1 对数和指数 464

A.2　整型函数和关系 465

A.3　求和 466

A.4　有用的数学技术 467

参考书目 468

索引 476