第一章 引言 1
1.1算法 1
插入排序 1
伪代码的使用约定 3
练习 4
1.2分析算法 4
插入排序算法的分析 5
最坏情况和平均情况分析 6
增长的量级 7
练习 7
1.3设计算法 8
1.3.1分治法 8
1.3.2分治算法分析 10
合并排序算法的分析 10
练习 10
1.4小结 11
练习 12
问题 12
1-1运行时间的比较 12
1-2合并排序中插入排序在短数组上的应用 12
1-3逆序对 13
第一部分 数学基础 14
引言 14
第二章 函数的增长 15
2.1渐近记号 15
Θ-记号 15
O-记号 17
Ω-记号 18
方程中的渐近记号 18
o-记号 19
ω-记号 19
不同函数间的比较 20
练习 21
2.2标准记号体系和通用函数 21
单调性 21
底（Floor）和顶（Ceiling） 21
多项式 22
指数式 22
对数式 23
阶乘 24
多重对数函数 24
斐波那契数 24
练习 25
问题 26
2-1多项式的渐近性态 26
2-2相对渐近增长 26
2-3根据渐近增长率排序 26
2-4渐近记号的性质 27
2-5 O和Ω的一些变形 27
2-6多重函数 27
第三章 求和运算 29
3.1求和公式和性质 29
线性性质 29
算术级数 30
几何级数 30
调和级数 30
积分级数与微分级数 30
套迭级数 31
积 31
练习 31
3.2和式的界 32
数学归纳法 32
对项的限界 33
分解和式 34
积分近似公式 35
练习 36
问题 37
3-1和式的界 37
第四章 递归式 38
4.1替换方法 39
作一个好的猜测 39
一些细微问题 40
避免陷井 40
改变变量 41
练习 41
4.2迭代方法 41
递归树 42
练习 44
4.3主方法 44
主定理 44
主方法的应用 45
练习 45
4.4主定理的证明 46
4.4.1取整数幂时的证明 46
递归树 47
4.4.2底函数和顶函数 50
练习 52
问题 52
4-1递归式的例子 52
4-2找出所缺的整数 53
4-3参数传递的代价 53
4-4进一步的递归式的例子 53
4-5 Sloppincss条件 54
4-6斐波拉契数 54
4-7 VLSI芯片测试 55
第五章 集合、关系、函数、图和树 56
5.1集合 56
练习 59
5.2关系 59
练习 61
5.3函数 61
练习 63
5.4图 63
练习 66
5.5树 67
5.5.1自由树 67
5.5.2有根树和有序树 69
5.5.3二叉树和位置树 69
练习 71
问题 72
5-1图的着色问题 72
5-2友好图 72
5-3二分树 72
第六章 计数和概率 73
6.1计数 73
和规则与积规则 73
串 73
排列 74
组合 74
二项系数 74
二项界 75
练习 76
6.2概率 77
概率公理 77
离散概率分布 78
连续一致概率分布 78
条件概率和独立性 79
贝叶斯定理 80
练习 81
6.3离散随机变量 82
随机变量的期望值 83
方差和标准差 84
练习 84
6.4几何分布与二项分布 85
几何分布 85
二项分布 86
练习 89
6.5二项分布的尾 90
练习 94
6.6概率分析 95
6.6.1生日悖论 95
另一种分析方法 96
6.6.2球与盒子 97
6.6.3序列 98
练习 99
问题 99
6-1球和盒子 99
6-2 max程序的分析 100
6-3雇用问题 100
6-4概率计数 101
第二部分 排序和顺序统计学 102
引言 102
输入数据的结构 102
排序算法 102
顺序统计学 103
第七章堆排序 104
7.1堆 104
练习 105
7.2保持堆的性质 105
练习 106
7.3建堆 106
练习 109
7.4堆排序算法 109
练习 110
7.5优先级队列 111
练习 112
问题 113
7-1由插入而建堆 113
7-2对d叉堆的分析 113
第八章 快速排序 114
8.1对快速排序的描述 114
对数组进行划分 114
练习 116
8.2快速排序的性能 116
最坏情况划分 116
最佳情况划分 117
对称划分 118
关于平均情况的直觉考虑 118
练习 119
8.3快速排序的随机化版本 120
练习 121
8.4快速排序分析 121
8.4.1最坏情况分析 121
8.4.2平均情况分析 122
关于划分过程的分析 122
关于平均情况性态的递归式 123
解递归式 123
上述和式的紧确界 124
练习 124
问题 125
8-1划分的正确性 125
8-2 Lomuto划分算法 125
8-3 Stooge排序 126
8-4快速排序中的堆栈深度 126
8-5“三数取中”划分 127
第九章 线性时间排序 128
9.1排序算法的下界 128
决策树模型 128
最坏情况下界 129
练习 130
9.2计数排序 130
练习 132
9.3基数排序 132
练习 134
9.4桶排序 134
练习 136
问题 136
9-1比较排序的平均情况下界 136
9-2以线性时间做原地置换排序 137
第十章 中位数和顺序统计学 138
10.1最大元素和最小元素 138
同时找最小元素和最大元素 139
练习 139
10.2以线性期望时间做选择 139
练习 141
10.3最坏情况线性时间的选择 141
练习 142
问题 143
10-1已排序的i个最大数 143
10-2带权中位数 143
10-3小型顺序统计 144
第三部分 数据结构 146
引言 146
动态集合的元素 146
动态集合上的操作 146
第三部分纵观 147
第十一章 基本数据结构 148
11.1栈和队列 148
栈 148
队列 149
练习 150
11.2.链表 151
查找链表 152
对链表的插入操作 152
对链表的删除操作 152
哨兵 153
练习 154
11.3指针和对象的实现 155
对象的多重数组表示 155
对象的单数组表示 155
分配和释放对象 156
练习 158
11.4有根树的表示 158
二叉树 158
无界分叉的有根树 159
其他树的表示 160
练习 160
问题 161
11-1表的比较 161
11-2用链表实现可合并性 161
11-3查找一紧凑的排序链表 161
第十二章 杂凑表 163
12.1直接寻址表 163
练习 164
12.2杂凑表 165
通过拉链法来解决碰撞 166
对带拉链杂凑的分析 166
练习 168
12.3杂凑函数 168
好的杂凑函数的特点 169
将关键字解释为实数 169
12.3.1除法杂凑法 169
12.3.2乘法杂凑法 170
12.3.3全域杂凑 171
练习 172
12.4开放地址法 173
线性探查 174
二次探查 175
双重杂凑 176
对开放地址杂凑的分析 176
练习 179
问题 179
12-1最长探查的界 179
12-2查找静态集合 180
12-3拉链法中槽的大小 180
12-4二次探查 180
12-5 K-全域杂凑 181
第十三章 二叉查找树 182
13.1二叉查找树 182
练习 183
13.2查询二叉查找树 184
查找 184
最大元素和最小元素 185
前趋和后继 185
练习 186
13.3插入和删除 187
插入 187
删除 188
练习 189
13.4随机构造的二叉查找树 190
练习 194
问题 194
13-1具有相同关键字的二叉查找树 194
13-2基数树 195
13-3随机构造的二叉查找树中平均节点深度 195
13-4不同的二叉树个数 196
第十四章 红-黑树 197
14.1红-黑树的性质 197
练习 198
14.2旋转 199
练习 200
14.3插入 201
练习 204
14.4删除 204
练习 208
问题 209
14-1持久动态集合 209
14-2红-黑树上的连接操作 210
第十五章 数据结构的扩张 211
15.1动态顺序统计 211
检索具有给定秩的元素 212
确定一个元素的秩 213
对子树规模的维护 213
练习 214
15.2如何扩张数据结构 215
对红-黑树的扩张 216
练习 217
15.3区间树 217
练习 221
问题 222
15-1最大重迭点 222
15-2 Joscphus排列 222
第四部分 高级设计和分析技术 223
引言 223
第十六章 动态程序设计 224
16.1矩阵链乘法 224
计算括号化的重数 225
最优括号化的结构 226
一个递归解 226
计算最优代价 227
构造一个最优解 229
练习 229
16.2动态程序设计基础 230
最优结构 230
重迭子问题 231
记忆化 232
练习 234
16.3最长公共子序列 234
对最长公共子序列进行刻划 234
子问题的递归解 235
计算LCS的长度 236
构造一个LCS 237
对代码的改进 237
练习 238
16.4最优多边形三角剖分 238
与括号化的对应 239
最优三角剖分的子结构 241
一个递归解 241
练习 241
问题 242
16-1 Bitonic欧几里德货郎担问题 242
16-2优美打印 243
16-3编辑距E离 243
16-4 Vitcrbi算法 244
第十七章 贪心算法 245
17.1活动选择问题 245
证明贪心算法的正确性 247
练习 248
17.2贪心策略的基本内容 248
贪心选择性质 249
最优子结构 249
贪心法与动态程序设计 249
练习 250
17.3哈夫曼编码 251
前缀编码 252
构造哈夫曼编码 253
哈夫曼算法的正确性 254
练习 256
17.4贪心法的理论基础 257
17.4.1矩阵胚 257
17.4.2关于加权矩阵胚的贪心算法 258
练习 261
17.5一个任务调度问题 262
练习 264
问题 264
17-1找换硬币 264
17-2无环子图 264
17-3调度问题的变形 265
第十八章 平摊分析 266
18.1聚集方法 266
栈操作 267
二进计数器 268
练习 269
18.2会计方法 270
栈操作 270
二进计数器的增值 271
练习 271
18.3势能方法 271
栈操作 272
二进计数器的增值 273
练习 274
18.4动态表 274
18.4.1表的扩张 275
18.4.2表扩张和收缩 276
练习 281
问题 281
18-1按位反序二进计数器 281
18-2使二叉查找动态化 282
18-3平摊权平衡树 282
第五部分 高级数据结构 284
引言 284
第十九章 B-树 286
辅存上的数据结构 286
19.1 B-树的定义 288
B-树的高度 289
练习 290
19.2 B-树上的基本操作 290
查找B-树 290
创建一棵空B-树 291
B-树中节点的分裂 292
向B-树中插入一关键字 293
练习 296
问题 299
19-1辅存中的栈 299
19-2联结与分裂2-3-4树 299
第二十章 二项堆 301
20.1二项树与二项堆 302
20.1.1二项树 303
20.1.2二项堆 304
二项堆的表示 305
练习 305
20.2二项堆上的操作 306
创建一个新的二项堆 306
寻找最小关键字 306
合并两个二项堆 306
插入一个节点 311
抽取具有最小关键字的节点 312
对一个关键字减值 313
删除一个关键字 313
练习 314
问题 315
20-1 2-3-4堆 315
20-2 采用可合并堆的最小生成树算法 316
第二十一章 斐波那契堆 317
21.1斐波那契堆的结构 318
势函数 319
最大度数 319
21.2可合并堆操作 319
创建一个新的斐波那契堆 320
插入一个节点 320
寻找最小节点 321
合并两个斐波那契堆 321
抽取最小节点 322
练习 326
21.3减小一个关键字与删除一个节点 326
减小一个关键字 326
删除一个节点 329
练习 329
21.4最大度数的界 329
练习 332
问题 332
21-1删除的另一种实现 332
21-2另一些斐波那契堆操作 332
第二十二章 用于分离集合的数据结构 334
22.1分离集合的操作 334
分离集合数据结构的一个应用 335
练习 336
22.2分离集合的链表表示 337
UNION的一个简单实现 337
一种加权合并启发式 337
练习 338
22.3分离集合森林 339
改进运行时间的启发式 339
分离集合森林的伪代码 340
启发式知识对运行时间的影响 341
练习 341
22.4关于带路径压缩的按秩合并的分析 342
Ackerman 数与其逆函数 342
秩的性质 344
时间界的证明 345
练习 348
问题 348
22-1脱机最小值 348
22-2深度确定 349
22-3 Tarjan的脱机最小公共祖先算法 350
第六部分 图的算法 351
引言 351
第二十三章 图的基本算法 352
23.1图的表示 352
练习 354
23.2宽度优先搜索 354
分析 357
最短路径 357
宽度优先树 359
练习 360
23.3深度优先搜索 361
深度优先搜索的性质 363
边的分类 365
练习 366
23.4拓扑排序 367
练习 368
23.5强连通支 369
练习 373
问题 374
23-1通过宽度优先搜索对边进行分类 374
23-2挂接点、桥以及双连通子图 374
23-3欧拉回路 375
第二十四章 最小生成树 376
24.1最小生成树的形成 377
练习 379
24.2Kruskal算法和Prim算法 380
Kruskal算法 381
Prim算法 382
练习 384
问题 385
24-1次最小生成树 385
24-2稀疏图的最小生成树 385
第二十五章 单源最短路径 387
变体 387
负权边 388
最短路径的表示方法 389
本章概述 389
25.1最短路径和松弛技术 390
最短路径的理想基础 390
松弛 391
松弛的性质 392
最短路径树 394
练习 396
25.2 Dijkstra算法 397
分析 399
练习 400
25.3 Bcllman-Ford算法 400
练习 403
25.4有向无回路图中的单源最短路径 403
练习 405
25.5差分约束与最短路径 405
线性规划 406
差分约束系统 406
约束图 407
差分约束系统问题的求解 409
练习 409
问题 410
25-1对Bcllman-Ford算法的Yen氏改进 410
25-2嵌套框 411
25-3套汇问题 411
25-4关于单源最短路径的Gabow定标算法 411
25-5Karp最小平均权回路算法 412
第二十六章 每对结点间的最短路径 414
本章概述 415
26.1最短路径与矩阵乘法 415
最短路径的结构 416
解决每对结点间的最短路径问题的一种递归方法 416
自底向上计算最短路径的权 416
算法运行时间的改进 419
练习 419
26.2 Floyd-Warshall算法 420
最短路径的结构 421
解决每对结点间最短路径问题的一种递归方案 421
自底向上计算最短路径的权 423
建立最短路径 423
有向图的传递闭包 424
练习 425
26.3关于稀疏图的Johnson算法 426
通过重赋权保持最短路径 427
通过重赋权产生非负的权 429
计算每对结点间的最短路径 429
练习 430
26.4解决有向图中路径问题的一般性框架 430
闭半环的定义 430
有向图中路径的计算 431
闭半环的实例 433
关于有向图标示的一个动态规划算法 433
练习 435
问题 435
26-1动态图的传递闭包 435
26-2ε-稠密图中的最短路径 436
26-3作为一个闭半环的最小生成树 436
第二十七章 最大流 437
27.1流网络 437
流网络与流 438
网络流的一个实例 439
多个源和多个汇的网络 441
对流的处理 441
练习 442
27.2 Ford-Fulkcrson方法 443
残留网络 443
增广路径 445
流网络的割 446
基本的Ford-Fulkcrson算法 448
Ford-Fulkcrson算法的分析 449
练习 452
27.3最大偶匹配 452
最大偶匹配问题 453
寻求最大偶匹配 453
练习 455
27.4先流推进算法 455
直觉知识 456
基本的操作 457
一般性算法 458
先流推进方法的正确性 459
先流推进方法的分析 460
练习 463
27.5向前提升算法 463
容许边和容许网络 464
相邻表 465
溢出结点的释放 465
向前提升算法 458
算法分析 470
练习 471
问题 471
27-1逃脱问题 471
27-2最小路径覆盖 472
27-3航天飞机进行的实验 472
27-4最大流的更新 473
27-5用定标法计算最大流 473
27-6具有容量上限和下限的最大流 473
第七部分 论题选编 475
引言 475
第二十八章 排序网络 477
28.1 比较网络 477
练习 480
28.2 0-1原则 480
练习 482
28.3 双调排序网络 483
半清洁器 483
双调排序程序 484
练习 485
28.4 合并网络 485
练习 487
28.5 排序网络 487
练习 488
问题 489
28-1 转置顺序网络 489
28-2 Batcher奇偶合并网络 489
28-3 排列网络 490
第二十九章 运算电路 491
29.1 组合电路 491
组合电路 492
全加器 493
电路深度 494
电路规模 494
练习 495
29.2加法电路 495
29.2.1行波进位加法 495
29.2.2先行进位加法器 496
完成先行进位加法器的构造 496
29.2.3保留进位加法 501
练习 502
29.3乘法电路 504
29.3.1阵列乘法器 504
分析 507
29.3.2华莱士树型乘法器 507
分析 508
练习 509
29.4时钟电路 509
29.4.1位串行加法 509
分析 511
行波进位加法与位串行加法 511
29.4.2线性阵列乘法器 511
一种慢速线性阵列实现方法 513
一种快速的线性阵列实现方法 513
练习 514
问题 515
29-1除法电路 515
29-2关于对称函数的布尔公式 515
第三十章 关于并行计算机的算法 517
PRAM模型 517
并发存储器存取方式与互斥存储器存取方式 518
同步与控制 519
本章概述 519
30.1指针转移 520
30.1.1表排序 520
正确性 521
分析 522
30.1.2列表的并行前缀 522
30.1.3欧拉回路技术 524
练习 526
30.2 CRCW算法与EREW算法 527
并发操作发挥作用的有关问题 527
并发写操作发挥作用的一个问题 529
用EREW算法来模拟CRCW算法 531
练习 533
30.3 Brent定理与工作效率 533
练习 536
30.4工作效率高的并行前缀计算 537
递归的并行前缀计算 537
选择要消除的对象 539
分析 539
练习 541
30.5确定的打破对称性问题 541
着色与最大独立集 542
计算6-着色问题 542
根据6-着色计算出MIS 545
练习 545
问题 546
30-1分段的并行前缀 546
30-2处理器效率的最大值算法 546
30-3连通子图 547
30-4对光栅像进行转置处理 548
第三十一章 关于矩阵的操作 549
31.1矩阵的性质 549
矩阵和向量 549
关于矩阵的操作 552
矩阵的逆矩阵,秩和行列式 553
正定矩阵 555
练习 555
31.2关于矩阵乘法的Strassen算法 556
算法总论 556
确定子矩阵的乘积 557
讨论 560
练习 561
31.3代数系统与布尔矩阵乘法 561
拟环 561
环 562
布尔矩阵的乘法 563
域 564
练习 564
31.4求解线性方程组 565
LUP分解总述 566
正向替换与逆向替换 566
关于LU分解的计算 569
LUP分解的计算 572
练习 575
31.5逆矩阵 575
根据LUP分解来计算逆矩阵 576
矩阵乘法与逆矩阵 576
把求逆矩阵问题转化为矩阵乘法问题 577
练习 578
31.6对称正定矩阵与最小二乘逼近 579
最小二乘逼近 581
练习 584
问题 584
31-1 Shamir布尔矩阵乘法算法 584
31-2三对角线性方程组 585
31-3.样条 585
第三十二章 多项式与快速付里叶变换 587
多项式 587
本章概述 588
32.1多项式的表示 588
系数表示法 589
点值表示法 589
关于系数形式表示的多项式的快速乘法 591
练习 592
32.2 DFT与FFT 593
单位元素的复根 593
DFT 595
FFT 595
对单位元素的复根进行插值 598
练习 599
32.3有效的FFT实现方法 599
FFT的一种迭代实现 600
并行FFT电路 603
练习 604
问题 604
32-1分治乘法 604
32-2Tocplitz矩阵 604
32-3求多项式在某一点的所有阶导数的值 604
32-4多项式在多个点的求值 605
32-5运用模运算的FFT 606
第三十三章 有关数论的算法 607
输入的规模与算术运算的代价 607
33.1基本的数论概念 608
可除性与约数 608
素数与合数 608
除法定理,余数和同模 608
公约数与最大公约数 609
互质数 610
唯一的因子分解 611
练习 611
33.2最大公约数 612
欧几里德算法 613
EUCLID算法的运行时间 613
欧几里德算法的推广形式 615
练习 616
33.3模运算 616
有限群 617
根据模加法与模乘法所定义的群 617
子群 620
由一个元素生成的子群 620
练习 621
33.4求解模线性方程 622
练习 624
33.5中国余数定理 625
练习 627
33.6元素的幂 627
运用反复平方法求数的幂 630
练习 631
33.7 RSA公开密钥加密系统 631
公开密钥加密系统 631
RSA加密系统 632
练习 635
33.8.素数的测试 636
素数的密度 636
伪素数测试过程 637
Miller-Rabin随机性素数测试方法 638
Miller-Rabin素数测试过程的出错率 639
练习 640
33.9整数的因子分解 641
POLLARD的rho启发性方法 641
练习 644
问题 644
33-1二进制的gcd算法 644
33-2欧几里德算法中对位操作的分析 645
33-3关于Fibonacci数的三个算法 645
33-4二次残数 645
第三十四章 串匹配 647
记号与术语 648
34.1朴素的串匹配算法 649
练习 649
34.2 Rabim-Karp算法 650
练习 653
34.3利用有限自动机进行串匹配 654
有限自动机 654
串匹配自动机 655
计算变迁函数 658
练习 658
34.4 Knuth-Morris-Pratt算法 659
关于模式的前缀函数 659
运行时间分析 662
前缀函数计算过程的正确性 662
KMP算法的正确性 664
练习 664
34.5 Boyer-Moore算法 665
坏字符启发性方法 666
好后缀启发性方法 668
练习 670
问题 670
34-1基于重复因子的串匹配算 670
34-2并行串匹配 671
第三十五章计算几何学 672
35.1线段的性质 672
叉积 673
确定连续线段是向左转还是向右转 674
确定两条线段是否相交 674
叉积的其它应用 675
练习 675
35.2确定任意一对线段是否相交 676
排序线段 676
扫除线的移动 677
求线段交点的伪代码 678
正确性 679
运行时间 680
练习 680
35.3寻找凸包 680
Graham扫描法 682
Jarvis步进法 687
练习 688
35.4寻找最近点对 688
分治算法 689
正确性 690
算法实现与运行时间 691
练习 691
问题 692
35-1凸层 692
35-2最大层 692
35-3巨人和鬼 693
35-4稀疏包分布 693
第三十六章NP-完全性 694
36.1多项式时间 695
抽象问题 695
编码 696
形式语言体系 698
练习 699
36.2多项式时间的验证 700
汉密尔顿回路 700
验证算法 701
复杂类NP 701
练习 702
36.3 NP-完全性与可约简性 703
可化简性 703
NP-完全性 705
电路可满足性 705
练习 710
36.4 NP-完全性的证明 710
公式可满足性 711
3-CNF可满足性 713
练习 715
36.5一些NP-完全的问题 716
36.5.1集团问题 716
36.5.2顶点覆盖问题 718
36.5.3子集和问题 720
36.5.4汉密尔顿回路问题 722
36.5.5货郎担问题 726
练习 727
问题 728
36-1独立集 728
36-2图的着色 728
第三十七章 近似算法 730
近似算法的性能界 730
本章内容的安排 731
37.1顶点覆盖问题 731
练习 733
37.2货郎担问题 733
37.2.1带三角不等式的货郎担问题 734
37.2.2一般货郎担问题 736
练习 737
37.3集合覆盖问题 737
一个贪心近似算法 738
分析 739
练习 740
37.4子集和问题 741
一个指数时间算法 741
一个完全多项式时间近似方案 742
练习 744
问题 744
37-1装箱 744
37-2对最大集团规模的近似 745
37-3加权集合覆盖问题 745