目录前言教学建议第一部分　计算模型第1章　抽象的算法设计与分析2　1.1　RAM模型的引入2　　1.1.1　计算的基本概念2　　1.1.2　计算模型的基本概念3　　1.1.3　RAM模型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　对数log n17　　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.3　Master定理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.1　Prim算法120　　10.1.1　Prim算法的正确性122　　10.1.2　Prim算法的实现125　　10.1.3　Prim算法的分析126　10.2　Kruskal算法127　　10.2.1　Kruskal算法的正确性128　　10.2.2　判断是否成环——基于并查集的实现129　　10.2.3　Kruskal算法的实现与分析133　10.3　最小生成树贪心构建框架MCE134　　10.3.1　从MCE框架的角度分析Prim算法135　　10.3.2　从MCE框架的角度分析Kruskal算法136　10.4　习题137第11章　给定源点的最短路径142　11.1　Dijkstra算法142　　11.1.1　Dijkstra算法的设计142　　11.1.2　Dijkstra算法的正确性与性能分析144　11.2　从Dijkstra算法到贪心遍历框架BestFS146　11.3　习题147第12章　贪心策略的其他应用151　12.1　相容任务调度问题151　　12.1.1　直觉的尝试151　　12.1.2　基于任务结束时间的贪心算法152　12.2　Huffman编码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.4　Floyd-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.1　NP完全问题的定义193　　16.1.1　NP问题的定义193　　16.1.2　NP难与NP完全问题的定义194　16.2　NP完全性证明的初步知识195　　16.2.1　一般问题和特例问题195　　16.2.2　等价的问题196　16.3　习题197附录A　数学归纳法199附录B　二叉树200参考文献201