算法基础（第5版）

Richard E. Neapolitan 美国东北伊利诺伊大学计算机科学教授，C Suite Consulting Group贝叶斯网络和统计学研究员。研究方向包括：概率与统计、人工智能、认知科学，以及贝叶斯网络和概率建模在医学、生物和金融领域的应用。他是国际知名的理论家和实践者，并受邀在世界各地发表讲演、举办研讨会。Neapolitan还是一位多产的作家，另著有《专家系统的概率推理》《学习贝叶斯网络》《当代人工智能》等专著。

《算法基础》自1997年出版以来深受读者喜爱，已经被翻译成多种语言出版，并成为世界许多高校广泛采用的算法教材之一。书中对算法设计、算法的复杂度分析和计算复杂度进行了恰如其分的介绍。作者用平实的语言和简单的符号介绍了各种抽象的数学概念，既浅显易懂，又不失严谨。为了便于读者理解和记忆，作者还提供了大量的示例，并在附录中介绍了基本的数学概念。 第5版新增了一章，介绍遗传算法和遗传编程，其中提供了理论和实践两方面的应用。此外，这一版还对练习和示例进行了全面更新，并且改进了教师资源。本书可作为本科生和研究生算法课程的教材，也可供程序员及算法分析和设计人员阅读。

第1章　算法：效率、分析和阶　　1 1.1　算法　　1 1.2　开发高效算法的重要性　　5 1.2.1　顺序查找与二分查找的对比 　　6 1.2.2　斐波那契序列　　7 1.3　算法分析　　10 1.3.1　复杂度分析　　10 1.3.2　理论应用　　14 1.3.3　正确性分析　　15 1.4　阶　　15 1.4.1　阶的直观介绍　　15 1.4.2　阶数的严谨介绍　　17 1.4.3　利用极限计算阶　　23 1.5　本书概要　　25 1.6　习题　　25 第2章　分而治之　　30 2.1　二分查找　　30 2.2　合并排序　　33 2.3　分而治之方法　　38 2.4　快速排序（分割交换排序）　　38 2.5　Strassen矩阵乘法算法　　42 2.6　大整数的算术运算　　46 2.6.1　大整数的表示：加法和其他线性时间运算　　46 2.6.2　大整数的乘法　　46 2.7　确定阈值　　50 2.8　不应使用分而治之方法的情况　　53 2.9　习题　　53 第3章　动态规划　　58 3.1　二项式系数　　58 3.2　Floyd最短路径算法　　61 3.3　动态规划与最优化问题　　66 3.4　矩阵链乘法　　67 3.5　最优二叉查找树　　73 3.6　旅行推销员问题　　79 3.7　序列对准　　84 3.8　习题　　88 第4章　贪婪方法　　92 4.1　最小生成树　　94 4.1.1　Prim算法　　96 4.1.2　Kruskal算法　　100 4.1.3　Prim算法与Kruskal算法的比较 　　 103 4.1.4　最终讨论　　103 4.2　单源最短路径的Dijkstra算法　　104 4.3　调度计划　　106 4.3.1　使系统内总时间最短　　106 4.3.2　带有最终期限的调度安排 　　108 4.4　霍夫曼编码　　112 4.4.1　前缀码　　113 4.4.2　霍夫曼算法　　114 4.5　贪婪方法与动态规划的比较：背包问题 　　 116 4.5.1　0-1背包问题的一种贪婪方法 　　116 4.5.2　部分背包问题的贪婪方法 　　118 4.5.3　0-1背包问题的动态规划方法 　　118 4.5.4　0-1背包问题动态规划算法的改进　　118 4.6　习题　　120 第5章　回溯　　124 5.1　回溯方法　　124 5.2　n皇后问题　　129 5.3　用蒙特卡洛算法估计回溯算法的效率 132 5.4　“子集之和”问题　　134 5.5　图的着色　　138 5.6　哈密顿回路问题　　141 5.7　0-1背包问题　　143 5.7.1　0-1背包问题的回溯算法 　　143 5.7.2　比较0-1背包问题的动态规划算法与回溯算法　　149 5.8　习题　　150 第6章　分支定界　　153 6.1　用0-1背包问题说明分支定界　　154 6.1.1　带有分支定界修剪的宽度优先查找　　154 6.1.2　带有分支定界修剪的最佳优先查找　　158 6.2　旅行推销员问题　　161 6.3　溯因推理（诊断）　　167 6.4　习题　　173 第7章　计算复杂度介绍：排序问题 　　175 7.1　计算复杂度　　175 7.2　插入排序和选择排序　　176 7.3　每次比较最多减少一个倒置的算法的下限　　179 7.4　再谈合并排序　　181 7.5　再谈快速排序　　185 7.6　堆排序　　186 7.6.1　堆和基本堆例程　　186 7.6.2　堆排序的一种实现　　189 7.7　合并排序、快速排序和堆排序的比较 193 7.8　仅通过键的比较进行排序的下限 　　194 7.8.1　排序算法的决策树　　194 7.8.2　最差情况下的下限　　196 7.8.3　平均情况下的下限　　197 7.9　分配排序（基数排序）　　200 7.10　习题　　203 第8章　再谈计算复杂度：查找问题 　　207 8.1　仅通过键的比较进行查找的下限 　　207 8.1.1　最差表现的下限　　209 8.1.2　平均情况下的下限　　210 8.2　插值查找　　213 8.3　树中的查找　　215 8.3.1　二叉查找树　　215 8.3.2　B树　　218 8.4　散列　　219 8.5　选择问题：对手论证　　222 8.5.1　找出最大键　　222 8.5.2　同时找出最大键和最小键 　　223 8.5.3　找出第二大的键　　227 8.5.4　查找第k小的键　　230 8.5.5　选择问题的一种概率算法 　　236 8.6　习题　　238 第9章　计算复杂度和难解性：NP 理论简介　　241 9.1　难解性　　241 9.2　再谈输入规模　　242 9.3　三类一般问题　　244 9.3.1　已经找到多项式时间算法的问题　　244 9.3.2　已经证明难解的问题　　245 9.3.3　未被证明是难解的，但也从来没有找到多项式时间算法的问题 　　245 9.4　NP理论　　245 9.4.1　集合P和NP　　247 9.4.2　NP完全问题　　250 9.4.3　NP困难、NP容易和NP等价问题 　　 256 9.5　处理NP困难问题　　259 9.5.1　旅行推销员问题的近似算法 　　259 9.5.2　装箱问题的近似算法　　263 9.6　习题　　266 第10章　遗传算法和遗传编程　　268 10.1　遗传知识复习　　268 10.2　遗传算法　　270 10.2.1　算法　　270 10.2.2　说明范例　　270 10.2.3　旅行推销员问题　　272 10.3　遗传编程　　278 10.3.1　说明范例　　279 10.3.2　人造蚂蚁　　281 10.3.3　在金融贸易中的应用283 10.4　讨论及扩展阅读　　284 10.5　习题　　284 第11章　数论算法　　286 11.1　数论回顾　　286 11.1.1　合数与质数　　286 11.1.2　最大公约数　　286 11.1.3　质因数分解　　288 11.1.4　最小公倍数　　289 11.2　计算最大公约数　　290 11.2.1　欧氏算法　　290 11.2.2　欧氏算法的扩展　　292 11.3　模运算回顾　　294 11.3.1　群论　　294 11.3.2　关于n同余　　295 11.3.3　子群　　299 11.4　模线性方程的求解　　302 11.5　计算模的幂　　305 11.6　寻找大质数　　307 11.6.1　寻找大质数　　307 11.6.2　检查一个数字是否为质数 　　307 11.7　RSA公钥密码系统　　318 11.7.1　公钥加密系统　　318 11.7.2　RSA加密系统　　319 11.8　习题　　321 第12章　并行算法简介　　324 12.1　并行体系结构　　325 12.1.1　控制机制　　326 12.1.2　地址空间的组织　　326 12.1.3　互联网络　　328 12.2　PRAM模型　　330 12.2.1　为CREW PRAM模型设计算法 　　 332 12.2.2　为CRCW PRAM模型设计算法 　　 337 12.3　习题　　339 附录A　必备数学知识回顾　　340 附录B　求解递归方程：在递归算法分析中的应用　　363 附录C　不交集的数据结构　　388 参考文献　　395