（已有44条评价）
基本信息
- 原书名：Introduction to Algorithms
- 原出版社： The MIT Press; third edition edition
- 作者： (美)Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein
- 译者： 殷建平 徐云 王刚 刘晓光 苏明 邹恒明 王宏志
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111407010
- 上架时间：2012-12-12
- 出版日期：2013 年1月
- 开本：16开
- 页码：780
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
教材
【插图】
编辑推荐
MIT四大名师联手铸就，影响全球千万程序员的“算法圣经”!国内外千余所高校采用！
内容简介
书籍
计算机书籍
在有关算法的书中，有一些叙述非常严谨，但不够全面；另一些涉及了大量的题材，但又缺乏严谨性。本书将严谨性和全面性融为一体，深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。全书各章自成体系，可以作为独立的学习单元；算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂；说明和解释力求浅显易懂，不失深度和数学严谨性。
《算法导论(原书第3版)》选材经典、内容丰富、结构合理、逻辑清晰，对本科生的数据结构课程和研究生的算法课程都是非常实用的教材，在IT专业人员的职业生涯中，本书也是一本案头必备的参考书或工程实践手册。
第3版的主要变化：
新增了van Emde Boas树和多线程算法，并且将矩阵基础移至附录。
修订了递归式（现在称为“分治策略”）那一章的内容，更广泛地覆盖分治法。
移除两章很少讲授的内容：二项堆和排序网络。
修订了动态规划和贪心算法相关内容。
流网络相关材料现在基于边上的全部流。
由于关于矩阵基础和Strassen算法的材料移到了其他章，矩阵运算这一章的内容所占篇幅更小。
修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。
新增100道练习和28道思考题，还更新并补充了参考文献。
计算机书籍
在有关算法的书中，有一些叙述非常严谨，但不够全面；另一些涉及了大量的题材，但又缺乏严谨性。本书将严谨性和全面性融为一体，深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。全书各章自成体系，可以作为独立的学习单元；算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂；说明和解释力求浅显易懂，不失深度和数学严谨性。
《算法导论(原书第3版)》选材经典、内容丰富、结构合理、逻辑清晰，对本科生的数据结构课程和研究生的算法课程都是非常实用的教材，在IT专业人员的职业生涯中，本书也是一本案头必备的参考书或工程实践手册。
第3版的主要变化：
新增了van Emde Boas树和多线程算法，并且将矩阵基础移至附录。
修订了递归式（现在称为“分治策略”）那一章的内容，更广泛地覆盖分治法。
移除两章很少讲授的内容：二项堆和排序网络。
修订了动态规划和贪心算法相关内容。
流网络相关材料现在基于边上的全部流。
由于关于矩阵基础和Strassen算法的材料移到了其他章，矩阵运算这一章的内容所占篇幅更小。
修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。
新增100道练习和28道思考题，还更新并补充了参考文献。
作译者
Thomas H. Cormen （托马斯?科尔曼） 达特茅斯学院计算机科学系教授、系主任。目前的研究兴趣包括：算法工程、并行计算、具有高延迟的加速计算。他分别于1993年、1986年获得麻省理工学院电子工程和计算机科学博士、硕士学位，师从Charles E. Leiserson教授。由于他在计算机教育领域的突出贡献，Cormen教授荣获2009年ACM杰出教员奖。
Charles E. Leiserson（查尔斯?雷瑟尔森）麻省理工学院计算机科学与电气工程系教授，Margaret MacVicar Faculty Fellow。他目前主持MIT超级计算技术研究组，并是MIT计算机科学和人工智能实验室计算理论研究组的成员。他的研究兴趣集中在并行和分布式计算的理论原理，尤其是与工程现实相关的技术研究。Leiserson教授拥有卡内基?梅隆大学计算机科学博士学位，还是ACM、IEEE和SIAM的会士。
Ronald L. Rivest （罗纳德?李维斯特）现任麻省理工学院电子工程和计算机科学系安德鲁与厄纳?维特尔比（Andrew and Erna Viterbi）教授。他是MIT计算机科学和人工智能实验室的成员，并领导着其中的信息安全和隐私中心。他1977年从斯坦福大学获得计算机博士学位，主要从事密码安全、计算机安全算法的研究。他和Adi Shamir和Len Adleman一起发明了RSA公钥算法，这个算法在信息安全中获得最大的突破，这一成果也使他和Shamir、Adleman一起得到2002年ACM图灵奖。他现在担任国家密码学会的负责人。
Clifford Stein（克利福德?斯坦）哥伦比亚大学计算机科学系和工业工程与运筹学系教授，他还是工业工程与运筹学系的系主任。在加入哥伦比亚大学大学之前，他在达特茅斯学院计算机科学系任教9年。Stein教授拥有MIT硕士和博士学位。他的研究兴趣包括：算法的设计与分析，组合优化、运筹学、网络算法、调度、算法工程和生物计算。
Charles E. Leiserson（查尔斯?雷瑟尔森）麻省理工学院计算机科学与电气工程系教授，Margaret MacVicar Faculty Fellow。他目前主持MIT超级计算技术研究组，并是MIT计算机科学和人工智能实验室计算理论研究组的成员。他的研究兴趣集中在并行和分布式计算的理论原理，尤其是与工程现实相关的技术研究。Leiserson教授拥有卡内基?梅隆大学计算机科学博士学位，还是ACM、IEEE和SIAM的会士。
Ronald L. Rivest （罗纳德?李维斯特）现任麻省理工学院电子工程和计算机科学系安德鲁与厄纳?维特尔比（Andrew and Erna Viterbi）教授。他是MIT计算机科学和人工智能实验室的成员，并领导着其中的信息安全和隐私中心。他1977年从斯坦福大学获得计算机博士学位，主要从事密码安全、计算机安全算法的研究。他和Adi Shamir和Len Adleman一起发明了RSA公钥算法，这个算法在信息安全中获得最大的突破，这一成果也使他和Shamir、Adleman一起得到2002年ACM图灵奖。他现在担任国家密码学会的负责人。
Clifford Stein（克利福德?斯坦）哥伦比亚大学计算机科学系和工业工程与运筹学系教授，他还是工业工程与运筹学系的系主任。在加入哥伦比亚大学大学之前，他在达特茅斯学院计算机科学系任教9年。Stein教授拥有MIT硕士和博士学位。他的研究兴趣包括：算法的设计与分析，组合优化、运筹学、网络算法、调度、算法工程和生物计算。
目录
《算法导论(原书第3版)》
出版者的话
译者序
前言
第一部分 基础知识
第1章 算法在计算中的作用3
1.1 算法3
1.2 作为一种技术的算法6
思考题8
本章注记8
第2章 算法基础9
2.1 插入排序9
2.2 分析算法13
2.3 设计算法16
2.3.1 分治法16
2.3.2 分析分治算法20
思考题22
本章注记24
第3章 函数的增长25
3.1 渐近记号25
出版者的话
译者序
前言
第一部分 基础知识
第1章 算法在计算中的作用3
1.1 算法3
1.2 作为一种技术的算法6
思考题8
本章注记8
第2章 算法基础9
2.1 插入排序9
2.2 分析算法13
2.3 设计算法16
2.3.1 分治法16
2.3.2 分析分治算法20
思考题22
本章注记24
第3章 函数的增长25
3.1 渐近记号25
译者序
我从1994年开始每年都为本科生讲授《算法设计与分析》课程，粗略地统计一下发现至今已有5000余名各类学生听过该课。算法的重要性不言而喻，因为不管新概念、新方法、新理论如何引人注目，信息的表示与处理总是计算技术（含软件、硬件、应用、网络、安全、智能等）永恒的主题。信息处理的核心是算法，在大数据时代，设计高效的算法显得格外重要。
当初，为了教好这门基础必修课，提高教学质量，我觉得应该从教学内容的改革入手，具体来说，采用的教材应该与国际一流大学接轨。1997年访美期间，在Stanford大学了解到他们采用的教材是Thomas H. Cormen等编著的《Introduction to Algorithms》，于是从Stanford书店买了一本带回来，从第二年开始便改用该书作教材。至今，15年过去了，我们一直追随其变迁，从第二版到第三版。教学实践证明它确实是一本好教材，难怪世界范围内包括MIT、CMU、Stanford、UCB、Cornell、UIUC等国际国内名校在内的1000余所大学都一直用它作为教材或教学参考书，也难怪它印数巨大且在《高引用计算机科学文献》（《Most Cited Computer Science Citations》）一览表中名列前茅。
这是一本有1200多页的厚书，教学内容非常丰富，不但涵盖了典型算法、算法分析、算法设计方法和NP完全等内容，而且还包括数据结构，甚至高级数据结构的介绍。后者可作为国内《数据结构》课程的教材或教学参考资料。在学时有限的情况下，要在本科阶段教完前者的所有内容也是困难的，故要做取舍。好在该书的各个章节相对独立且难度由浅入深，我们的做法是将相对容易的一般的入门性内容留在本科阶段，而将相对难的专门的较深入的内容并入研究生课程《算法及复杂性》或《计算复杂性》。除本校外，本人就曾多次应邀在兰州大学、湖南大学和浙江师范大学等院校为研究生讲授过这些内容。其实该书也适合希望增强自身程序设计能力和程序评判能力的广大应用计算技术的社会公众，特别是参加信息学奥林匹克竞赛和ACM程序设计竞赛的选手及其教练员。
教学过程中我们发现该书具有以下特点：（1）选材与时俱进，具有实用性且能引起读者的兴趣。该书中研究的许多问题都是当前现实应用中的关键技术问题。（2）采用伪码描述算法，既简洁易懂又便于抓住本质，再配上丰富的插图来描述和解释算法的执行过程使得教学内容更加通俗，便于自学。（3）对算法正确性和复杂性的分析比较全面，既有严密的论证，又有直观的解释。（4）既有结论性知识的介绍，也有逐步导出结论的研究过程的展示。（5）丰富的练习题和思考题使得及时检验所学知识掌握情况和进一步拓展学习内容成为可能。
同时，我们也注意到：学生们总是反映看英文版教材速度太慢，所以他们总是想方设法再找一本中译版来阅读。正是这样的背景，在第三版的《Introduction to Algorithms》出版后，我们应机械工业出版社编辑的邀请，启动了长久的翻译工程，先后参加翻译工作的老师有：国防科学技术大学的殷建平教授（翻译第1~3章）、中国科学技术大学的徐云教授（翻译第10~14章、第18~21章和第27章）、南开大学的王刚教授（翻译第4章和第15~17章）、南开大学的刘晓光教授（翻译第6~9章）、南开大学的苏明副研究员（翻译第5章和第28~30章）、上海交通大学的邹恒明教授（翻译第22~26章）、哈尔滨工业大学的王宏志副教授（翻译第31~35章和附录部分）。由于水平有限且工作量巨大，译文中一定存在许多不足，在此敬请各位同行专家学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱：algorithms@hzbook.com。在整个工程即将完成之际，我们特别要感谢机械工业出版社的温莉芳老师和王春华老师，没有你们的信任、耐心和支持整个翻译工作不可能完成。
殷建平
2012年11月于长沙
当初，为了教好这门基础必修课，提高教学质量，我觉得应该从教学内容的改革入手，具体来说，采用的教材应该与国际一流大学接轨。1997年访美期间，在Stanford大学了解到他们采用的教材是Thomas H. Cormen等编著的《Introduction to Algorithms》，于是从Stanford书店买了一本带回来，从第二年开始便改用该书作教材。至今，15年过去了，我们一直追随其变迁，从第二版到第三版。教学实践证明它确实是一本好教材，难怪世界范围内包括MIT、CMU、Stanford、UCB、Cornell、UIUC等国际国内名校在内的1000余所大学都一直用它作为教材或教学参考书，也难怪它印数巨大且在《高引用计算机科学文献》（《Most Cited Computer Science Citations》）一览表中名列前茅。
这是一本有1200多页的厚书，教学内容非常丰富，不但涵盖了典型算法、算法分析、算法设计方法和NP完全等内容，而且还包括数据结构，甚至高级数据结构的介绍。后者可作为国内《数据结构》课程的教材或教学参考资料。在学时有限的情况下，要在本科阶段教完前者的所有内容也是困难的，故要做取舍。好在该书的各个章节相对独立且难度由浅入深，我们的做法是将相对容易的一般的入门性内容留在本科阶段，而将相对难的专门的较深入的内容并入研究生课程《算法及复杂性》或《计算复杂性》。除本校外，本人就曾多次应邀在兰州大学、湖南大学和浙江师范大学等院校为研究生讲授过这些内容。其实该书也适合希望增强自身程序设计能力和程序评判能力的广大应用计算技术的社会公众，特别是参加信息学奥林匹克竞赛和ACM程序设计竞赛的选手及其教练员。
教学过程中我们发现该书具有以下特点：（1）选材与时俱进，具有实用性且能引起读者的兴趣。该书中研究的许多问题都是当前现实应用中的关键技术问题。（2）采用伪码描述算法，既简洁易懂又便于抓住本质，再配上丰富的插图来描述和解释算法的执行过程使得教学内容更加通俗，便于自学。（3）对算法正确性和复杂性的分析比较全面，既有严密的论证，又有直观的解释。（4）既有结论性知识的介绍，也有逐步导出结论的研究过程的展示。（5）丰富的练习题和思考题使得及时检验所学知识掌握情况和进一步拓展学习内容成为可能。
同时，我们也注意到：学生们总是反映看英文版教材速度太慢，所以他们总是想方设法再找一本中译版来阅读。正是这样的背景，在第三版的《Introduction to Algorithms》出版后，我们应机械工业出版社编辑的邀请，启动了长久的翻译工程，先后参加翻译工作的老师有：国防科学技术大学的殷建平教授（翻译第1~3章）、中国科学技术大学的徐云教授（翻译第10~14章、第18~21章和第27章）、南开大学的王刚教授（翻译第4章和第15~17章）、南开大学的刘晓光教授（翻译第6~9章）、南开大学的苏明副研究员（翻译第5章和第28~30章）、上海交通大学的邹恒明教授（翻译第22~26章）、哈尔滨工业大学的王宏志副教授（翻译第31~35章和附录部分）。由于水平有限且工作量巨大，译文中一定存在许多不足，在此敬请各位同行专家学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱：algorithms@hzbook.com。在整个工程即将完成之际，我们特别要感谢机械工业出版社的温莉芳老师和王春华老师，没有你们的信任、耐心和支持整个翻译工作不可能完成。
殷建平
2012年11月于长沙
前言
在计算机出现之前，就有了算法。现在有了计算机，就需要更多的算法，算法是计算的核心。
本书提供了对当代计算机算法研究的一个全面、综合的介绍。书中给出了多个算法，并对它们进行了较为深入的分析，使得这些算法的设计和分析易于被各个层次的读者所理解。我们力求在不牺牲分析的深度和数学严密性的前提下，给出深入浅出的说明。
书中每一章都给出了一个算法、一种算法设计技术、一个应用领域或一个相关的主题。算法是用英语和一种“伪代码”来描述的，任何有一点程序设计经验的人都能看得懂。书中给出了244幅图，说明各个算法的工作过程。我们强调将算法的效率作为一种设计标准，对书中的所有算法，都给出了关于其运行时间的详细分析。
本书主要供本科生和研究生的算法或数据结构课程使用。因为书中讨论了算法设计中的工程问题及其数学性质，所以，本书也可以供专业技术人员自学之用。
本书是第3版。在这个版本里，我们对全书进行了更新，包括新增了若干章、修订了伪代码等。
致使用本书的教师
本书的设计目标是全面、适用于多种用途。它可用于若干课程，从本科生的数据结构课程到研究生的算法课程。由于书中给出的内容比较多，只讲一学期一般讲不完，因此，教师们应该将本书看成是一种“缓存区”或“瑞典式自助餐”，从中挑选出能最好地支持自己希望教授的课程的内容。
教师们会发现，要围绕自己所需的各个章节来组织课程是比较容易的。书中的各章都是相对独立的，因此，你不必担心意想不到的或不必要的各章之间的依赖关系。每一章都是以节为单位，内容由易到难。如果将本书用于本科生的课程，可以选用每一章的前面几节内容；用于研究生的课程中，则可以完整地讲授每一章。
全书包含957道练习和158道思考题。每一节结束时给出练习，每一章结束时给出思考题。练习一般比较短，用于检查学生对书中内容的基本掌握情况。有一些是简单的自查性练习，有一些则要更充实，可以作为家庭作业布置给学生。每一章后的思考题都是一些叙述较为详细的实例研究，它们常常会介绍一些新的知识。一般来说，这些思考题都会包含几个小问题，引导学生逐步得到问题的解。
鉴于本书前几版使用的反馈，我们在本书配套网站上公布了其中一些练习和思考题的答案（但不是全部），网址为http://mitpress.mit.edu/algorithms/。我们会定期更新这些答案，因此需要教师每次授课前都到这个网站上来查看。
在那些不太适合本科生、更适合研究生的章节和练习前面，都加上了星号()。带星号的章节也不一定就比不带星号的更难，但可能要求了解更多的数学知识。类似地，带星号的练习可能要求有更好的数学背景或创造力。
致使用本书的学生
希望本教材能为学生们提供关于算法这一领域的有趣介绍。我们力求使书中给出的每一个算法都易于理解和有趣。为了在同学们遇到不熟悉或比较困难的算法时提供帮助，我们逐个步骤地描述每一个算法。此外，为了便于大家理解书中对算法的分析，对于其中所需的数学知识，我们给出了详细的解释。如果对某一主题已经有所了解，会发现根据书中各章的编排顺序，可以跳过一些介绍性的小节，直接阅读更高级的内容。
本书是一本大部头著作，读者所修的课程可能只讲授其中的一部分。我们试图使它能成为一本现在对读者有用的教材，将来在读者的职业生涯中，也能成为一本案头的数学参考书或工程实践手册。
阅读本书需要哪些预备知识呢?
读者需要有一些程序设计方面的经验，尤其需要理解递归过程和简单的数据结构，如数组和链表。
读者应该能较为熟练地利用数学归纳法进行证明。书中有一些内容要求读者具备初等微积分方面的知识。除此之外，本书的第一部分和第八部分将介绍读者需要用到的所有数学技巧。
我们收到读者的反馈，他们强烈希望提供练习和思考题的答案，为此，我们在http://mitpress.mit.edu/algorithms/这个网站上给出了少数练习和思考题的答案，读者可以根据我们的答案来检验自己的解答。
致使用本书的专业技术人员
本书涉及的主题非常广泛，因而是一本很好的算法参考手册。因为每一章都是相对独立的，所以读者可以重点查阅自己感兴趣的主题。
本书提供了对当代计算机算法研究的一个全面、综合的介绍。书中给出了多个算法，并对它们进行了较为深入的分析，使得这些算法的设计和分析易于被各个层次的读者所理解。我们力求在不牺牲分析的深度和数学严密性的前提下，给出深入浅出的说明。
书中每一章都给出了一个算法、一种算法设计技术、一个应用领域或一个相关的主题。算法是用英语和一种“伪代码”来描述的，任何有一点程序设计经验的人都能看得懂。书中给出了244幅图，说明各个算法的工作过程。我们强调将算法的效率作为一种设计标准，对书中的所有算法，都给出了关于其运行时间的详细分析。
本书主要供本科生和研究生的算法或数据结构课程使用。因为书中讨论了算法设计中的工程问题及其数学性质，所以，本书也可以供专业技术人员自学之用。
本书是第3版。在这个版本里，我们对全书进行了更新，包括新增了若干章、修订了伪代码等。
致使用本书的教师
本书的设计目标是全面、适用于多种用途。它可用于若干课程，从本科生的数据结构课程到研究生的算法课程。由于书中给出的内容比较多，只讲一学期一般讲不完，因此，教师们应该将本书看成是一种“缓存区”或“瑞典式自助餐”，从中挑选出能最好地支持自己希望教授的课程的内容。
教师们会发现，要围绕自己所需的各个章节来组织课程是比较容易的。书中的各章都是相对独立的，因此，你不必担心意想不到的或不必要的各章之间的依赖关系。每一章都是以节为单位，内容由易到难。如果将本书用于本科生的课程，可以选用每一章的前面几节内容；用于研究生的课程中，则可以完整地讲授每一章。
全书包含957道练习和158道思考题。每一节结束时给出练习，每一章结束时给出思考题。练习一般比较短，用于检查学生对书中内容的基本掌握情况。有一些是简单的自查性练习，有一些则要更充实，可以作为家庭作业布置给学生。每一章后的思考题都是一些叙述较为详细的实例研究，它们常常会介绍一些新的知识。一般来说，这些思考题都会包含几个小问题，引导学生逐步得到问题的解。
鉴于本书前几版使用的反馈，我们在本书配套网站上公布了其中一些练习和思考题的答案（但不是全部），网址为http://mitpress.mit.edu/algorithms/。我们会定期更新这些答案，因此需要教师每次授课前都到这个网站上来查看。
在那些不太适合本科生、更适合研究生的章节和练习前面，都加上了星号()。带星号的章节也不一定就比不带星号的更难，但可能要求了解更多的数学知识。类似地，带星号的练习可能要求有更好的数学背景或创造力。
致使用本书的学生
希望本教材能为学生们提供关于算法这一领域的有趣介绍。我们力求使书中给出的每一个算法都易于理解和有趣。为了在同学们遇到不熟悉或比较困难的算法时提供帮助，我们逐个步骤地描述每一个算法。此外，为了便于大家理解书中对算法的分析，对于其中所需的数学知识，我们给出了详细的解释。如果对某一主题已经有所了解，会发现根据书中各章的编排顺序，可以跳过一些介绍性的小节，直接阅读更高级的内容。
本书是一本大部头著作，读者所修的课程可能只讲授其中的一部分。我们试图使它能成为一本现在对读者有用的教材，将来在读者的职业生涯中，也能成为一本案头的数学参考书或工程实践手册。
阅读本书需要哪些预备知识呢?
读者需要有一些程序设计方面的经验，尤其需要理解递归过程和简单的数据结构，如数组和链表。
读者应该能较为熟练地利用数学归纳法进行证明。书中有一些内容要求读者具备初等微积分方面的知识。除此之外，本书的第一部分和第八部分将介绍读者需要用到的所有数学技巧。
我们收到读者的反馈，他们强烈希望提供练习和思考题的答案，为此，我们在http://mitpress.mit.edu/algorithms/这个网站上给出了少数练习和思考题的答案，读者可以根据我们的答案来检验自己的解答。
致使用本书的专业技术人员
本书涉及的主题非常广泛，因而是一本很好的算法参考手册。因为每一章都是相对独立的，所以读者可以重点查阅自己感兴趣的主题。
