第一篇基本知识 2
第一章算法概念 2
1.1算法 2
目 录 2
插入排序 3
伪代码的使用约定 4
1.2算法分析 4
插入排序算法的分析 5
最坏情况和平均情况分析 6
1.3.1分治法 7
增长的量级 7
1.3算法设计 7
1.3.2分治算法分析 9
合并排序算法的分析 9
1.4小结 10
思考题 10
练习一 11
第二章函数的增长 13
2.1渐近记号 13
Θ－记号 13
O－记号 15
方程中的渐近记号 16
Ω－记号 16
O－记号 17
ω－记号 17
不同函数间的比较 18
2.2标准记号体系和通用函数 18
多项式 19
指数式 19
底（Floor）和顶（Ceiling） 19
单调性 19
对数式 20
阶乘 21
多重对数函数 21
斐波那契数 22
思考题 22
练习二 25
第三章求和运算 26
3.1求和公式和性质 26
线性性质 26
套迭级数 27
积分级数与微分级数 27
算术级数 27
几何级数 27
调和级数 27
积 28
3.2和式的界 28
数学归纳法 28
对项的限界 29
分解和式 30
积分近似公式 32
练习三 33
思考题 33
第四章递归式 35
4.1替换方法 35
作一个好的猜测 36
一些细微问题 37
避免陷井 37
改变变量 37
4.2迭代方法 38
递归树 39
主定理 40
4.3主方法 40
主方法的应用 41
* 4.4主定理的证明 42
4.4.1 取整数幂时的证明 42
递归树 43
4.4.2底函数和顶函数 46
思考题 48
练习四 50
5.1集合 52
第五章集合、关系、函数、图和树 52
5.2关系 54
5.3函数 56
5.4图 57
5.5树 60
5.5.1 自由树 60
5.5.2有根树和有序树 62
5.5.3二叉树和位置树 63
思考题 64
练习五 65
串 67
和规则与积规则 67
第六章计数和概率 67
6.1计数 67
排列 68
组合 68
二项系数 68
三项界 69
6.2概率 69
概率公理 70
离散概率分布 70
条件概率和独立性 71
连续一致概率分布 71
贝叶斯定理 72
6.3离散随机变量 73
随机变量的期望值 74
方差和标准差 75
6.4几何分布与二项分布 75
几何分布 76
二项分布 77
6.5二项分布的尾 79
6.6.1生日悖论 83
6.6概率分析 83
另一种分析方法 84
6.6.2球与盒子 85
6.6.3序列 85
思考题 87
练习六 88
第二篇排序和顺序统计学 92
输入数据的结构 92
排序算法 92
顺序统计学 93
7.1堆 94
第七章堆排序 94
7.2保持堆的性质 95
7.3建堆 96
7.4堆排序算法 98
7.5优先级队列 99
思考题 101
练习七 102
第八章快速排序 104
8.1对快速排序的描述 104
对数组进行划分 104
最坏情况划分 106
8.2快速排序的性能 106
最佳情况划分 107
对称划分 107
关于平均情况的直觉考虑 108
8.3快速排序的随机化版本 109
8.4快速排序分析 110
8.4.1最坏情况分析 110
8.4.2平均情况分析 111
关于划分过程的分析 111
关于平均情况性态的一个递归式 111
解递归式 112
上述和式的紧确界 113
思考题 113
练习八 115
第九章线性时间排序 117
9.1排序算法的下界 117
决策树模型 117
最坏情况下界 118
9.2计数排序 118
9.3基数排序 120
9.4桶排序 121
思考题 123
练习九 124
第十章中位数和顺序统计学 126
10.1最大元素和最小元素 126
同时找最小元素和最大元素 127
10.2以线性期望时间做选择 127
10.3最坏情况线性时间的选择 129
思考题 130
练习十 131
动态集合上的操作 133
动态集合的元素 133
第三篇数据结构 133
内容综述 134
第十一章基本数据结构 135
11.1栈和队列 135
栈 135
队列 136
11.2链表 137
查找链表 138
对链表的插入操作 138
哨兵 139
对链表的删除操作 139
11.3指针和对象的实现 140
对象的多重数组表示 141
对象的单数组表示 141
分配和释放对象 142
11.4有根树的表示 143
二叉树 143
无界分叉的有根树 144
树的其他表示 145
思考题 145
练习十一 146
第十二章杂凑表 149
12.1直接寻址表 149
12.2杂凑表 150
通过拉链法来解决碰撞 151
对带拉链杂凑的分析 152
12.3杂凑函数 153
好的杂凑函数的特点 153
将关键字解释为实数 153
12.3.1除法杂凑法 154
12.3.2乘法杂凑法 154
12 3.3全域杂凑 155
12.4开放地址法 156
线性探查 158
二次探查 158
双重杂凑 158
对开放地址杂凑的分析 159
思考题 161
练习十二 163
第十三章二叉查找树 165
13.1二叉查找树 165
查找 166
13.2查询二叉查找树 166
最大元素和最小元素 167
前趋和后继 168
13.3插入和删除 169
插入 169
删除 170
* 13.4随机构造的二叉查找树 171
思考题 174
练习十三 177
14.1红－黑树的性质 179
第十四章红－黑树 179
14.2旋转 180
14.3插入 182
14.4删除 185
思考题 188
练习十四 190
第十五章数据结构的扩张 192
15.1动态顺序统计 192
检索具有给定秩的元素 193
确定一个元素的秩 193
对子树规模的维护 194
15.2如何扩张数据结构 195
对红－黑树的扩张 196
15.3 区间树 197
思考题 200
练习十五 201
第四篇高级设计和分析技术 204
第十六章 动态程序设计 204
16.1 矩阵链乘法 204
计算括号化的重数 205
一个递归解 206
最优括号化的结构 206
计算最优代价 207
构造最优解 209
16.2 动态程序设计基础 209
最优结构 209
重叠子问题 210
记忆化 211
16.3 最长公共子序列 213
对最长公共子序列进行刻划 213
计算LCS的长度 214
子问题的递归解 214
构造一个LCS 215
对代码的改进 216
16.4最优多边形三角剖分 216
与括号化的对应 217
最优三角剖分的子结构 219
一个递归解 219
思考题 220
练习十六 220
17.1 活动选择问题 223
第十七章贪心算法 223
证明贪心算法的正确性 225
17.2 贪心策略的基本内容 226
贪心选择性质 226
最优子结构 226
贪心法与动态程序设计 226
17.3哈夫曼编码 228
前缀编码 228
构造哈夫曼编码 230
哈夫曼算法的正确性 231
*17.4贪心法的理论基础 232
17.4.1矩阵胚 233
17.4.2关于加权矩阵胚的贪心算法 234
17.5一个任务调度问题 236
思考题 238
练习十七 239
第十八章平摊分析 241
18.1聚集方法 241
栈操作 241
二进计数器 243
栈操作 244
18.2会计方法 244
二进计数器的增值 245
18.3势能方法 246
栈操作 246
二进计数器的增值 247
18.4动态表 248
18.4.1表的扩张 248
18.4.2表扩张和收缩 251
思考题 254
练习十八 256
辅存上的数据结构 259
第五篇高级数据结构 259
第十九章B－树 259
19.1 B－树的定义 261
B－树的高度 262
19.2 B－树上的基本操作 263
查找B－树 263
创建一棵空B－树 264
B－树中节点的分裂 264
向B－树中插入一关键字 265
19.3从B－树中删除一个关键字 268
思考题 270
练习十九 271
第二十章 二项堆 273
20.1二项树与二项堆 274
20.1.1 二项树 274
20.1.2 二项堆 275
二项堆的表示 276
创建一个新的二项堆 277
寻找最小关键字 277
20.2 二项堆上的操作 277
合并两个二项堆 278
插入一个节点 282
抽取具有最小关键字的节点 283
对一个关键字减值 284
删除一个关键字 284
思考题 285
练习二十 287
第二十一章斐波那契堆 288
21.1斐波那契堆的结构 289
21.2可合并堆操作 290
最大度数 290
势函数 290
创建一个新的斐波那契堆 291
插入一个节点 291
寻找最小节点 292
合并两个斐波那契堆 292
抽取最小节点 292
21.3减小一个关键字与 296
删除一个节点 296
减小一个关键字 297
21.4最大度数的界 299
删除一个节点 299
思考题 301
练习二十一 302
第二十二章用于分离集合的数据结构 303
22.1分离集合的操作 303
分离集合数据结构的一个应用 304
22.2分离集合的链表表示 305
UNION的一个简单实现 305
一种加权合并启发式 306
改进运行时间的启发式 307
22.3分离集合森林 307
分离集合森林的伪代码 308
启发式知识对运行时间的影响 309
*22.4 关于带路径压缩的 309
按秩合并的分析 309
Ackerman函数与其逆函数 309
秩的性质 311
时间界的证明 312
思考题 315
练习二十二 317
第二十三章图的基本算法 319
第六篇图的算法 319
23.1 图的表示 320
23.2宽度优先搜索 322
分析 324
最短路径 324
宽度优先树 326
23.3深度优先搜索 327
深度优先搜索的性质 330
边的分类 331
23.4拓扑排序 332
23.5强连通支 333
思考题 337
练习二十三 339
第二十四章最小生成树 342
24.1最小生成树的形成 343
24.2 Kruskal算法和Prim算法 345
Kruskal算法 345
Prim算法 347
思考题 349
练习二十四 351
第二十五章单源最短路径 352
单源最短路径问题的变形 352
负权边 353
最短路径的表示方法 353
本章概述 354
25.1最短路径和松弛技术 355
最短路径的理想基础 355
松弛技术 356
松弛的性质 357
最短路径树 358
25.2 Dijkstra算法 360
分析 362
25.3 Bellman-Ford算法 363
25.4有向无回路图中的 366
单源最短路径 366
25.5差分约束与最短路径 367
线性程序设计 367
差分约束系统 368
约束图 369
差分约束系统问题的求解 370
思考题 371
练习二十五 373
第二十六章每对结点间的最短路径 377
26.1最短路径与矩阵乘法 378
最短路径的结构 379
解决每对结点间的最短路径问题的 379
一种递归方法 379
自底向上计算最短路径的权 379
算法运行时间的改进 381
26.2 Floyd-Warshall算法 382
最短路径的结构 382
自底向上计算最短路径的权 383
解决每对结点间最短路径问题的 383
一种递归方案 383
建立最短路径 385
有向图的传递闭包 385
26.3关于稀疏图的Johnson算法 387
通过重赋权保持最短路径 387
通过重赋权产生非负的权 388
计算每对结点间的最短路径 389
的一般性框架 390
闭半环的定义 390
*26.4解决有向图中路径问题 390
有向图中路径的计算 391
闭半环的实例 393
关于有向图标示的一个 394
动态程序设计算法 394
思考题 395
练习二十六 396
第二十七章最大流 399
27.1 流网络 399
流网络与流 399
网络流的一个实例 401
多个源和多个汇的网络 402
对流的处理 403
27.2 Ford-Fulkerson方法 404
残留网络 404
增广路径 406
流网络的割 406
基本的Ford-Fulkerson算法 408
Ford-Fulkerson算法的分析 409
最大二分匹配问题 412
27.3最大二分匹配 412
寻求最大二分匹配 413
27.4先流推进算法 415
直觉知识 415
基本的操作 416
一般性算法 417
先流推进方法的正确性 418
先流推进方法的分析 419
*27.5向前提升算法 421
容许边和容许网络 421
相邻表 422
溢出结点的释放 423
向前提升算法 425
算法分析 427
思考题 428
练习二十七 431
第七篇论题选编 436
第二十八章排序网络 436
28.1比较网络 436
28.2 0-1原则 438
半清洁器 440
28.3双调排序网络 440
双调排序程序 442
28.4合并网络 442
28.5排序网络 444
思考题 445
练习二十八 447
第二十九章算术电路 449
29.1 组合电路 449
组合元件 449
组合电路 450
全加器 451
电路规模 452
电路深度 452
29.2加法电路 453
29.2.1行波进位加法 453
29.2.2先行进位加法器 454
完成先行进位加法器的构造 458
29.2.3保留进位加法 459
29.3乘法电路 460
29.3.1阵列乘法器 460
29.3.2华莱士树乘法器 463
分析 463
分析 464
29.4时钟电路 464
29.4.1位串行加法 465
分析 466
行波进位加法与位串行加法 466
29.4.2线性阵列乘法器 466
一种慢速线性阵列实现方法 467
一种快速的线性阵列实现方法 469
思考题 469
练习二十九 470
PRAM模型 473
第三十章关于并行计算机的算法 473
并发存储器存取方式与 474
互斥存储器存取方式 474
同步与控制 475
本章概述 475
30.1指针转移 475
30.1.1表排序 476
正确性 477
30.1.2列表的并行前缀 478
分析 478
30.1.3欧拉回路技术 480
30.2 CRCW算法与EREW算法 482
并发操作发挥作用的有关问题 482
并发写操作发挥作用的一个问题 484
用EREW算法来模拟CRCW算法 486
30.3 Brent定理与工作效率 488
*30.4高效的并行前缀计算 490
递归的并行前缀计算 490
选择要消除的对象 492
分析 493
30.5确定的打破对称性问题 494
着色与最大独立集 495
计算6－着色问题 495
根据6－着色计算出 MIS 498
思考题 498
练习三十 501
第三十一章矩阵操作 503
31.1矩阵的性质 503
矩阵和向量 503
关于矩阵的操作 506
逆矩阵，秩和行列式 507
正定矩阵 508
31.2关于矩阵乘法的Strassen算法 509
算法概述 509
确定子矩阵的乘积 510
讨论 513
* 31.3代数系统与布尔矩阵乘法 513
拟环 513
环 514
域 515
布尔矩阵的乘法 515
31.4求解线性方程组 516
LUP分解总述 517
正向替换与逆向替换 518
关于LU分解的计算 520
LUP分解的计算 523
31.5逆矩阵 526
根据LUP分解来计算逆矩阵 526
矩阵乘法与逆矩阵 526
矩阵乘法问题 527
把求逆矩阵问题转化为 527
31.6对称正定矩阵与 529
最小二乘逼近 529
最小二乘逼近 530
思考题 533
练习三十一 535
第三十二章多项式与快速傅里叶变换 539
多项式 539
32.1多项式的表示 540
系数表示法 540
本章概述 540
点值表示法 541
关于系数形式表示的多项式 543
的快速乘法 543
32.2 DFT与FFT 544
单位元素的复根 544
DFT 546
FFT 546
对单位元素的复根进行插值 548
FFT的一种迭代实现 549
32.3有效的FFT实现方法 549
并行FFT电路 552
思考题 553
练习三十二 556
第三十三章有关数论的算法 558
输入的规模与算术运算的代价 558
33.1基本的数论概念 559
可除性与约数 559
素数与合数 559
除法定理，余数和同模 559
公约数与最大公约数 560
互质数 561
唯一的因子分解 561
33.2最大公约数 562
欧几里德算法 563
EUCLID算法的运行时间 563
欧几里德算法的推广形式 564
33.3模运算 565
有限群 565
根据模加法与模乘法所定义的群 566
子群 568
由一个元素生成的子群 569
33.4求解模线性方程 570
33.5中国余数定理 572
33.6元素的幂 574
运用反复平方法求数的幂 576
33.7 RSA公开密钥加密系统 577
公开密钥加密系统 577
RSA加密系统 579
33.8素数的测试 581
素数的密度 581
伪素数测试过程 582
Miller-Rabin随机性素数测试方法 583
Miller-Rabin素数测试过程的出错率 585
*33.9整数的因子分解 587
POLLARD的rho启发性方法 587
思考题 590
练习三十三 592
第三十四章串匹配 595
记号与术语 595
34.1朴素的串匹配算法 596
34.2 Rabin-Karp算法 597
34.3 利用有限自动机进行串匹配 600
有限自动机 601
串匹配自动机 601
计算变迁函数 604
34.4 Knuth-Morris-Pratt算法 605
关于模式的前缀函数 605
运行时间分析 607
前缀函数计算过程的正确性 608
KMP算法的正确性 609
34.5 Boyer-Moore算法 610
坏字符启发性方法 611
好后缀启发性方法 613
思考题 614
练习三十四 616
第三十五章计算几何学 618
35.1线段的性质 618
叉积 619
确定连续线段是向左转还是向右转 620
确定两条线段是否相交 620
叉积的其他应用 621
35.2确定任意一对线段是否相交 621
扫除线的移动 622
排序线段 622
求线段交点的伪代码 623
正确性 624
运行时间 625
35.3寻找凸包 625
Graham扫描法 626
Jarvis步进法 631
35.4寻找最近点对 632
分治算法 632
正确性 633
算法实现与运行时间 634
思考题 635
练习三十五 636
第三十六章NP－完全性 639
36.1多项式时间 640
抽象问题 640
编码 641
形式语言体系 642
36.2多项式时间的验证 644
汉密尔顿回路 644
复杂类NP 645
验证算法 645
36.3 NP－完全性与可化简性 646
可化简性 647
NP－完全性 648
电路可满足性 649
36.4 NP－完全性的证明 653
公式可满足性 653
3－CNF可满足性 655
36.5一些NP－完全的问题 658
36.5.1集团问题 658
36.5.2顶点覆盖问题 660
36.5.3子集和问题 661
36.5.4汉密尔顿回路问题 663
36.5.5货郎担问题 668
思考题 669
练习三十六 670
第三十七章近似算法 673
近似算法的性能界 673
本章内容的安排 674
37.1 顶点覆盖问题 674
37.2.1 满足三角不等式的货郎担问题 676
37.2货郎担问题 676
37.2.2一般货郎担问题 678
37.3集合覆盖问题 679
一个贪心近似算法 680
分析 680
37.4子集和问题 682
一个指数时间算法 682
一个完全多项式时间近似方案 683
思考题 686
练习三十七 686