基本信息
- 原书名：Algorithms Unlocked
- 作者： (美)托马斯 H.科尔曼（Thomas H.Cormen）
- 译者： 王宏志
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111520764
- 上架时间：2015-12-11
- 出版日期：2016 年1月
- 开本：16开
- 页码：232
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
教材
编辑推荐
《算法导论》第一作者托马斯 H.科尔曼面向大众读者的算法著作
理解计算机科学中关键算法的简明读本，帮助您开启算法之门
内容简介
作译者
作者：（美国）托马斯 H.科尔曼（Thomas H.Cormen） 译者：王宏志
目录
出版者的话
译者序
前言
第1章什么是算法以及为什么应该关注算法1
1.1正确性2
1.2资源利用3
1.3针对非计算机专业人士的计算机算法5
1.4针对计算机专业人士的计算机算法6
1.5拓展阅读7
第2章如何描述和评估计算机算法9
2.1如何描述计算机算法9
2.2如何描述运行时间16
2.3循环不变式19
2.4递归21
2.5拓展阅读23
第3章排序算法和查找算法24
3.1二分查找26
3.2选择排序31
3.3插入排序34
3.4归并排序38
译者序
前言
第1章什么是算法以及为什么应该关注算法1
1.1正确性2
1.2资源利用3
1.3针对非计算机专业人士的计算机算法5
1.4针对计算机专业人士的计算机算法6
1.5拓展阅读7
第2章如何描述和评估计算机算法9
2.1如何描述计算机算法9
2.2如何描述运行时间16
2.3循环不变式19
2.4递归21
2.5拓展阅读23
第3章排序算法和查找算法24
3.1二分查找26
3.2选择排序31
3.3插入排序34
3.4归并排序38
译者序
Algorithms Unlocked
算法设计与分析是计算机科学的核心内容之一，算法设计与分析的能力也成为计算机科学从业者最重要的基本功之一，因而“算法设计与分析”是计算机专业学生的重要专业课程。尽管算法设计与分析很重要，但这门课程对许多读者来说稍显“高冷”，主要表现为其内容抽象、覆盖范围广、需要的数学基础多，因而学习算法设计与分析仿若攀登一座费时费力的高山。
针对这种情况，计算机领域的大牛Thomas Cormen出手了。他撰写了此书作为面向算法设计与分析初学者的入门书籍。本书有着如下几个鲜明的特点。
第一，本书仅仅使用了有限的数学知识。对于很多算法初学者来说，阻碍其学习的很重要的一个绊脚石就是算法设计与分析中涉及的大量数学知识，覆盖了概率论、代数、数学分析、图论等多个方面，而本书不需要读者具备这些方面的深入知识，为算法初学者提供了一条入门的捷径。
第二，本书语言通俗生动，并且把算法和现实中的问题紧密连接，避免出现大量算法分析细节。一方面，让算法真正成为生活中的一种思维方式，让读者深入了解算法思想的实际用途；另一方面，对于很多应用背后的算法知识，让读者在“知其然”的同时“知其所以然”。
第三，本书覆盖范围广，在200多页的篇幅中覆盖了图论算法、字符串算法、密码算法、数据压缩算法，甚至NP完全问题和不可判定问题，使读者可在最短的时间内掌握多种应用中不同的算法。
特别值得一提的是，本书的作者Thomas Cormen也是算法设计与分析方面的经典教材《算法导论》的作者之一，译者有幸参与了该书的翻译工作。《算法导论》是一本内容深入的算法设计与分析方面的大部头教材，而本书则可以看作是《算法导论》的一个薄薄的入门版本，通过阅读本书，读者可以用最短的时间轻松地窥见算法设计与分析的门径，奠定学习“算法设计与分析”课程的基础。
在本书英文版出版以后，译者应机械工业出版社的邀请开始了本书的翻译工作。由于水平有限且时间紧张，译文中一定存在许多不足，在此敬请各位同行、专家、学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱wangzh@hit.edu.cn，以改进本书的译本。
最后，我要感谢哈尔滨工业大学的孔欣欣同学在翻译过程中进行的辅助翻译工作。在完成译稿之后，我的爱人黎玲利博士阅读全文并提出了很多有益的意见，在此也表示感谢。同时感谢机械工业出版社的姚蕾编辑和朱劼编辑，由于她们的信任和支持，本书的翻译工作才得以顺利进行。
王宏志
算法设计与分析是计算机科学的核心内容之一，算法设计与分析的能力也成为计算机科学从业者最重要的基本功之一，因而“算法设计与分析”是计算机专业学生的重要专业课程。尽管算法设计与分析很重要，但这门课程对许多读者来说稍显“高冷”，主要表现为其内容抽象、覆盖范围广、需要的数学基础多，因而学习算法设计与分析仿若攀登一座费时费力的高山。
针对这种情况，计算机领域的大牛Thomas Cormen出手了。他撰写了此书作为面向算法设计与分析初学者的入门书籍。本书有着如下几个鲜明的特点。
第一，本书仅仅使用了有限的数学知识。对于很多算法初学者来说，阻碍其学习的很重要的一个绊脚石就是算法设计与分析中涉及的大量数学知识，覆盖了概率论、代数、数学分析、图论等多个方面，而本书不需要读者具备这些方面的深入知识，为算法初学者提供了一条入门的捷径。
第二，本书语言通俗生动，并且把算法和现实中的问题紧密连接，避免出现大量算法分析细节。一方面，让算法真正成为生活中的一种思维方式，让读者深入了解算法思想的实际用途；另一方面，对于很多应用背后的算法知识，让读者在“知其然”的同时“知其所以然”。
第三，本书覆盖范围广，在200多页的篇幅中覆盖了图论算法、字符串算法、密码算法、数据压缩算法，甚至NP完全问题和不可判定问题，使读者可在最短的时间内掌握多种应用中不同的算法。
特别值得一提的是，本书的作者Thomas Cormen也是算法设计与分析方面的经典教材《算法导论》的作者之一，译者有幸参与了该书的翻译工作。《算法导论》是一本内容深入的算法设计与分析方面的大部头教材，而本书则可以看作是《算法导论》的一个薄薄的入门版本，通过阅读本书，读者可以用最短的时间轻松地窥见算法设计与分析的门径，奠定学习“算法设计与分析”课程的基础。
在本书英文版出版以后，译者应机械工业出版社的邀请开始了本书的翻译工作。由于水平有限且时间紧张，译文中一定存在许多不足，在此敬请各位同行、专家、学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱wangzh@hit.edu.cn，以改进本书的译本。
最后，我要感谢哈尔滨工业大学的孔欣欣同学在翻译过程中进行的辅助翻译工作。在完成译稿之后，我的爱人黎玲利博士阅读全文并提出了很多有益的意见，在此也表示感谢。同时感谢机械工业出版社的姚蕾编辑和朱劼编辑，由于她们的信任和支持，本书的翻译工作才得以顺利进行。
王宏志
前言
Algorithms Unlocked
计算机是如何解决问题的呢？小小的GPS是如何只在几秒钟内就从无数条可能路径中找出到达目的地的最快捷路径的呢？在网上购物时，又如何防止他人窃取你的信用卡账号呢？解决这些问题，以及大量其他问题的答案均是算法。我写本书的目的就是为你打开算法之门，解开算法之谜。
我是《算法导论》的合著者之一。《算法导论》是一本特别好的书（当然，这是我个人的主观评价），但是它确实相当专业。
本书并不是《算法导论》，甚至不能被称为一本教材。它既没有对计算机算法领域进行广度或深度的研究，也没有遵照惯例来讲述设计计算机算法的方法，甚至连一道需要读者自己求解的难题或者练习题也没有。
那么，这是一本什么样的书呢？如果你符合如下条件，那么就可以开始阅读之旅了：
●你对计算机如何解决问题感兴趣；
●你想知道如何评估这些解决方案的质量；
●你想了解计算方面的问题和这些问题的解决方案是如何与非计算机世界关联起来的；
●你能处理一点数学运算；
●你不需要编写过计算机程序（当然，编写过程序更好）。
一些计算机算法方面的书籍是讲述理论概念的，并涉及非常少的技术细节；一些书籍关注的全是技术细节；而另外一些书籍是介于这两者之间的。每类图书都有自己的定位，我将本书定位于介于两者之间。诚然，本书涉及了一些数学知识，并且部分地方阐述得非常仔细，但是我已经竭力避免深入阐述细节（或许除了本书的末尾部分，我无法克制住自己，阐述了一些细节知识）。
我认为本书有点像开胃菜。设想你去了一家意大利餐厅，点了一份开胃菜，直到吃完开胃菜，你才会决定是否点其余食物。开胃菜到了，你就开始用餐了。或许你不喜欢吃开胃菜，并且决定不点其他菜了。可能你喜欢吃开胃菜，但是吃完它，你就感觉饱了，因此不需要点其他菜了。或者也有可能你喜欢吃开胃菜，但你并没有吃饱，此时你便开始期待其他菜了。将本书看作开胃菜，我希望能够产生后两种结果之一：或者读完了本书，你就很满足，感觉没有必要再深入探究算法世界了；或者你非常喜欢从本书中所学到的知识，以至于你想要学习更多算法方面的内容。每一章最后一节的标题为“拓展阅读”，其中会介绍更多关于该章主题的更为深入的书籍和文章。
你将从本书中学到什么
我无法断定你将从本书中学到什么。如下是我希望你能从本书中学到的：
●什么是计算机算法，能够采用一种方式来描述计算机算法，以及如何评估算法。
●在计算机中查找信息的简单方式。
●在计算机中重排信息以使其以一种预定顺序排列的方法。（我们称这一任务为“排序”。）
●如何解决那些能在计算机中以一种称为“图”的数学结构建模的基本难题。在许多应用中，利用图建模的领域包括：道路网（哪些十字路口到哪些十字路口有直接相连的道路，这些道路有多长），任务间的依赖关系（哪个任务必须在其他任务之前完成），金融关系（世界各国货币间的汇率是多少），或者是人与人之间的联系（谁认识谁？谁讨厌谁？哪个演员和哪个演员出现在同一个电影中等）。
●如何解决关于文本字符串的问题。其中一些问题在某些领域有所应用，例如生物学领域，其中字符表示基本的分子，字符串表示DNA结构。
●密码学背后的基本原理。即使你自己从来没有加密过一条信息，你的计算机很可能已经对它执行加密操作了（例如当你在网上购物时）。
计算机是如何解决问题的呢？小小的GPS是如何只在几秒钟内就从无数条可能路径中找出到达目的地的最快捷路径的呢？在网上购物时，又如何防止他人窃取你的信用卡账号呢？解决这些问题，以及大量其他问题的答案均是算法。我写本书的目的就是为你打开算法之门，解开算法之谜。
我是《算法导论》的合著者之一。《算法导论》是一本特别好的书（当然，这是我个人的主观评价），但是它确实相当专业。
本书并不是《算法导论》，甚至不能被称为一本教材。它既没有对计算机算法领域进行广度或深度的研究，也没有遵照惯例来讲述设计计算机算法的方法，甚至连一道需要读者自己求解的难题或者练习题也没有。
那么，这是一本什么样的书呢？如果你符合如下条件，那么就可以开始阅读之旅了：
●你对计算机如何解决问题感兴趣；
●你想知道如何评估这些解决方案的质量；
●你想了解计算方面的问题和这些问题的解决方案是如何与非计算机世界关联起来的；
●你能处理一点数学运算；
●你不需要编写过计算机程序（当然，编写过程序更好）。
一些计算机算法方面的书籍是讲述理论概念的，并涉及非常少的技术细节；一些书籍关注的全是技术细节；而另外一些书籍是介于这两者之间的。每类图书都有自己的定位，我将本书定位于介于两者之间。诚然，本书涉及了一些数学知识，并且部分地方阐述得非常仔细，但是我已经竭力避免深入阐述细节（或许除了本书的末尾部分，我无法克制住自己，阐述了一些细节知识）。
我认为本书有点像开胃菜。设想你去了一家意大利餐厅，点了一份开胃菜，直到吃完开胃菜，你才会决定是否点其余食物。开胃菜到了，你就开始用餐了。或许你不喜欢吃开胃菜，并且决定不点其他菜了。可能你喜欢吃开胃菜，但是吃完它，你就感觉饱了，因此不需要点其他菜了。或者也有可能你喜欢吃开胃菜，但你并没有吃饱，此时你便开始期待其他菜了。将本书看作开胃菜，我希望能够产生后两种结果之一：或者读完了本书，你就很满足，感觉没有必要再深入探究算法世界了；或者你非常喜欢从本书中所学到的知识，以至于你想要学习更多算法方面的内容。每一章最后一节的标题为“拓展阅读”，其中会介绍更多关于该章主题的更为深入的书籍和文章。
你将从本书中学到什么
我无法断定你将从本书中学到什么。如下是我希望你能从本书中学到的：
●什么是计算机算法，能够采用一种方式来描述计算机算法，以及如何评估算法。
●在计算机中查找信息的简单方式。
●在计算机中重排信息以使其以一种预定顺序排列的方法。（我们称这一任务为“排序”。）
●如何解决那些能在计算机中以一种称为“图”的数学结构建模的基本难题。在许多应用中，利用图建模的领域包括：道路网（哪些十字路口到哪些十字路口有直接相连的道路，这些道路有多长），任务间的依赖关系（哪个任务必须在其他任务之前完成），金融关系（世界各国货币间的汇率是多少），或者是人与人之间的联系（谁认识谁？谁讨厌谁？哪个演员和哪个演员出现在同一个电影中等）。
●如何解决关于文本字符串的问题。其中一些问题在某些领域有所应用，例如生物学领域，其中字符表示基本的分子，字符串表示DNA结构。
●密码学背后的基本原理。即使你自己从来没有加密过一条信息，你的计算机很可能已经对它执行加密操作了（例如当你在网上购物时）。
序言
文艺复兴以来，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的各个领域取得了垄断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年间名家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅擘划了研究的范畴，还揭示了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会因年月的流逝而减退。
近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算机科学发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计算机教材将对我国计算机教育事业的发展起到积极的推动作用，也是与世界接轨、建设真正的世界一流大学的必由之路。
机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998年开始，我们就将工作重点放在了遴选、移译国外优秀教材上。经过多年的不懈努力，我们与Pearson， McGrawHill， Elsevier， MIT， John Wiley & Sons， Cengage等世界著名出版公司建立了良好的合作关系，从他们现有的数百种教材中甄选出Andrew STanenbaum， Bjarne Stroustrup， Brain WKernighan， Dennis Ritchie， Jim Gray， Afred VAho， John E.Hopcroft， Jeffrey DUllman， Abraham Silberschatz， William Stallings， Donald EKnuth， John LHennessy， Larry LPeterson等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者学习、研究及珍藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。
“计算机科学丛书”的出版工作得到了国内外学者的鼎力相助，国内的专家不仅提供了中肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品在中国的传播，有的还专门为其书的中译本作序。迄今，“计算机科学丛书”已经出版了近两百个品种，这些书籍在读者中树立了良好的口碑，并被许多高校采用为正式教材和参考书籍。其影印版“经典原版书库”作为姊妹篇也被越来越多实施双语教学的学校所采用。
权威的作者、经典的教材、一流的译者、严格的审校、精细的编辑，这些因素使我们的图书有了质量的保证。随着计算机科学与技术专业学科建设的不断完善和教材改革的逐渐深化，教育界对国外计算机教材的需求和应用都将步入一个新的阶段，我们的目标是尽善尽美，而反馈的意见正是我们达到这一终极目标的重要帮助。华章公司欢迎老师和读者对我们的工作提出建议或给予指正，我们的联系方法如下：华章网站：wwwhzbookcom
电子邮件：hzjsj@hzbookcom
联系电话：（010）88379604
联系地址：北京市西城区百万庄南街1号
邮政编码：100037
近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算机科学发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计算机教材将对我国计算机教育事业的发展起到积极的推动作用，也是与世界接轨、建设真正的世界一流大学的必由之路。
机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998年开始，我们就将工作重点放在了遴选、移译国外优秀教材上。经过多年的不懈努力，我们与Pearson， McGrawHill， Elsevier， MIT， John Wiley & Sons， Cengage等世界著名出版公司建立了良好的合作关系，从他们现有的数百种教材中甄选出Andrew STanenbaum， Bjarne Stroustrup， Brain WKernighan， Dennis Ritchie， Jim Gray， Afred VAho， John E.Hopcroft， Jeffrey DUllman， Abraham Silberschatz， William Stallings， Donald EKnuth， John LHennessy， Larry LPeterson等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者学习、研究及珍藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。
“计算机科学丛书”的出版工作得到了国内外学者的鼎力相助，国内的专家不仅提供了中肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品在中国的传播，有的还专门为其书的中译本作序。迄今，“计算机科学丛书”已经出版了近两百个品种，这些书籍在读者中树立了良好的口碑，并被许多高校采用为正式教材和参考书籍。其影印版“经典原版书库”作为姊妹篇也被越来越多实施双语教学的学校所采用。
权威的作者、经典的教材、一流的译者、严格的审校、精细的编辑，这些因素使我们的图书有了质量的保证。随着计算机科学与技术专业学科建设的不断完善和教材改革的逐渐深化，教育界对国外计算机教材的需求和应用都将步入一个新的阶段，我们的目标是尽善尽美，而反馈的意见正是我们达到这一终极目标的重要帮助。华章公司欢迎老师和读者对我们的工作提出建议或给予指正，我们的联系方法如下：华章网站：wwwhzbookcom
电子邮件：hzjsj@hzbookcom
联系电话：（010）88379604
联系地址：北京市西城区百万庄南街1号
邮政编码：100037
媒体评论
“算法是计算机科学的核心。这是唯一一本力图针对大众读者的算法书籍。它使一个抽象的主题变得简洁易懂，而没有过多拘泥于细节。本书具有深远的影响，还没有人能够比托马斯 H.科尔曼更能胜任缩小算法专家和公众的差距这一工作。”
——Frank Dehne，卡尔顿大学计算机科学系教授
“托马斯 H.科尔曼写了一部关于基本算法的引人入胜的、简洁易读的调查报告。有一定计算机编程基础并富有进取精神的读者将会洞察到隐含在高效计算机之下的关键的算法技术。”
——Phil Klein，布朗大学汁算机科学系教授
“托马斯 H.科尔曼帮助读者广泛理解计算机科学中的关键算法。对于计算机科学专业的学生和从业者，本书对每个计算机科学家必须理解的关键算法都进行了很好的回顾。对于非专业人士，它确实打开了每天所使用的工具的核心——算法世界的大门。”
——G．Ayorkor Korsah，阿什西大学计算机科学系助理教授
——Frank Dehne，卡尔顿大学计算机科学系教授
“托马斯 H.科尔曼写了一部关于基本算法的引人入胜的、简洁易读的调查报告。有一定计算机编程基础并富有进取精神的读者将会洞察到隐含在高效计算机之下的关键的算法技术。”
——Phil Klein，布朗大学汁算机科学系教授
“托马斯 H.科尔曼帮助读者广泛理解计算机科学中的关键算法。对于计算机科学专业的学生和从业者，本书对每个计算机科学家必须理解的关键算法都进行了很好的回顾。对于非专业人士，它确实打开了每天所使用的工具的核心——算法世界的大门。”
——G．Ayorkor Korsah，阿什西大学计算机科学系助理教授
书摘
在前面的章节中，我们看到了对n个元素的数组进行排序的4个算法。其中的2个算法，选择排序和插入排序，最坏情况下的运行时间是Θ（n2），这并不是很好。另一个算法，快速排序，最坏情况下的运行时间也是Θ（n2），但是平均情况下仅仅会花费Θ（nlgn）时间。归并排序在任何情况下所花费的时间均是Θ（nlgn）。实际上，快速排序是这4个算法中最快的一个，但是如果必须要避免最坏情况的发生，你一定会选择归并排序。
Θ（nlgn）是能得到的最好情况吗？能否设计出一个可在最坏情况下超越Θ（nlgn）运行时间的算法？答案取决于游戏的规则：在确定排序顺序时，排序算法是如何允许使用排序关键字的？
在这一章中，我们将看到在一些特定规则下，我们不能超越Θ（nlgn）。随后我们看到了两个排序算法，计数排序和基数排序打破了规则的约束，仅仅在Θ（n）时间内就能实现对数组的排序。
4.1基于排序的规则
如果回忆前一章的4个算法是如何使用排序关键字的，你将看到它们在确定排序顺序时仅仅依赖于对排序关键字对进行的比较。它们确定决策时的依据均是“如果这个元素的排序关键字比另一个元素的排序关键字小，那么就进行相应操作，否则，进行其他操作或者什么也不做。”你可能会认为一个排序算法可能仅仅能制定这种形式的决策；除此之外，一个排序算法还可能做出什么样的决策依据呢？
Θ（nlgn）是能得到的最好情况吗？能否设计出一个可在最坏情况下超越Θ（nlgn）运行时间的算法？答案取决于游戏的规则：在确定排序顺序时，排序算法是如何允许使用排序关键字的？
在这一章中，我们将看到在一些特定规则下，我们不能超越Θ（nlgn）。随后我们看到了两个排序算法，计数排序和基数排序打破了规则的约束，仅仅在Θ（n）时间内就能实现对数组的排序。
4.1基于排序的规则
如果回忆前一章的4个算法是如何使用排序关键字的，你将看到它们在确定排序顺序时仅仅依赖于对排序关键字对进行的比较。它们确定决策时的依据均是“如果这个元素的排序关键字比另一个元素的排序关键字小，那么就进行相应操作，否则，进行其他操作或者什么也不做。”你可能会认为一个排序算法可能仅仅能制定这种形式的决策；除此之外，一个排序算法还可能做出什么样的决策依据呢？
