《算法设计与分析》简介：

本书讲授算法设计与分析的基础知识。首先介绍计算模型的基本概念；其次围绕遍历、分治、贪心、动态规划这四个经典算法设计策略，讲解了排序、选择、查找、图遍历、小生成树、短路径等经典算法问题；后介绍了计算复杂性的基础知识。本书主要面向计算机专业本科生，以及其他需要学习计算机科学基础知识与了解计算机程序设计背后原理的读者。

《算法设计与分析》目录：

前言
教学建议
第一部分计算模型
第1章抽象的算法设计与分析2
1.1RAM模型的引入2
1.1.1计算的基本概念2
1.1.2计算模型的基本概念3
1.1.3RAM模型4
1.1.4计算模型的选择：易用性和精确性6
1.2抽象算法设计7
1.2.1算法问题规约7
1.2.2算法正确性证明：数学归纳法8
1.3抽象算法分析10
1.3.1抽象算法的性能指标10
1.3.2最坏情况时间复杂度分析11
1.3.3平均情况时间复杂度分析12
1.4习题13
第2章从算法的视角重新审视数学的概念16
2.1数学运算背后的算法操作16
2.1.1取整x和x16
2.1.2对数logn17
2.1.3阶乘n！18
2.1.4常见级数求和∑ni=1f（i）19
2.1.5期望E（X）20
2.2函数的渐近增长率22
2.3“分治递归”求解24
2.3.1替换法24
2.3.2分治递归与递归树25
2.3.3Master定理26
2.4习题27
第二部分朴素遍历
第3章线性表的遍历32
3.1基于遍历的选择与查找32
3.2基于遍历的排序33
3.2.1选择排序34
3.2.2插入排序35
3.3习题37
第4章图的深度优先遍历39
4.1图和图遍历39
4.2有向图的深度优先遍历40
4.2.1有向图的深度优先遍历框架40
4.2.2有向图的深度优先遍历树42
4.2.3活动区间43
4.3有向图的深度优先遍历应用45
4.3.1拓扑排序45
4.3.2关键路径48
4.3.3有向图中的强连通片50
4.4无向图的深度优先遍历54
4.4.1无向图的深度优先遍历树55
4.4.2无向图的深度优先遍历框架56
4.5无向图的深度优先遍历应用57
4.5.1容错连通57
4.5.2寻找割点58
4.5.3寻找桥60
4.6习题61
第5章图的广度优先遍历66
5.1广度优先遍历66
5.1.1广度优先遍历框架67
5.1.2有向图的广度优先遍历树70
5.1.3无向图的广度优先遍历树70
5.2广度优先遍历的应用72
5.2.1判断二分图72
5.2.2寻找k度子图73
5.3习题74
第三部分分治策略
第6章排序：从遍历到分治78
6.1快速排序78
6.1.1插入排序的不足78
6.1.2快速排序的改进79
6.1.3快速排序的分析81
6.2合并排序84
6.3基于比较的排序的下界86
6.3.1决策树的引入87
6.3.2比较排序最坏情况时间复杂度的下界88
6.3.3比较排序平均情况时间复杂度的下界88
6.4习题90
第7章堆的设计与应用95
7.1堆的定义95
7.2堆的抽象维护96
7.2.1堆的修复96
7.2.2堆的构建97
7.3堆的具体实现98
7.4堆的应用100
7.4.1堆排序100
7.4.2基于堆实现优先队列100
7.5习题101
第8章线性时间选择103
8.1期望线性时间的选择103
8.1.1期望线性时间的选择算法设计103
8.1.2期望线性时间的选择算法分析104
8.2最坏情况线性时间的选择106
8.2.1最坏情况线性时间的选择算法设计106
8.2.2最坏情况线性时间的选择算法分析107
8.3习题108
第9章对数时间查找110
9.1折半查找110
9.1.1经典折半查找110
9.1.2折半查找的推广111
9.2平衡二叉搜索树112
9.2.1二叉搜索树及其平衡性113
9.2.2红黑树的定义114
9.2.3红黑树的平衡性115
9.3习题116
第四部分贪心策略
第10章最小生成树120
10.1Prim算法120
10.1.1Prim算法的正确性122
10.1.2Prim算法的实现125
10.1.3Prim算法的分析126
10.2Kruskal算法127
10.2.1Kruskal算法的正确性128
10.2.2判断是否成环——基于并查集的实现129
10.2.3Kruskal算法的实现与分析133
10.3最小生成树贪心构建框架MCE134
10.3.1从MCE框架的角度分析Prim算法135
10.3.2从MCE框架的角度分析Kruskal算法136
10.4习题137
第11章给定源点的最短路径142
11.1Dijkstra算法142
11.1.1Dijkstra算法的设计142
11.1.2Dijkstra算法的正确性与性能分析144
11.2从Dijkstra算法到贪心遍历框架BestFS146
11.3习题147
第12章贪心策略的其他应用151
12.1相容任务调度问题151
12.1.1直觉的尝试151
12.1.2基于任务结束时间的贪心算法152
12.2Huffman编码153
12.2.1可变长度编码153
12.2.2最优编码方案的性质154
12.2.3贪心的Huffman编码156
12.3习题156
第五部分动态规划
第13章最短路径160
13.1有向无环图上的给定源点最短路径问题160
13.2传递闭包问题和Shortcut算法161
13.3所有点对最短路径：基于路径长度的递归163
13.4Floyd—Warshall算法：基于中继节点范围的递归164
13.5习题166
第14章动态规划算法168
14.1动态规划的动机168
14.2动态规划的基本过程169
14.2.1基于朴素遍历的递归170
14.2.2未作规划的递归171
14.2.3采用动态规划的递归171
14.3动态规划的应用174
14.3.1动态规划的要素174
14.3.2编辑距离问题175
14.3.3硬币兑换问题176
14.3.4最大和连续子序列问题178
14.3.5相容任务调度问题179
14.4习题179
第六部分计算复杂性理论初步
第15章多项式时间归约188
15.1问题间的归约188
15.1.1优化问题和判定问题188
15.1.2问题间归约的定义189
15.2多项式时间：解决问题与完成归约190
15.2.1多项式时间可解的问题190
15.2.2多项式时间归约191
15.3习题192
第16章NP完全问题的基本概念193
16.1NP完全问题的定义193
16.1.1NP问题的定义193
16.1.2NP难与NP完全问题的定义194
16.2NP完全性证明的初步知识195
16.2.1一般问题和特例问题195
16.2.2等价的问题196
16.3习题197
附录A数学归纳法199
附录B二叉树200
参考文献201
· · · · · ·