本书为高等学校计算机类专业核心课程“算法设计与分析”教材. 全书以算法设计技术和分析方法为主线来组织各知识单元. 主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等. 力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术.与本书配套的有习题解答与学习指导用书、PPT电子教案以及MOOC视频教学资源等. 本书适合作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生的教学用书，也可以作为从事实际问题求解的算法设计与分析工作的科技人员的参考书.

第3版前言普通高等教育“十一五”国家级规划教材《算法设计与分析（第2版）》已经出版6年了. 在这6年里，计算机科学技术又有了新的发展，各种新的技术和算法层出不穷. 然而万变不离其宗，各种新的算法依然是建立在各种经典算法技术的基础上，最新的算法技术往往是对各种已有算法技术的组合和改进. 掌握了本书所介绍的各种经典算法技术之后，在学习理解新的算法技术时，或者在学习掌握各领域内的专门算法时，可以事半功倍. 本次修订对第2版的内容未作大的改动，除了订正一些错误，以及对文字做了进一步的精细加工外，主要在第11章中新增最后一节，介绍了姚的极小极大原理，并补充了相应的习题. 姚的极小极大原理是证明随机算法复杂度下界的主要工具，在各种随机算法模型下都有着广泛应用. 本次修订主要由刘田完成. 对广大读者提出的宝贵建议和意见，以及清华大学出版社的大力支持，我们一如既往地表示衷心的感谢！作者2022年6月于北京大学第2版前言FOREWORD作为普通高等教育“十一五”国家级规划教材，《算法设计与分析》出版已经近5年了. 在这5年的时间里，大数据、云计算、“互联网+”等新领域、新问题、新应用层出不穷，许多问题求解都离不开问题的建模和算法的设计与分析. 这次修订保持了第1版原书的基本结构、主要内容与写作特色，仍旧以算法设计技术为主线来组织素材. 考虑到线性规划与网络流问题在实践中的广泛应用，本书增加了两章(第6、7章)内容，并在第9章中增添了整数线性规划的NP完全性证明. 此外，补充了部分习题，并对原书的某些疏漏之处进行了更新. 与本书同步更新的还有教学辅导用书《算法设计与分析习题解答与学习指导（第2版）》、PPT电子课件，本书MOOC视频教学资源也将于近期完成. 本书第1章至第4章由屈婉玲完成，第5章和第8章由王捍贫完成，第6章、第7章、第9章和第10章由张立昂完成，第11章和第12章由刘田完成. 对广大读者所提出的建议和意见，我们表示衷心的感谢！作者2015年11月于北京大学第1版前言FOREWORD作为问题求解和程序设计的重要基础，“算法设计与分析”在高等学校计算机科学与技术专业的课程体系中是一门重要的必修课. 通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，也对培养学生的逻辑思维和创造性有着不可替代的作用. ACM IEEE Computing Curricula 2004与我国教育部高等学校计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范》都把该课程列入相关专业的核心课程之一. 纵观计算机学科数十年发展的历史，算法与计算复杂性理论一直是计算机科学研究的热点和活跃领域，也是获得图灵奖最多的研究领域之一. 面对计算机应用领域的大量问题，最重要的是根据问题的性质选择正确的求解思路，即找到一个好的算法. 特别在复杂的、海量信息的处理中，一个好的算法往往起着决定性的作用. 目前已经出版了许多算法教材，各有特色. 作为普通高等教育“十一五”国家级规划教材，我们在多年从事算法设计分析及计算复杂性理论的教学和研究的基础上，精心选材，完成了本书的写作. 本书的主要特点是： (1) 以算法设计技术为主线来组织素材，深入分析各种设计技术的适用范围、设计步骤、算法的正确性证明与复杂度的分析方法、算法改进的途径、局限性等. 与通常的算法与数据结构教材有所不同，本书不过多地关注实现细节，算法描述采用伪码，力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，为从事实际问题的算法设计与分析工作在理论上提供清晰的、整体的思路和方法. (2) 从对具体算法的设计技术与分析方法，自然过渡到对问题难度的分析和界定. 这里处理的不是一个具体的算法，而是对求解该问题的一大类算法的评价和分析，是对问题本身计算复杂度的估计. 基于这种分析，就能回答“求解该问题的最好算法是什么”和“它能好到什么程度”等问题，从而为选择最好的算法给出依据. 一般的算法教材涉及这方面的知识比较少，本书比较系统地介绍了一些关于问题复杂度的分析方法. (3) NP完全理论是计算复杂性理论的核心内容，其中“P≠NP”问题是21世纪最重要的数学难题之一. 计算复杂性理论关注的不仅仅是某个具体问题，而是希望了解每一个问题在计算难度的层次结构中到底处于什么位置，不同问题的难度之间有什么关系. 本书力求用清晰易懂的语言，对计算复杂性理论的核心内容和针对难解问题的处理策略加以简单的介绍，希望为从事复杂问题求解的读者提供一点帮助. (4) 本书的素材来自多年的教学积淀，选材适当，组织合理，首先引入基本概念和数学基础知识，然后进入算法设计与分析的核心内容. 在叙述中不但注意理论的严谨，也精选了大量生动有趣的例子. 每章都配有难度适当的练习，适合教学使用. 全书共10章，第1章是基础知识，介绍和算法设计与分析有关的基本概念、符号和数学知识；第2章至第5章分别阐述分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术；第6章介绍算法分析与问题的计算复杂度；第7章是NP完全性理论；第8章是近似算法；第9章是随机算法；第10章介绍处理难解问题的策略.本书既可以作为本科生教材，也可以作为研究生教材. 对于本科生教学，建议讲授第1章至第6章的全部内容，第7章至第10章可根据情况选择部分内容做一些概括性的介绍. 研究生教学可以选择第1章至第9章的全部内容，第10章可根据情况选讲. 此外，对于从事实际问题求解的研究工作者，本书也可以作为一本算法设计与分析的入门参考书.为了更好地为使用本教材的读者服务，作者正在撰写和开发与本教材配套的教学辅导书和PPT电子教案.本书的第1章至第4章由屈婉玲完成，第5章和第6章由王捍贫完成，第7章和第8章由张立昂完成，第9章和第10章由刘田完成.在编写过程中，作者参考了国内外多种版本的算法设计与分析以及计算复杂性方面的教材、论文和专著，从中吸取了一些好的思路和素材，在此一并向有关作者致谢. 特别感谢李晓明教授审阅了初稿并提出了宝贵意见，感谢清华大学出版社对本书出版的大力支持. 我们期待着广大读者，特别是使用本书的教师和学生对本书的批评、指正和建议. 作者2010年11月于北京大学