《算法设计与分析基础（第3版）》

书海网短评：
　　《算法设计与分析基础（第3版）》独辟蹊径，采用一种更全面的算法设计技术分类方法。《算法设计与分析基础（第3版）》涵盖递归与非递归算法的数学分析，也涉及经验分析和算法可视化，探讨算法的局限性及解决方法，将算法视为解决问题的

编辑推荐

　　《算法设计与分析基础（第3版）》独辟蹊径，采用一种更全面的算法设计技术分类方法。《算法设计与分析基础（第3版）》涵盖递归与非递归算法的数学分析，也涉及经验分析和算法可视化，探讨算法的局限性及解决方法，将算法视为解决问题的工具，通过谜题和游戏来开拓算法思维

　　《算法设计与分析基础（第3版）》为学生提供600多道习题(含提示)，为教师提供有详细解答的教师手册

内容简介

　　作者基于丰富的教学经验，开发了一套全新的算法分类方法。该分类法站在通用问题求解策略的高度，对现有大多数算法准确分类，从而引领读者沿着一条清晰、一致、连贯的思路来探索算法设计与分析这一迷人领域。《算法设计与分析基础（第3版）》作为第3版，相对前版调整了多个章节的内容和顺序，同时增加了一些算法，并扩展了算法的应用，使得具体算法和通用算法设计技术的对应更加清晰有序；各章累计增加了70道习题，其中包括一些有趣的谜题和面试问题。　　《算法设计与分析基础（第3版）》十分适合用作算法设计和分析的基础教材，也适合任何有兴趣探究算法奥秘的读者使用，只要读者具备数据结构和离散数学的知识即可。　　SimplifiedChineseeditioncopyright?2015byPEARSONEDUCATIONASIALIMITEDandTSINGHUAUNIVERSITYPRESS.　　OriginalEnglishlanguagetitle:IntroductiontotheDesignandAnalysisofAlgorithms,3rdEditionbyAnanyLevitin,Copyright?2012EISBN:9780132316811AllRightsReserved.Publishedbyarrangementwiththeoriginalpublisher,PearsonEducation,Inc.,publishingasPearsonEducation,Inc.ThiseditionisauthorizedforsaleonlyinthePeople’sRepublicofChina（excludingtheSpecialAdministrativeRegionofHongKongandMacao）.　　《算法设计与分析基础（第3版）》中文简体翻译版由PearsonEducation授权给清华大学出版社在中国境内（不包括中国香港、澳门特别行政区）出版发行。

前言/序言

　　一个人在接受科技教育时能得到的最珍贵的收获是能够终身受用的通用智能工具。　　——乔治·福赛思　　无论是计算科学还是计算实践，算法都在其中扮演着重要角色。因此，这门学科中出现了大量的教材。它们在介绍算法的时候，基本上都选择了以下两种方案中的一种。第一种方案是按照问题的类型对算法进行分类。这类教材安排了不同的章节分别讨论排序、查找、图等算法。这种做法的优点是，对于解决同一问题的不同算法，它能够立即比较这些算法的效率。其缺点在于，由于过于强调问题的类型，它忽略了对算法设计技术的讨论。　　第二种方案围绕着算法设计技术来组织章节。在这种结构中，即使算法来自于不同的计算领域，如果它们采用了相同的设计技术，就会被编成一组。从各方（例如[BaY95]）获得的信心使我相信，这种结构更适合于算法设计与分析的基础课程。强调算法设计技术有三个主要原因。第一，学生们在解决新问题时，可以运用这些技术设计出新的算法。从实用的角度看，这使得学习算法设计技术颇有价值。第二，学生们会试图按照算法的内在设计方法对已知的众多算法进行分类。计算机科学教育的一个主要目的，就是让学生们知道如何发掘不同应用领域的算法间的共性。毕竟，每门学科都会倾向于把它的重要主题归纳为几个甚至一个规则。第三，依我看来，算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用。　　遗憾的是，无论是从理论还是从教学的角度，传统的算法设计技术分类法都存在一些严重的缺陷。其中最显著的缺陷就是无法对许多重要的算法进行分类。由于这种局限性，这些书的作者不得不在按照设计技术进行分类的同时，另外增加一些章节来讨论特殊的问题类型。但这种改变导致课程缺乏一致性，而且很可能会使学生感到迷惑。　　算法设计技术的新分类法　　传统算法设计技术分类法的缺陷令我感到失望，它激发我开发一套新的分类法（[Lev99]），这套分类法就是《算法设计与分析基础（第3版）》的基础。以下是这套新分类法的几个主要优势。　　新分类法比传统分类法更容易理解。它包含的某些设计策略，例如蛮力法、减治法、变治法、时空权衡和迭代改进，几乎从不曾被看作重要的设计范例。　　新分类法很自然地覆盖了许多传统方法无法分类的经典算法（欧几里得算法、堆排序、查找树、散列法、拓扑排序、高斯消去法、霍纳法则等，不胜枚举）。所以，新分类法能够以一种连贯的、一致的方式表达这些经典算法的标准内容。　　新分类法很自然地容纳了某些设计技术的重要变种（例如，它能涵盖减治法的3个变种和变治法的3个变种）。　　在分析算法效率时，新分类法与分析方法结合得更好（参见附录B）。　　设计技术作为问题求解的一般性策略　　在《算法设计与分析基础（第3版）》中，主要将设计技术应用于计算机科学中的经典问题（这里唯一的创新是引入了一些数值算法的内容，我们也是用同样的通用框架来表述这些算法的）。但把这些设计技术看作问题求解的一般性工具时，它们的应用就不仅限于传统的计算问题和数学问题了。有两个因素令这一点变得尤其重要。第一，越来越多的计算类应用超越了它们的传统领域，并且有足够的理由使人相信，这种趋势会愈演愈烈。第二，人们渐渐认识到，提高学生们的问题求解能力是高等教育的一个主要目标。为了满足这个目标，在计算机科学课程体系中安排一门算法设计和分析课程是非常合适的，因为它会告诉学生如何应用一些特定的策略来解决问题。　　虽然我并不建议将算法设计和分析课程变成一门教授一般性问题求解方法的课程，但我深信，我们不应错过算法设计和分析课程提供的这样一个独一无二的机会。为了这个目标，《算法设计与分析基础（第3版）》包含了一些和谜题相关的应用。虽然利用谜题来教授算法课程绝不是我的创新，但《算法设计与分析基础（第3版）》打算通过引进一些全新的谜题来系统地实现这个思路。　　如何使用《算法设计与分析基础（第3版）》　　我的目标是写一本既不泛泛而谈，又可供学生们独立阅读的教材。为了实现这个目标，《算法设计与分析基础（第3版）》做了如下努力。　　根据乔治？福赛思的观点（参见前面的引文），我试图着重强调隐藏在算法设计和分析背后的主要思想。在选择特定的算法来阐述这些思想的时候，我并不倾向于涉及大量的算法，而是选择那些最能揭示其内在设计技术或分析方法的算法。幸运的是，大多数经典算法满足这个要求。　　第2章主要分析算法的效率，该章将分析非递归算法的方法和分析递归算法的典型方法区别开来。这一章还花了一些篇幅介绍算法经验分析和算法可视化。　　书中系统地穿插着一些面向读者的提问。其中有些问题是经过精心设计的，而且答案紧随其后，目的是引起读者的注意或引发疑问。其余问题的用意是防止读者走马观花，不能充分理解《算法设计与分析基础（第3版）》的内容。　　每一章结束时都会对本章最重要的概念和结论做一个总结。　　《算法设计与分析基础（第3版）》包含600多道习题。有些习题是为了给大家练习，另外一些则是为了指出书中正文部分所涉及内容的重要意义，或是为了介绍一些书中没有涉及的算法。有一些习题利用了因特网上的资源。较难的习题数量不多，会在教师用书中用一种特殊的记号标注出来（因为有些学生可能没有勇气做那些有难度标注的习题，所以《算法设计与分析基础（第3版）》没有对习题标注难度）。谜题类的习题用一种特殊的图标做标注。　　《算法设计与分析基础（第3版）》所有的习题都附有提示。除了编程练习，习题的详细解法都能够在教师资源中找到。请发送邮件到coo@netease.com，申请教师相关资源（也可联系培生公司的当地销售代表，或者访问www.pearsonhighered.com/irc）。《算法设计与分析基础（第3版）》的任何读者都可以在CS支持网站http：//cssupport.pearsoncmg.com上找到PowerPoint格式的幻灯片文件。如果对算法有兴趣，欢迎加入QQ群“算法学习交流”，群号：425283001。　　第3版的变化　　第3版有若干变化。其中最重要的变化是介绍减治法和分治法的先后顺序。第3版会先介绍减治法，后介绍分治法，这样做有以下几个优点。　　较之分治法，减治法更简单。　　在求解问题方面，减治法应用更广。　　这样的编排顺序便于先介绍插入排序，后介绍合并排序和快速排序。　　数组划分的概念通过选择性问题引入，这次利用Lomuto算法的单向扫描来实现，而将Hoare划分方法的双向扫描留至后文与快速排序一并介绍。　　折半查找归入介绍减常量算法的章节。　　另一个重要变化是重新编排第8章关于动态规划的内容，具体如下所述。　　导述部分的内容是全新的。在前两版中用计算二项式系数的例子来引入动态规划这一重要技术，但在第3版中会介绍3个基础性示例，这样介绍的效果更好。　　8.1节的习题是全新的，包括一些在前两版中没有涉及的流行的应用。　　第8章其他小节的顺序也做了调整，以便达到由浅入深、循序渐进的效果。　　此外，还有其他一些变化。增加了不少与《算法设计与分析基础（第3版）》所述算法相关的应用。遍历图算法不再随减治法介绍，而是纳入蛮力算法和穷举查找的范畴，我认为这样更合理。在介绍生成组合对象的算法时，新增了格雷码算法。对求解最近对问题的分治法有更深入的探讨。改进的内容包括算法可视化和求解旅行商问题的近似算法，当然参考文献也有相应的更新。　　第3版一共新增约70道习题，其中涉及算法谜题和面试问题。　　先修课程　　《算法设计与分析基础（第3版）》假定读者已经学习了离散数学的标准课程和一门基础性的编程课程。有了这样的知识背景，读者应该能够掌握《算法设计与分析基础（第3版）》的内容而不会遇到太大的困难。尽管如此，1.4节、附录A和附录B仍然对基本的数据结构以及必须用到的求和公式与递推关系分别进行复习和回顾。只有3个小节（2.2节、11.4节和12.4节）会用到一些简单的微积分知识，如果读者缺少必要的微积分知识，完全可以跳过这3个涉及微积分的小节，这并不妨碍对《算法设计与分析基础（第3版）》其余部分的理解。　　课程进度安排　　如果打算开设一门围绕算法设计技术来讲解算法设计和分析理论的基础课程，可以采用《算法设计与分析基础（第3版）》作为教材。但要想在一个学期内完成该课程，《算法设计与分析基础（第3版）》涵盖的内容可能过于丰富了。大体上来说，跳过第3～12章的部分内容不会影响读者对后面部分的理解。《算法设计与分析基础（第3版）》的任何一个部分都可以安排学生自学。尤其是2.6节和2.7节，它们分别介绍了经验分析和算法可视化，这两小节的内容可以结合课后练习布置给学生。　　下面给出了针对一个学期课程的教学计划，这是按照40课时的集中教学来设计的。　　课次主题小节　　1课程简介1.1～1.3　　2，3分析框架；常用符号、和2.1，2.2　　4非递归算法的数学分析2.3　　5，6递归算法的数学分析2.4，2.5（+附录B）　　7　蛮力算法3.1，3.2（+3.3）　　8穷举查找3.4　　9深度优先查找和广度优先查找3.5　　10～11减一算法：插入排序、拓扑排序4.1，4.2　　12折半查找和其他减常量算法4.4　　13减变量算法4.5　　14～15分治法：合并排序、快速排序5.1～5.2　　16其他分治法示例5.3、5.4或5.5　　16　减变量算法5.6　　17～19实例化简：预排序、高斯消去法、平衡查找树6.1～6.3　　20改变表现：堆和堆排序或者霍纳法则和二进制幂6.4或6.5　　21问题化简6.6　　22～24时空权衡：串匹配、散列法、B树　7.2～7.4　　25～27动态规划算法8.1～8.4（选3节）　　28～30贪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法9.1～9.4　　31～33迭代改进算法10.1～10.4（选3节）　　34下界的参数11.1　　35决策树11.2　　36P、NP和NP完全问题11.3　　37数值算法11.4（+12.4）　　38回溯法12.1　　39分支界限法12.2　　40NP困难问题的近似算法　12.3　　致谢　　我要向《算法设计与分析基础（第3版）》的评审表达衷心的感谢，还要感谢《算法设计与分析基础（第3版）》前两版的许多读者，他们提供了许多宝贵的意见和建议，帮助《算法设计与分析基础（第3版）》得以改进和完善。《算法设计与分析基础（第3版）》第3版尤其得益于下列人士的评审，包括AndrewHarrington（芝加哥洛约拉大学）、DavidLevine（圣文德大学）、StefanoLombardi（加州大学河滨分校）、DanielMcKee（宾州曼斯菲尔德大学）、SusanBrilliant（弗吉尼亚州立联邦大学）、DavidAkers（菩及海湾大学）以及两名匿名评审。　　我要感谢培生出版社所有为《算法设计与分析基础（第3版）》付出不懈努力的工作人员和相关人士。尤其要感谢《算法设计与分析基础（第3版）》编辑MattGoldstein、编务助理ChelseaBell、市场经理YezAlayan和产品总监KaylaSmith-Tarbox。我还要感谢RichardCamp为《算法设计与分析基础（第3版）》审稿，WindfallSoftware的PaulAnagnostopoulos和JacquiScarlott为《算法设计与分析基础（第3版）》排版并提供项目管理支持，以及MaryEllenOliver为《算法设计与分析基础（第3版）》进行校对。　　最后，我要感谢两位家人。另一半整天都在写书比自己本人写书更让人崩溃，我的妻子Maria已容忍我多年并任劳任怨地帮助我，《算法设计与分析基础（第3版）》400多幅插图以及教师手册都是凭她一己之力完成的。女儿Miriam是我多年的英语老师，她不但阅读了《算法设计与分析基础（第3版）》大量篇幅，还帮我为每章找到了合适的名人名言。　　AnanyLevitin