本书作者根据自己20多年的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分主要的算法技术，包括：分治法、贪心法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、生成树问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等，还介绍了问题本身的计算复杂性的概念和NP完全问题的理论等。

沈孝钧　 美国密苏里大学荣休教授。他本科毕业于清华大学，后留学美国，就读于伊利诺大学香槟分校，师从著名计算机科学家C. L. Liu教授。获得博士后，受聘于密苏里大学堪萨斯分校计算机系直至退休。在30余年的教学和研究工作中，他主要讲授计算机算法和离散数学。他研究的领域包括离散数学、几何算法、并行处理、计算机网络中的调度算法等。除会议文章外，他有数十篇论文发表在国际著名期刊上，包括SIAM Journal on Computing、Discrete Mathematics、Discrete Applied Mathematics、IEEE Journal on Selected Areas in Communications、IEEE Transactions on Networking等。

目　　录<br />前言<br />教学建议<br />第1章　概述　1<br />1.1　算法与数据结构及程序的关系　1<br />1.1.1　什么是算法　1<br />1.1.2　算法与数据结构的关系　1<br />1.1.3　算法与程序的关系　2<br />1.1.4　选择排序的例子　2<br />1.1.5　算法的伪码表示　2<br />1.2　算法复杂度分析　 3<br />1.2.1　算法复杂度的度量　3<br />1.2.2　算法复杂度与输入数据规模的关系　4<br />1.2.3　输入数据规模的度量模型　4<br />1.2.4　算法复杂度分析中的两个简化假设　5<br />1.2.5　最好情况、最坏情况和平均情况<br />的复杂度分析　5<br />1.3　函数增长渐近性态的比较　6<br />1.3.1　三种比较关系及O、、记号　6<br />1.3.2　表示算法复杂度的常用函数　7<br />1.4　问题复杂度与算法复杂度的关系　9<br />1.4.1　问题复杂度是算法复杂度的<br />下界　9<br />1.4.2　问题复杂度与最佳算法　9<br />1.4.3　易处理问题和难处理问题　9<br />习题　 10<br />第2章　分治法　11<br />2.1　分治法原理　11<br />2.1.1　二元搜索的例子　11<br />2.1.2　表示复杂度的递推关系　12<br />2.2　递推关系求解　13<br />2.2.1　替换法　13<br />2.2.2　序列求和法与递归树法　15<br />2.2.3　常用序列和公式　16<br />2.2.4　主方法求解　18<br />2.3　例题示范　19<br />习题　 20<br />第3章　基于比较的排序算法　24<br />3.1　插入排序　　24<br />3.1.1　插入排序的算法 24<br />3.1.2　插入排序算法的复杂度分析　25<br />3.1.3　插入排序的优缺点　26<br />3.2　合并排序　26<br />3.2.1　合并算法及其复杂度　26<br />3.2.2　合并排序的算法及其复杂度　27<br />3.2.3　合并排序的优缺点　29<br />3.3　堆排序　 30<br />3.3.1　堆的数据结构　30<br />3.3.2　堆的修复算法及其复杂度　31<br />3.3.3　为输入数据建堆　32<br />3.3.4　堆排序算法　33<br />3.3.5　堆排序算法的复杂度　34<br />3.3.6　堆排序算法的优缺点　35<br />3.3.7　堆用作优先队列　35<br />3.4　快排序　36<br />3.4.1　快排序算法　36<br />3.4.2　快排序算法最坏情况复杂度　39<br />3.4.3　快排序算法平均情况复杂度　40<br />3.4.4　快排序算法最好情况复杂度　41<br />3.4.5　快排序算法的优缺点　42<br />习题　 42<br />第4章　不基于比较的排序算法　46<br />4.1　比较排序的下界　46<br />4.1.1　决策树模型及排序最坏情况下界　46<br />4.1.2　二叉树的外路径总长与排序平均<br />情况下界　 49<br />4.1.3　二叉树的全路径总长与堆排序<br />最好情况下界　 51<br />4.2　不基于比较的线性时间排序算法　54<br />4.2.1　计数排序　 54<br />4.2.2　基数排序　57<br />4.2.3　桶排序　58<br />习题　60<br />第5章　中位数和任一顺序数的选择　63<br />5.1　问题定义　63<br />5.2　最大数和最小数的选择　63<br />5.2.1　最大和最小顺序数的选择算法及<br />其复杂度　64<br />5.2.2　同时找出最大数和最小数的<br />算法　65<br />5.3　线性时间找出任一顺序数的算法　66<br />5.3.1　最坏情况复杂度为O(n)的算法 66 <br />5.3.2　平均情况复杂度为O(n)的算法　 68<br />5.4　找出k个最大顺序数的算法　69<br />5.4.1　一个理论联系实际的问题　69 <br />5.4.2　利用堆来找k个最大顺序数的<br />算法　 70<br />5.4.3　利用锦标赛树来找k个最大顺序数<br />的算法　70<br />习题　 71<br />第6章　动态规划　 73<br />6.1　动态规划的基本原理　73<br />6.2　矩阵连乘问题　 75<br />6.2.1　定义子问题　75<br />6.2.2　归纳公式　77<br />6.2.3　算法伪码和例子　78<br />6.3　最长公共子序列问题　81<br />6.3.1　定义子问题　81<br />6.3.2　归纳公式　82<br />6.3.3　算法伪码和例子　82<br />6.4　最佳二元搜索树问题　84<br />6.4.1　定义子问题和归纳公式　85<br />6.4.2　算法伪码和例子　87<br />6.5　多级图及其应用　 89<br />6.6　最长递增子序列问题　92<br />6.6.1　定义子问题　93<br />6.6.2　归纳公式　93<br />6.6.3　算法伪码和例子　93<br />习题　 95<br />第7章　贪心算法　 103<br />7.1　最佳邮局设置问题　103<br />7.2　一个简单的最佳活动安排问题　105<br />7.3　其他最佳活动安排问题　106<br />7.3.1　两个大礼堂的最佳活动安排<br />问题　106<br />7.3.2　等长时间的活动的最佳安排<br />问题　109<br />7.4　哈夫曼编码问题　112<br />7.4.1　前缀码　112<br />7.4.2　最佳前缀码——哈夫曼编码　114<br />7.5　最佳加油计划问题　118<br />7.5.1　最佳加油计划问题的描述　118<br />7.5.2　贪心算法的基本思路　119<br />7.5.3　贪心算法的伪码　120<br />习题　 121<br />第8章　图的周游算法　 128<br />8.1　图的表示　128<br />8.1.1　邻接表　129<br />8.1.2　邻接矩阵 129<br />8.2　广度优先搜索及应用　130<br />8.2.1　广度优先搜索策略　130<br />8.2.2　广度优先搜索算法及距离树　131<br />8.2.3　无向图的二着色问题　133<br />8.3　深度优先搜索及应用　136<br />8.3.1　深度优先搜索的策略　136<br />8.3.2　深度优先搜索算法和深度优先<br />搜索树　137<br />8.3.3　深度优先搜索算法举例和图中<br />边的分类　140<br />8.3.4　拓扑排序　141<br />8.3.5　无回路有向图中最长路径问题<br />及应用　144<br />8.3.6　有向图的强连通分支的分解　146<br />8.3.7　无向图的双连通分支的分解　150<br />习题　 156<br />第9章　图的最小支撑树　 162<br />9.1　计算最小支撑树的一个通用的<br />贪心算法策略　163<br />9.2　Kruskal 算法　165<br />9.3　Prim 算法　168<br />习题　 173<br />第10章　单源最短路径　178<br />10.1　Dijkstra 算法　179<br />10.2　Bellman-Ford 算法　184<br />习题　 189<br />第11章　网络流　192<br />11.1　网络模型和最大网络流问题　192<br />11.2　网络中的流与割的关系　196<br />11.2.1　网络中的割及其容量　197<br />11.2.2　剩余网络和增广路径　198<br />11.2.3　最大流最小割定理　201<br />11.3　Ford-Fulkerson 算法　202<br />11.3.1　Ford-Fulkerson 的通用算法　202<br />11.3.2　Edmonds-Karp 算法　204<br />11.3.3　Dinic 算法　207<br />11.4　 二部图的匹配问题　210<br />11.4.1　0-1网络的最大流问题　211<br />11.4.2　用网络流求二部图的最大匹配<br />的算法　212<br />11.4.3　Philip Hall 婚配定理　214<br />11.4.4　Birkhoff-von Neumann 定理　215<br />11.5　推进-重标号算法简介　217<br />11.5.1　预流和高度函数　217<br />11.5.2　在剩余网络中对顶点的两个<br />操作　219<br />11.5.3　推进-重标号算法的初始化　220<br />11.5.4　推进-重标号的通用算法　220<br />11.5.5　推进-重标号的通用算法的复杂<br />度分析　223<br />习题　 224<br />第12章　计算几何基础　228<br />12.1　平面线段及相互关系　228<br />12.1.1　向量的点积和叉积　229<br />12.1.2　平面线段的相互关系　230<br />12.2　平扫线技术和线段相交的确定　233<br />12.2.1　平扫线的状态和事件点　234<br />12.2.2　用平扫线确定线段相交的<br />算法　235<br />12.3　平面点集的凸包　237<br />12.3.1　Graham 扫描法　238<br />12.3.2　Jarvis行进法 243<br />12.4　最近点对问题　245<br />12.4.1　预备工作和分治法的底　245<br />12.4.2　分治法的分　246<br />12.4.3　分治法的合　247<br />12.4.4　分治法的伪码　248<br />习题　 249<br />第13章　字符串匹配　252<br />13.1　一个朴素的字符串匹配算法　252<br />13.2　Rabin-Karp 算法　253<br />13.3　基于有限状态自动机的匹配<br />算法　255<br />13.3.1　有限状态自动机简介　255<br />13.3.2　字符串匹配用的自动机　256<br />13.3.3　基于有限状态自动机的匹配<br />算法 259<br />13.4　Knuth-Morris-Pratt (KMP) 算法　260<br />13.4.1　模式的前缀函数　260<br />13.4.2　基于前缀函数的KMP 算法　263<br />习题　 265<br />第14章　NP 完全问题　266<br />14.1　预备知识　267<br />14.1.1　图灵机　267<br />14.1.2　符号集和编码对计算复杂度的<br />影响　268<br />14.1.3　判断型问题和优化型问题及其<br />关系　268<br />14.1.4　判断型问题的形式语言表示　270<br />14.1.5　多项式关联和多项式归约　271<br />14.2　P和NP语言类　272<br />14.2.1　非确定图灵机和NP语言类　273<br />14.2.2　多项式检验算法和NP类语言的<br />关系　274<br />14.3　NPC语言类和NPC问题　276<br />14.3.1　第一个NPC问题　277<br />14.3.2　若干著名NPC问题的证明　281<br />习题　 295<br />第15章　近似算法　301<br />15.1　近似算法的性能评价　301<br />15.2　顶点覆盖问题　302<br />15.3　货郎担问题　303<br />15.3.1　满足三角不等式的货郎担<br />问题　304<br />15.3.2　无三角不等式关系的一般<br />货郎担问题　307<br />15.4　集合覆盖问题　307<br />15.5　MAX-3-SAT问题　310<br />15.6　加权的顶点覆盖问题　311<br />15.7　子集和问题　313<br />15.7.1　一个保证最优解的指数型算法　313<br />15.7.2　子集和问题的一个完全多项式<br />近似机制　314<br />*15.8　鸿沟定理和不可近似性　317<br />15.8.1　鸿沟定理　318<br />15.8.2　任务均匀分配问题　319<br />习题　 321<br />第16章　穷举搜索　324<br />16.1　问题及方法的描述　324<br />16.2　回溯法　326<br />16.2.1　回溯法的通用算法　326<br />16.2.2　n皇后问题　327<br />16.2.3　子集和问题　328<br />16.2.4　回溯法的效率估计　330<br />16.3　分支限界法　331<br />16.3.1　分支限界法解n皇后问题　332<br />16.3.2　0/1背包问题　334<br />16.4　博弈树和α-β剪枝　340<br />16.4.1　博弈树及其评估的方法　340<br />16.4.2　α-β剪枝法　344<br />习题　 346<br />第17章　平摊分析和斐波那契堆　348<br />17.1　平摊分析的常用方法　349<br />17.1.1　聚集法　349<br />17.1.2　记账法　350<br />17.1.3　势能法　352<br />17.2　动态表格　353<br />17.2.1　只允许扩张的动态表格　353<br />17.2.2　扩张和收缩都有的动态表格　355<br />17.3　斐波那契堆　358<br />17.3.1　斐波那契堆的构造　358<br />17.3.2　可合并堆的操作　360<br />17.3.3　减小一个关键字和删除任一结点<br />的操作　365<br />17.3.4　最大度数的界　367<br />习题　 369<br />附录A　红黑树　372<br />附录B　用于分离集合操作的数据<br />结构　385<br />参考文献　397<br />