详情
算法详解系列图书共有4卷，本书是第一卷——基础算法。本书共有6章，主要介绍了4个主题，它们分别是渐进性分析和大O表示法、分冶算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了较多的便利。
书名：算法详解（卷1）——算法基础
ISBN：978-7-115-49352-1
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美]蒂姆•拉夫加登（Tim Roughgarden）
译 徐 波
责任编辑 武晓燕
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
Simplified Chinese translation copyright ©2018 by Posts and Telecommunications Press.
ALL RIGHTS RESERVED.
Algorithms Illuminated Part 1:The Basics, by Tim Roughgarden, ISBN 9780999282908.
Copyright © 2017 by Tim Roughgarden.
本书中文简体版由Tim Roughgarden授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式或任何手段复制和传播。
版权所有，侵权必究。
算法是计算机科学领域最重要的基石之一。算法是程序的灵魂，只有掌握了算法，才能轻松地驾驭程序开发。
《算法详解》系列图书共有4卷，本书是第1卷——算法基础。本书共有6章，主要介绍了4个主题，它们分别是渐进性分析和大O表示法、分治算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了较多的便利。
本书为对算法感兴趣的广大读者提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维以及计算思维的IT专业人士，以及在准备面试的应聘者和面试官阅读参考。
本书是在我的在线算法课程的基础之上编写的，是四卷本系列的第1卷。这个在线课程2012年起就定期举行，它建立在我在斯坦福大学教授多年的本科课程的基础之上。
本书对以下4个主题进行了介绍。
渐进性表示法为讨论算法的设计和分析提供了基本术语。它的关键概念是大O表示法，这是一种用于衡量算法的运行时间粒度的建模选择。我们将会看到，清晰的高层算法设计思想的一大优点就是可以忽略常数因子和低阶项，把注意力集中在算法的性能与输入长度之间的关系上。
算法设计中不存在万能的捷径，不存在适用于所有的计算问题的一种解决问题的方法。但是，还是存在一些通用的算法设计技巧适用于一定范围内的不同领域。在本系列的第1卷中，我们将讨论“分治”技巧。分治法的思路是把一个问题分解为几个更小的子问题，然后递归地解决这些子问题，并把它们的解决方案快速组合在一起形成原始问题的解决方案。我们将讨论用于排序、整数乘法、矩阵乘法和基本的计算几何学问题的快速分治算法。我们还将讨论主方法，它是一个强大的工具，用于分析分治算法的运行时间。
随机化算法在运行时采用了“掷硬币”的方式，它的行为取决于掷硬币的结果。令人吃惊的是，随机化常常能够带来简单、优雅且实用的算法。其中一个经典例子是随机化的快速排序（QuickSort）算法，我们将详细介绍这个算法并分析其运行时间。我们还将在《算法详解》系列的第2卷看到随机化算法的进一步应用。
作为前3个主题研究的附加成果，我们将学习几个著名的排序和选择算法，包括归并排序（MergeSort）、快速排序和线性时间级的选择（包括随机化版本和确定性版本）。这些算法具有令人炫目的高速度，以至于它们的运行时间较之读取输入所需要的时间并没有多出很多。创建类似这样的“低代价基本操作”集合，既可以直接用它来操作数据，也可以将其作为更困难问题的解决方案的基本单位。
关于本书内容的更详细介绍，可以阅读每章的“本章要点”，它对每一章的内容进行了总结，特别是那些重要的概念。
《算法详解（卷2）》讨论了数据结构（堆、平衡搜索树、散列表、布隆过滤器）、图形基本单元（宽度和深度优先的搜索、连通性、最短路径）以及它们的应用（从消除重复到社交网络分析）。卷3重点讨论了贪婪算法（调度、最小生成树、集群、霍夫曼编码）和动态编程（背包、序列对齐、最短路径、最佳搜索树等）。卷4则介绍了NP完整性及其对算法设计师的意义，还讨论了处理难解的计算问题的一些策略，包括对试探法和局部搜索的分析。
本书经常会出现“Q.e.d”等字样，它是quod erat demonstrandum的缩写，表示“证明完毕”。在数学著作中，它出现在证明过程的最后，表示证明已经完成。
精通算法需要大量的时间和精力，那为什么要学习算法呢？
读者将学习一些令人炫目的用于处理数据的高速子程序以及一些实用的数据结构，它们用于组织数据，并可以直接部署到自己的程序中。实现和使用这些算法将会扩展并提高读者的编程技巧。读者还将学习基本的算法设计范式，它们与许多不同领域的不同问题密切相关，并且可以作为预测算法性能的工具。这些“算法设计模式”可以帮助读者为自己碰到的问题设计新算法。
读者将会获得大量的实践以对算法进行描述和推导。通过数学分析，读者将对《算法详解》系列图书所涵盖的特定算法和数据结构产生深刻的理解。读者还将掌握一些广泛用于算法分析的实用数学技巧。
在学习了算法之后，很难发现有什么地方没有它们的踪影。不管是坐电梯、观察鸟群，还是管理自己的投资组合，甚至是观察婴儿的认知，算法思维都如影随行。算法思维在计算机科学之外的领域，包括生物学、统计学和经济学越来越实用。
研究算法就像是观看计算机科学最近60年的精彩剪辑。当读者参加一个计算机科学的鸡尾酒会时，会上有人讲了一个关于Dijkstra算法的笑话时，你就不会感觉自己被排除在这个圈子之外了。在阅读了本书系列之后，读者将会了解许多这方面的知识。
在过去这些年里，有很多学生向我讲述了《算法详解》系列图书是怎样帮助他们在技术访谈中大放异彩。
《算法详解》系列图书只有一个目标：尽可能以读者容易接受的方式介绍算法的基础知识。读者可以把本书看成是专家级算法教师的课程记录，教师们以课程的形式传道解惑。
市面上还有一些非常优秀的更为传统、全面的算法教材，它们都可以作为《算法详解》系列关于算法的其他细节、问题和主题的有益补充。我鼓励读者探索和寻找自己喜欢的其他教材。另外还有一些图书的出发点有所不同，它们偏向于站在程序员的角度寻找一种特定编程语言的成熟算法实现。网络中存在大量免费的这类算法。
《算法详解》系列图书以及建立在它的基础之上的在线课程的整体目标是尽可能地扩展读者群体的范围。学习我的在线课程的人们具有不同的年龄、背景、生活方式，有大量来自全世界各个角落的学生（包括高中生、大学生等）、软件工程师（包括现在的和未来的）、科学家和专业人员。
本书并不是讨论编程的，理想情况下读者应该已经了解了一种标准语言（例如Java、Python、C、Scala、Haskell等）并掌握了基本的编程技巧。作为一个立竿见影的试验，读者可以试着阅读第1.4节的代码。如果读者觉得自己能够看懂，那么看懂本书的其他部分应该也没有问题。
如果读者想要提高自己的编程技巧，那么可以观看一些非常优秀的讲述基础编程的免费在线课程。
我们还会根据需要使用数学分析帮助读者理解算法为什么能够实现目标，是怎样实现目标的。Eric Lehman和Tom Leighton关于计算机科学的数学知识的免费课程是极为优秀的，可以帮助读者复习数学记法（例如∑和
）、数学证明的基础知识（归纳、悖论等）、离散概率等更多知识。附录A和附录B分别提供了数学归纳法和离散概率的快速回顾。带星号的章节是最强调数学背景的。对数学不太精通或者时间较为紧张的读者可以在第一次阅读时跳过这些章节，这种做法并不会影响全书内容的连续性。
《算法详解》系列的在线课程当前运行于Coursera和Stanford Lagunita平台。另外还有一些资源可以帮助读者根据自己的心愿提升对在线课程的体验。
视频。如果读者觉得相比阅读文字，更喜欢听和看，那么可以在YouTube的视频播放列表中观看。这些视频涵盖了《算法详解》系列的所有主题。我希望它们能够激发读者学习算法的持续热情。当然，它们并不能完全取代书的作用。
小测验。读者怎么才能知道自己是否完全理解了本书所讨论的概念呢？散布于全书的小测验及其答案和详细解释就起到了这个作用。当读者阅读到这块内容时，最好能够停下来认真思考，然后再继续阅读接下来的内容。
章末习题。每章的末尾都有一些相对简单的问题，用于测试读者对该章内容的理解。另外还有一些开放性的、难度更大的挑战题。本书并未包含章末习题的答案，但是读者可以通过本书的论坛（稍后介绍）与我以及其他读者进行交流。
编程题。许多章的最后部分是一个建议的编程项目，其目的是通过创建自己的算法工作程序，来培养读者对算法的完全理解。读者可以在www.algorithmsi- lluminated.org上找到数据集、测试例以及它们的答案。
论坛。在线课程能够取得成功的一个重要原因是它们为参与者提供了互相帮助的机会，读者可以通过论坛讨论课程材料和调试程序。本书系列的读者也有同样的机会，你可以通过www.algorithmsilluminated.org参与互动。
如果没有过去几年里我的算法课程中数以千计的参与者的热情和渴望，《算法详解》系列图书就不可能面世。这些课程既包括斯坦福校园里的课程，也包括在线平台的课程。我特别感谢那些为本书的早期草稿提供详细反馈的人们：Tonya Blust、Yuan Cao、Jim Humelsine、Bayram Kuliyev、Patrick Monkelban、Kyle Schiller、Nissanka Wickremasinghe和Daniel Zingaro。
我非常欣赏来自读者的建议和修正意见，读者最好通过上面所提到的讨论组与我进行交流。
Tim Roughgarden斯坦福大学
加利福尼亚 斯坦福，2017年9月
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，点击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您是学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
本章的目标是激发读者学习算法的兴趣。我们首先介绍算法的基本概念以及它的重要性。接着，我们通过两个整数相乘的问题来说明精妙的算法是怎样改进那些简单或粗糙的解决方案的。然后，我们详细讨论了归并排序算法。之所以选择这个算法是出于下面这些理由：首先，它是一种非常实用并且非常有名的算法，是读者应该掌握的；其次，它是一种非常合适的“热身”算法，可以为以后学习更复杂的算法打下良好的基础；最后，它是分治算法设计范式的权威引导教程。在本章的最后，我们将描述一些算法分析的指导原则。在本书中，我们将使用这些原则对本书所介绍的算法进行分析。
我们首先要阐明本书的价值，帮助读者激发学习算法的热情。那么，什么是算法呢？它是一组具有良好定义的规则（或者说是一种配方），可以有效地解决一些计算方面的问题。我们可能要处理一大串数字，需要对它们进行重新整理，使它们按顺序排列；我们可能需要在地图上计算从某个起点到某个目标地点的最短路径；我们可能需要在某个最后期限之前完成一些任务，并且需要知道应该按照什么样的顺序完成这些任务，使它们都能在各自的最后期限之前完成。
我们为什么要学习算法呢？
算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。例如，在斯坦福大学，每个级别（学士、硕士和博士）的计算机科学系都需要学习算法课。下面仅仅是算法应用的一些例子。
（1）通信网络中的路由协议需要使用经典的最短路径算法。
（2）公钥加密依赖于高效的数论算法。
（3）计算机图像学需要用到几何算法所提供的计算基元（computational primitive）功能。
（4）数据库的索引依赖于平衡搜索树这种数据结构。
（5）计算机生物学使用动态编程算法对基因的相似度进行测量。
类似的例子还有很多。
算法是技术革新的推动力。算法在现代的技术革新中扮演了一个关键的角色。最显而易见的一个例子是搜索引擎使用一系列的算法高效地计算与特定搜索项相关联的各个Web页面的出现频率。
这种算法最有名的例子是Google当前所使用的网页排名（PageRank）算法。事实上，在美国白宫2010年12月的一个报告中，总统的科学技术顾问作了如下的描述：
“每个人都知道摩尔定律，它是Intel的共同创立者Gordon Moore于1965年所作的一个预测：集成电路中的半导体密度每过一到两年就会扩大一倍……在许多领域，由于算法的改进所获得的性能提升甚至远远超过由于处理器速度的急剧增加所带来的性能提升。”[1]
算法会对其他科学产生影射。虽说这个话题超出了本书的范围，但算法就像一面“镜子”一样，越来越多地用于对计算机科学技术之外的过程进行影射。例如，对量子计算的研究为量子力学提供了一种新的计算视角。经济市场中的价格波动也可以形象地看作一种算法过程。
甚至，技术革新本身也可以看作一种令人吃惊的有效搜索算法。
学习算法有益于思维。当我还是一名学生时，我最喜欢的课程始终是那些具有挑战性的课程。当我艰苦地征服这些课程时，我甚至能够感觉到自己的智商比刚开始学习这些课程时提高了几个点。我希望本书也能够为读者提供类似的体验。
算法很有趣！最后，我希望读者在读完本书后认为算法的设计和分析是件简单而愉快的事情。这并非易事，因为它需要把精确和创新这两个特征罕见地结合在一起。它常常会给我们带来挫折，但有时会让我们深深入迷。别忘了，当我们还是小孩子时，就已经开始学习算法了。
[1] 节选自2010年12月向总统和国会所提供的报告：Designing a Digital Future（第71页）。
小学三年级的时候，我们很可能就学习了两数相乘的计算方法，这是一种具有良好定义的规则，把输入（2 个数）转换为输出（它们的乘积）。在这里，我们要注意区分两个不同的概念：一个是对需要解决的问题的描述，另一个是对解决方案所使用方法（也就是问题的算法）的描述。在本书中，我们所采用的模式是首先介绍一个计算问题（输入及其目标输出），然后描述一个或多个解决该问题的算法。
在整数乘法问题中，它的输入是两个n位数字的整数，分别称为x和y。x和y的长度n可以是任意正整数，但我鼓励读者把n看作一个非常巨大的数，几千甚至更大[2]。（例如，在有些加密应用程序中，可能需要将两个非常巨大的数相乘。）整数乘法问题的目标输出就是x · y这个乘积。
问题：整数乘法
输入：两个n位数字的非负整数x和y。
输出：x和y的乘积。
精确地定义了计算问题之后，我们描述一种解决该问题的算法，这种算法和我们在小学三年级时所学习的算法是一样的。我们通过测量它所执行的“基本操作”的数量来评估这种算法的性能。现在，我们可以把基本操作看作下列的操作之一：
（1）两个个位数相加；
（2）两个个位数相乘；
（3）在一个数的之前或之后添加一个0。
为了加深记忆，我们讨论一个具体的例子，把x = 5678和y = 1234（因此n = 4）这两个整数相乘。详细过程如图1.1所示。这种算法首先计算第一个数与第二个数最后一位数字的“部分乘积”：5678×4 = 22 712。计算这个部分乘积的过程又可以细分为把第一个数的每位数字与4相乘，并在必要时产生“进位”[3]。在计算下一个部分乘积（5678×3 = 17 034）时，我们执行相同的操作，并把结果左移一位，相当于在末尾添加一个“0”。对于剩下的两个部分乘积，也是执行相同的操作。最后一个步骤就是把所有的4个部分乘积相加。
图1.1 整数相乘的小学生算法
回想小学三年级的时候，我们接受了这种算法的正确性。也就是说，不管x和y是什么整数，只要所有的中间计算过程都是正确的，这种算法最终能够得出两个输入数x和y的正确乘积。
也就是说，我们绝不会得到错误的答案，并且它不会陷入无限循环。
小学老师很可能不会讨论实现整数相乘这个过程所需要的基本操作的数量。为了计算第一个部分乘积，我们把4依次与第1个数的5、6、7、8相乘，这样就产生了4个基本操作。由于进位的原因，我们还需要执行一些加法操作。
一般而言，计算一个部分乘积涉及n个乘法（每位数字1个）以及最多n个加法（每位数字最多1个），总共最多是2n个基本操作。第一个部分乘积和其他几个部分乘积相比并没有任何特殊之处，每个部分乘积都是最多需要2n个基本操作。由于一共有n个部分乘积（第2个整数的每位数字各产生1个部分乘积），因此计算所有的部分乘积最多需要n · 2n = 2n2个基本操作。我们还需要把所有的部分乘积相加得到最终的答案，但这个过程仍然需要相当数量的基本操作（最多可达2n2）。该算法的基本操作的数量总结如下：
基本操作的数量 ≤ 常数（此例中为2）· n2
可以想象，当输入数的位数越来越多时，这种算法所执行的基本操作的数量也会急剧增加。如果把输入数的位数增加一倍，需要执行的基本操作的数量是原来的4倍。如果输入的位数是原来的4倍，那么基本操作的数量就是原来的16倍，以此类推。
由于读者所接受的小学教育略有差异，有些读者可能会觉得上面这种方法是唯一可行的，还有些读者认为它至少是两数相乘最合适的方法之一。如果想成为一名严肃的算法设计师，那你必须要摆脱这种认为旧有方法理所当然的顺从思维。
Aho、Hopcroft和Ullman的经典算法名著在讨论了一些算法设计范式之后，对于这个问题提出了自己的见解：
“或许，成为优秀算法设计师的最重要原则就是拒绝满足。”[4]
或者如我所归纳的，每一名算法设计师都应该坚守下面这个信条：
我还能做得更好吗？
当我们面对一个计算问题的简单解决方案时，这个问题就显得格外合适。在小学三年级时，老师不可能要求我们对这种简单的整数相乘算法进行改进。但是到了现在这个时候，无疑是提出这个问题的良好时机。
[2] 如果想把两个不同长度的整数相乘（例如1234和56），一个简单的技巧就是在那个较短的数前面添加适当数量的0（例如，56就变成了0056）。另外，我们所讨论的算法也可以进行调整，使之适应不同长度的乘数。
[3] 8×4 = 32，产生的进位是3；7 × 4 = 28，28加进位3等于31，因此产生的进位也是3，以此类推。
[4] Alfred V. Aho、John E. Hopcroft和Jeffrey D. Ullman，The Design and Analysis of Computer Algorithms，Addison-Wesley，1974年出版，第70页。
算法设计的空间之丰富达到了令人吃惊的程度，除了小学三年级所学习的方法之外，肯定还有其他有趣的方法可以实现两个整数的乘法。本节描述了一种名为Karatsuba乘法[5]的方法。
为了让读者更方便了解Karatsuba乘法，我们还是沿用前面的x = 5678和y = 1234这个例子。我们将执行一系列与之前的小学算法截然不同的步骤，最终也生成x · y这个乘积。这些步骤序列可能会让读者觉得非常神秘，就像魔术师突然从自己的帽子里拽出一只兔子一样。在本节的后面，我们将介绍什么是Karatsuba乘法，并解释它的工作原理。现在，我们需要领悟的一个关键要点就是我们可以通过许多令人眼花缭乱的方法来解决诸如整数乘法这样的计算问题。
首先，我们把x的前半部分和后面部分划分开来，并分别为它们命名为a和b（因此a = 56，b = 78）。
类似，c和d分别表示12和34（图1.2）。
图1.2 把一个4位整数看成是一对两位整数
接着，我们执行一系列的操作，它们只涉及两位数a、b、c和d，并最终用一种神奇的方法把它们组合在一起，产生x和y的乘积。
步骤1：计算a · c = 56 × 12，其结果为672（欢迎读者验算）。
步骤2：计算b · d = 78 × 34 = 2652。
接下来的两个步骤显得更加神秘：
步骤3：计算( a + b) · ( c + d ) = 134 × 46 = 6164。
步骤4：步骤3的结果减去前两个步骤的结果6164 – 672 – 2562 = 2840。
最后，我们把步骤1、2、4的结果相加，不过在此之前先在步骤1的结果后面加上4个0，在步骤4的结果后面加上2个0。
步骤5：计算104×672 + 102 × 2840 + 2652 = 6 720 000 + 284 000 + 2652 = 7 006 652。
这个结果与第1.2节的小学算法所产生的结果完全相同！
读者肯定不明白这中间到底发生了什么。我希望读者既对此感到困惑，又为此入迷，并且非常愉快地发现除了小学所学习的整数相乘算法之外，还存在其他完全不同的算法。一旦意识到算法空间之广阔，我们就会萌生这样的想法：我们能不能比小学算法做得更好？上面所描述的这种算法是不是更加优秀？
输入：两个n位正整数x和y。
输出：x和y的乘积。
先决条件：n是2的整数次方。
在详细分析Karatsuba乘法之前，我们先探索一种更简单的处理整数乘法的递归方法[6] 。整数乘法的递归算法大致可以理解为调用更少位数的整数乘法（例如在上面的例子中，先执行12、34、56、78这些整数的乘法）。
一般而言，位数为偶数n的数x可以表示为2个n/2位的数，即它的前半部分a和后半部分b：
x = 10n/2 · a + b
类似，我们也可以得到下面的结果：
if n = 1 then // 基本条件[10]
通过单个步骤计算x·y，并返回结果
else // 递归条件
a, b := x的前半部分和后半部分
c, d := y的前半部分和后半部分
以递归的方法计算 ac := a·c，ad := a·d，bc := b·c，bd := b·d
使用小学数学加法计算10n·ac + 10n/2·(ad + bc) + bd并返回结果y = 10n/2 · c + d
为了计算x和y的乘积，我们使用上面这两个表达式并把它们相乘：
x · y = (10n/2 · a + b) · (10n/2 · c + d)
= 10n · ( a · c) + 10n/2 · ( a · d + b · c ) + b · d （1.1）
注意，表达式（1.1）中的所有乘法要么是在一对n/2位的整数之间进行的，要么涉及10的乘方。[7]
表达式（1.1）提示用一种递归方法进行两个整数的相乘。为了计算 x · y这个乘积，我们对表达式（1.1）进行计算。4个相关的乘积（a · c、a · d、b · c和b · d）所涉及的位数都少于n，因此我们可以用递归的方式计算它们。当这4个递归调用带着各自的答案返回时，我们就可以很简单地计算表达式（1.1）的值了：在a · c后面加上n个0；把a · d和b · c相加（使用小学加法），并在得出的结果后面加上n/2个0，并最终把这两个表达式与b · d相加[8]。我们用下面的伪码对这种名为RecIntMult的算法进行总结[9]。
RecIntMult
RecIntMult算法和小学算法相比是更快还是更慢呢？现在读者对这个问题应该不会有直观的感觉，我们将在第4章讨论这个问题的答案。
输入：2个n位正整数x和y。
输出：x和y的乘积。
先决条件：n是2的整数次方。
Karatsuba乘法是RecIntMult算法的一种优化版本。我们仍然从根据a、b、c、d进行了扩展的x·y表达式（1.1）开始。RecIntMult算法使用了4个递归调用，分别用于表达式（1.1）中的每个n/2位数之间的乘积。我们事实上并不真正关心a · d或b · c，只是关注它们的和a · d + b · c。由于我们真正关心的只有3个值：a · c、a · d + b · c和b · d，那么是不是只用3个递归调用就可以了呢？
为了观察这种想法是否可行，我们首先像前面一样以递归的方式调用a · c和b · d。
步骤1：用递归的方式计算a · c。
步骤2：用递归的方式计算b · d。
if n = 1 then //基本条件
通过单个步聚计算出x·y并返回结果
else // 递归条件
a, b := x的前半部分和后半部分
c, d := y的前半部分和后半部分
使用小学加法计算p:= a + b和q:= c + d
以递归的方法计算 ac := a·c，bd := b·d和pq:= p·q
使用小学加法计算adbc:= pq – ac – bd
使用小学加法计算10n ·ac + 10n/2·adbc + bd并返回结果我们不再递归地计算a · d 或b · c，而是递归地计算a + b和c + d的乘积[11]。
步骤3：计算a + b和c + d（使用小学加法），并以递归的方式计算(a + b)·(c + d)。
Karatsuba乘法所使用的关键技巧来源于19世纪早期的著名数学家Carl Friedrich Gauss，这是他在思考复数乘法时所想到的方法。从步骤3的结果中减去前两个步骤的结果所得到的值正是我们所需要的，也就是表达式（1.1）中a · d + b · c的中间系数：
步骤4：从步骤3的结果中减去前两个步骤的结果，获得a · d + b · c的值。
最后一个步骤就是计算表达式（1.1），其方法与RecIntMult算法相同。
步骤5：在步骤1的结果后面加上n个0，在步骤4的结果后面加上n/2个0，然后将它们与步骤2的结果相加，以计算表达式（1.1）。
Karatsuba
Karatsuba乘法只进行了3个递归调用！节省1个递归调用应该能够节省整体运行时间，但能够节省多少呢？Karatsuba算法是不是比小学乘法更快？答案并不显而易见，不过我们将在第4章引入一个方便的应用工具，用于对这类分治算法的运行时间进行分析。
关于伪码
本书在解释算法时混合使用了高级伪码和日常语言（就像本节一样）。我假设读者有能力把这种高级描述转换为自己所擅长的编程语言的工作代码。有些书籍和一些网络上的资源使用某种特定的编程语言来实现各种不同的算法。
强调用高级描述来代替特定语言的实现的第一个优点是它的灵活性：我假设读者熟悉某种编程语言，但我并不关注具体是哪种。其次，这种方法能够在一个更深入的概念层次上加深读者对算法的理解，而不需要关注底层的细节。经验丰富的程序员和计算机科学家一般也是在一种类似的高级层次上对算法进行思考和交流。
但是，要想对算法有一个深入的理解，最好能够自己实现它们。我强烈建议读者只有要时间，就应该尽可能多地实现本书所描述的算法。（这也是学习一种新的编程语言的合适借口！）每个章节最后的编程问题和支持测试案例提供了这方面的指导意见。
[5] 这种算法是Anatoly Karatsuba于1960年发现的，当时他还是一名23岁的学生。
[6] 相信读者都拥有一定的编程背景，所以应该听说过递归的概念。递归就是以子程序的形式用一个更小的输入调用自身，直到触发某个基本条件。
[7] 简单起见，我们假设n是2的整数次方。为了满足这个先决条件，一个简单的技巧就是在x和y前面添加适当数量的0，这最多可导致n的长度增加一倍。另外，当n是奇数时，把x和y分为两个几乎相同长度的数也是可行的。
[8] 递归算法还需要一个或多个基本条件，这样它才不会无限制地调用自身。在这个例子中，基本条件是x和y是一位数，此时就只用一个基本操作将它们相乘并返回结果。
[9] 在伪码中，我们使用“=”表示相等性测试，使用“:=”表示变量赋值。
[10] 递归的基本条件又被称为递归的终止条件。——译者注
[11] a + b和c + d这两个数最多可能有(n/2) + 1位数，但是这种算法仍然是适用的。
在本节中，我们第一次对一个具有相当深度的算法的运行时间进行分析，这个算法就是著名的MergeSort（归并排序）算法。
MergeSort是一种相对古老的算法，早在1945年就由约翰·冯·诺依曼提出并广为人知。我们为什么要在现代的算法课程中讨论这样的古老例子呢？
姜还是老的辣。尽管已经70岁“高龄”，但MergeSort仍然是一种可供选择的排序算法。它在实践中被一直沿用，仍然是许多程序库中的标准排序算法之一。
经典的分治算法。分治算法设计范式是一种通用的解决问题的方法，在许多不同的领域有着大量的应用。它的基本思路就是把原始问题分解为多个更小的子问题，并以递归的方式解决子问题，最终通过组合子问题的解决方案得到原始问题的答案。MergeSort可以作为一个良好的起点，帮助我们理解分治算法范式以及它的优点，包括它所面临的分析挑战。
校准预备条件。本节对MergeSort的讨论可以让读者明白自己当前的技术水平是否适合阅读本书。我假设读者具有一定的编程和数学背景（具有一定实践经验），能够把MergeSort的高级思路转换为自己所喜欢的编程语言的工作程序，并且能够看懂我们对算法所进行的运行时间分析。如果读者能够适应本节和下一节的内容，那么对于本书的剩余部分也不会有什么问题。
推动算法分析的指导原则。本节对MergeSort运行时间的分析展示了一些更加基本的指导原则，例如探求每个特定长度的输入的运行时间上界以及算法的运行时间增长率的重要性（作为输入长度的函数）。
为主方法热身。我们将使用“递归树方法”对MergeSort进行分析，这是一种对递归算法所执行的操作进行累计的方法。第4章将集合这些思路生成一个“主方法”。主方法是一种功能强大且容易使用的工具，用于界定许多不同的分治算法的运行时间，包括第1.3节所讨论的RecIntMult和Karatsuba算法。
读者很可能对排序问题以及一些解决排序问题的算法已经有所了解，我们姑且把它们放在一起。
问题：排序
输入：一个包含n个数的数组，以任意顺序排列。
输出：包含与输入相同元素的数组，但它们已经按照从小到大的顺序排列。
例如，假设输入数组是：
目标输出数组是：
在上面这个例子中，输入数组中的8个数是各不相同的。即使数组中出现了重复的数，排序也不会变得更困难，甚至变得更简单。但是，为了尽可能地简单，我们假设输入数组中的数总是不同的。我积极鼓励读者对我们所讨论的排序算法进行修改（如果可以修改），使之能够处理重复的值[12]。
如果读者并不关注运行时间的优化，那么要想实现一种正确的排序算法并不困难。也许最简单的方法就是首先对输入数组进行扫描，找到最小的元素并把它复制到输出数组的第1个元素，接着扫描并复制次小的元素，接下来依次类推。这种算法称为SelectionSort（选择排序）。读者可能听说过InsertionSort[13]（插入排序），这是同一个思路的一种更灵巧的实现方法，它把输入数组中的每个元素依次插入到有序的输出数组中的适当位置。读者可能还听说过BubbleSort（冒泡排序），它需要对一对对相邻的无序元素进行比较，并执行反复的交换，直到整个数组实现了排序。所有这些算法所需要的运行时间都是平方级的，意味着对长度为n的数组所执行的操作数量级是n2，即输入长度的平方。我们能不能做得更好？通过分治算法的范式，我们可以发现MergeSort算法较之这些简单的排序算法能够大幅度地提高性能。
理解MergeSort最容易的方法就是通过一个具体的例子（图1.3）。我们将使用1.4.2节的输入数组。
作为一种递归的分治算法，MergeSort以更小的输入数组调用自身。把一个排序问题分解为多个更小的排序问题的最简单方法就是把输入数组对半分开，并分别以递归的方式对数组的前半部分和后半部分进行排序。例如，在图1.3中，输入数组的前半部分和后半部分分别是{5, 4, 1, 8}和{7, 2, 6, 3}。通过神奇的递归（如果读者喜欢，也可以称为归纳），第一个递归调用对前半部分进行正确的排序，返回数组{1, 4, 5, 8}。第二个递归调用则返回数组{2, 3, 6, 7}。
图1.3 通过一个具体例子领会MergeSort
最后的“归并”步骤把这两个已经排序的长度为4的数组组合为一个已经排序的包含8个数的数组。下面描述了这个步骤的细节，其思路是通过索引遍历每个已经排序的子数组，并按照从左到右的有序方式生成输出数组。
输入：包含n个不同整数的数组A。
输出：包含与数组A相同整数的数组，这些整数已经按照从小到大的方式进行了排序。
图1.3大致相当于下面的伪码。对于通用的问题，它有两个递归调用和一个归并步骤。和往常一样，我们的描述并不需要逐行转换为工作代码（尽管已经相当接近）。
MergeSort
// 忽略基本条件
C := 对A的前半部分进行递归排序
D := 对A的后半部分进行递归排序
返回 Merge (C, D)这段伪码省略了一些内容，这些内容值得予以说明。作为一种递归算法，它必须有一个或多个基本条件，如果不再有进一步的递归，就直接返回答案。因此，如果输入数组A只包含0个或1个元素，MergeSort就返回该数组（它显然已经排序）。这段伪码并没有详细说明当n是奇数时，“前半部分”和“后半部分”是怎么划分的，但那种显而易见的理解（其中一半比另一半多一个元素）是可行的。最后，这段伪码忽略了怎么把两个子数组实际传递给它们各自的递归调用的实现细节。这些细节取决于编程语言。高级伪码的要点就是忽略这类细节，把注意力集中在超越任何特定编程语言的概念上。
输入：已经排序的数组C和D（每个数组的长度为n/2）。
输出：已经排序的数组B（长度为n）。
简化的先决条件：n是偶数。
我们应该怎样实现归并步骤呢？此时，两个递归调用已经完成了它们的工作，我们拥有了两个已经排序的长度为n/2的子数组C和D。我们的思路是按顺序遍历这两个已经排序的子数组，并按照从左到右的方式有序地生成输出数组[14]。
Merge
我们根据索引k遍历输出数组，根据索引i和j遍历已经排序的子数组。这3个数组都是从左向右进行遍历的。第3行的for循环实现向输出数组的传递。在第一次迭代中，这个子程序确认C或D中的最小元素，并把它复制到输出数组B的第一个位置。最小元素要么在C（此时为C[1]，因为C是经过排序的），要么在D（此时为D[1]，因为D是经过排序的）。把对应索引（i或j）的值加1就有效地略过了刚刚已经被复制的元素。再次重复这个过程，寻找C或D中剩余的最小元素（全体中的第二小元素）。一般而言，尚未被复制到B的最小元素是C[i]或D[j ]。这个子程序检查哪个元素更小，并进行相应的处理。由于每次迭代都是复制C或D中所剩下的最小的那个元素，因此输出数组确实是按有序的方式生成的。
1 i := 1
2 j := 1
3 for k := 1 to n do
4 if C[i] < D[j ] then
5 B[k] := C[i] // 生成输出数组
6 i := i + 1 // i的值增加1
7 else // D[j ] < C[i]
8 B[k] := D[j ]
9 j := j + 1和往常一样，我们的伪码有意写得比较粗略，这是为了强调整片森林而不是具体的树木。完整的实现应该要追踪C或D是否已经遍历到了数组的末尾，此时就把另一个数组的所有剩余元素都复制到数组B的最后部分（按顺序）。现在，就是读者自行实现MergeSort算法的好时机。
[12] 在实际使用中，每个数（称为键）常常具有相关联的数据（称为值）。例如，我们可能需要以社会保障号码为键对员工记录（具有姓名、工资等数据）进行排序。我们把注意力集中在对键进行排序上，并理解它能够保留与它相关联的数据。
[13] 虽说MergeSort处于统治地位，但InsertionSort在某些情况下还是非常常见的，尤其是在输入数组的长度较小的时候。
[14] 我们从1开始标识数组项（而不是从0开始），并使用“A[i ]”这种语法表示数组A的第i项。这些细节因不同的编程语言而异。
作为一个长度为n的输入数组的函数，MergeSort算法的运行时间是怎么样的呢？它是不是比更为简单的排序方法例如SelectionSort、InsertionSort和BubbleSort速度更快呢？“运行时间”表示算法的一个具体实现所执行的代码的行数。我们可以把它看成是在这个具体的实现中用调试器进行逐行追踪，每次追踪一个“基本操作”。我们所感兴趣的是在程序结束之前调试器所执行的步数。
分析MergeSort算法的运行时间是一项令人望而生畏的任务，因为它是一种会不断调用自身的递归算法。因此，在刚开始热身时，我们首先完成一个更简单的任务，就是理解在单次调用Merge子程序时（其参数是两个长度为
的已经排序的数组）所执行的操作数量。我们可以通过检查1.4.5节的代码（其中的n对应于
）直接完成这个任务。首先，第1行和第2行各自执行一项初始化操作，我们将它们计为2个操作。然后，是一个总共执行次的for循环。这个循环的每次迭代在第4行执行一个比较操作，并在第5行或第8行执行一个赋值操作，然后在第6行或第9行执行一个变量值加1的操作。在循环的每次推迭代中，循环索引k的值也要增加1。这意味着这个循环的次迭代每次都执行4个基本操作[15]。这样累加起来，我们可以推断出当Merge子程序对两个长度均为 的已经排序的数组进行归并时，最多需要执行4+ 2个操作。接下来，我们继续透支一些读者对作者的信任，采用一个粗略的不等式进一步简化任务：当≥1时，4+ 2 ≤ 6。因此，6是Merge子程序所执行的操作数量的合法上界。
辅助结论1.1（Merge的运行时间）对于每一对长度为 的已经排序的数组C和D，Merge子程序最多执行6个操作。
关于辅助结论、定理等名词
在数学著作中，最重要的技术性陈述是带编号的定理。辅助结论是一种用于协助证明定理的技术性陈述（就像Merge帮助实现MergeSort一样）。推论是一种从一个已经被证明的结果引导产生的结论，例如一个定理的一种特殊情况。对于那些本身并不是特别重要的独立的技术性陈述，我们将使用命题这个术语。
我们怎样才能从Merge子程序的简明分析转到MergeSort的分析呢？要知道递归算法会产生更多的对自身的调用，更为可怕的是递归调用数量的快速增长。随着递归深度的加深，递归调用的数量以指数级的速度增长。我们必须记住一个事实，传递给每个递归调用的输入要明显小于上一级递归调用的输入。这里存在两个相互制衡的竞争因素：一方面是需要解决的子问题的数量呈爆炸性增长；另一方面是这些子问题的输入越来越小。协调好这两个竞争因素有助于我们对MergeSort进行分析。最后，我们将证明MergeSort（包括它的所有递归调用）所执行的操作数量的上界，这是一个非常具体且实用的结论。
定理1.2（MergeSort的运行时间）对于每个长度n≥1的输入数组，MergeSort算法所执行的操作数量上界为6nlog2n + 6n，其中log2表示以2为底的对数。
关于对数
有些读者对对数这个概念十分恐惧，这毫无必要。对数实际上是一个非常“脚踏实地”的概念。对于正整数n，log2n表示下面的含义：在计算器中输入n，将它不断除以2，直到结果小于等于1，此时所执行的除法次数就是这个对数的值a。例如，32经过5次除以2的操作之后等于1，因此log2 32 = 5。1024经过10次除以2的操作之后等于1，因此log 2 1024 = 10。通过这两个例子会我们产生一个直觉，那就是log2 n的值要比n小很多（10与1024相比较），尤其是当n非常大的时候。图1.4的图形验证了这个直觉。
a 站在更正规的学术角度上，当n并不是2的整数次方时，log2n的值并不是整数，上面所描述的结果实际上是log2n向上调整为最接近的整数。我们可以忽略这些细微的差别。
图1.4 对数函数的增长速度要比恒等函数慢很多。本图的对数函数的底为2，其他底的对数函数的图形也类似
定理1.2宣布了MergeSort算法的优胜，并列出了分治算法设计范式的优点。我们提到了更简单的排序算法如SelectionSort、InsertionSort和BubbleSort的运行时间，它们与输入长度n是平方级的关系，意味着它们所需要的操作数量是稳定的n2级。在定理1.2中，其中一个n因子被log2 n所代替。如图1.4所示，这意味着MergeSort的运行速度一般要比更简单的排序算法快很多，尤其是当n非常大的时候[16]。
现在，我们对MergeSort算法进行完整的运行时间分析，这样就能理直气壮地宣称递归的分治方法所产生的排序算法比更简单的排序方法要快速得多。简单起见，我们假设输入数组的长度n是2的整数次方。我们只需要少量的额外工作就可以消除这个前提条件。
为了证明定理1.2所描述的运行时间上界，我们使用了一棵递归树，如图1.5所示[17] 。递归树方法的思路是在一个树结构中写出一个递归调用所完成的所有工作，树的节点对应于递归调用，一个节点的子节点对应于该节点所制造的递归调用。这个树结构向我们提供了一种条理化的方式归纳MergeSort通过所有的递归调用所完成的所有工作。
图1.5 MergeSort递归树。节点对应于递归调用。第0层对应于MergeSort的最外层调用，第1层对应于它的递归调用，接下来以此类推
递归树的根对应于MergeSort的最外层调用，其输入就是原始输入数组。我们称之为这棵树的第0层。由于MergeSort的每个调用会产生2个递归调用，因此这是棵二叉树（即每个节点有两个子节点）。这棵树的第1层具有2个节点，分别对应于最外层调用所制造的两个递归调用，一个作用于输入数组的左半部分，另一个作用于输入数组的右半部分。第1层的两个递归调用各自又制造两个递归调用，分别对原始输入数组的某四分之一部分进行操作。这个过程继续进行，最终到达递归的底部，即它们所处理的子数组的长度为1或0（基本条件）。
小测验1.1
当输入数组的长度为n时，递归树的层数大致有多少层？
（a）常数（与n无关）
（b）log2 n
（c）
（d）n
（关于正确答案和详细解释，参见第1.5.4节）
这棵递归树提出了一种特别方便的方法对MergeSort所完成的工作进行逐层计数。为了实现这个思路，我们需要理解两样东西：首先是特定的第j层递归的所有子问题的数量，其次是传递给这些子问题的输入数组的长度。
小测验1.2
什么是模式？在下面的句子空白处填上正确的答案：在递归树的第j层（j = 0、1、2……），共有（ ）个子问题，它们分别对一个长度为（ ）的子数组进行操作。
（a）分别是2j和2j
（b）分别是n/2j和n/2j
（c）分别是2j和n/2j
（d）分别是n/2j和2j
（关于正确答案及详细解释，参见第1.5.4节）
现在我们使用这个模式对MergeSort所执行的操作进行总结。我们逐层进行处理，先固定到该递归树的第j层。第j层递归调用一共完成多少工作呢（不包括它们的下层递归调用所执行的工作）？通过对MergeSort的代码进行检查，我们可以发现它只完成3项工作：执行两个递归调用，并对它们返回的结果调用Merge子程序。因此，忽略了下层的递归调用所完成的工作之后，第j层的子程序所完成的工作实际上就只有Merge所完成的工作。
从辅助结论1.1中，我们已经知道Merge最多执行6个操作，其中是该子程序的输入数组的长度。
概括上面这些信息，我们可以把第j层的递归调用（不包括下层的递归调用）所完成的工作表达为：
根据小测验1.2的答案，我们知道第1项等于2j，每个子问题的输入长度是n/2j。取=n/2j，辅助结论1.1提示每个第j层子问题最多执行6n/2j个操作。我们可以总结如下：第j递归层所有的递归调用所执行的操作数量最多不超过
。
引人注目的是，特定的第j层所完成的工作居然与j无关！也就是说，递归树的每一层所执行的操作数是相同的。这就为两个竞争因素提供了完美的平衡——子问题的数量在每一层都扩大一倍，但子问题所完成的工作量在每一层都减半。
我们感兴趣的是递归树的所有层次所执行的操作数量。根据小测验1.2的答案，递归树一共有log2 n + 1层（从第0层到第log2 n层）。由于每一层的操作数量上界是6n，我们可以把全部操作数量界定为
它与定理1.2所宣布的上界是匹配的。Q.e.d.[18]
关于基本操作
我们根据算法所执行的“基本操作”的数量来衡量像MergeSort这样的算法的运行时间。直觉上看，一个基本操作执行一个单一的任务（例如加法、比较或复制），并且只涉及少数的几个简单变量（例如32位整数[19] ）[20] 。
警告：在一些高级编程语言中，一行代码的背后可能包含大量的基本操作。例如，一行访问一个很长的数组的每个元素的代码所包含的基本操作的数量是与该数组的长度成正比的。
正确答案：（b）。正确答案为log2n。原因是递归每深入一层，输入数组的长度缩小一半。如果第0层的输入长度是n，第1层的递归调用是对长度为n/2的数组进行操作，第2层的递归调用是对长度为n/4的数组进行操作，接下来以此类推。当满足基本条件即输入数组的长度不大于1时，递归就到达了底部，不会再产生新的递归调用。那么，一共需要多少层的递归呢？它就是把n不断除以2最终得到不大于1的结果时所执行的除法次数。由于n是2的整数次方，所以这个层数正好就是log2 n（如果没有n是2的整数次方这个先决条件，就是log2 n向上取最接近的整数）。
正确答案：（c）。正确答案是在第j层递归中共有2j个子问题。首先观察第0层，它一共只有1个递归调用。第1层一共有2个递归调用。由于MergeSort调用它自身2次，所以每一层的递归调用的数量是前一层的两倍。这种连续的倍增意味着在递归树的第j层共有2j个子问题。类似，由于每个递归调用所接受的输入数组的长度只有前一层的一半，因此在经历了j层递归之后，输入长度已经缩减为n/2j。或者我们可以换另一种论证方式，我们已经知道第j层共有2j个子问题，原始输入数组（长度为n）被均匀地划分给这些子问题，因此每个子问题所处理的正好是长度为n/2j的输入数组。
[15] 有些人可能觉得4这个数字并不精确。每次迭代时把循环索引k与它的上界进行比较是不是也要算成是一个额外的操作（这样总数就是5个基本操作）？1.6节将会解释为什么类似这样的计数差别的影响微乎其微。出于作者与读者之间的信任，读者只要认可每次迭代执行4个基本操作就可以了。
[16] 关于这方面的讨论，可以参考第1.6.3节。
[17] 基于某些原因，计算机科学家一般把树看成是向下生长的。
[18]“Q.e.d.”是quod erat demonstrandum的缩写，表示“证明完毕”。在数学著作中，它出现在证明过程的最后，表示证明已经完成。
[19] 这个32位并不表示整数的数字个数，而是它的底层实现采用32个二进制位。——译者注
[20] 我们可以给出更精确的定义，但是并没有必要。
完成了第一个算法分析（定理1.2的MergeSort）之后，现在是时候回过头来明确与运行时间的分析及其解析有关的3个假设了。我们将采用这3个假设作为合理分析算法的指导原则，并用它们来定义“快速算法”的实际含义。
这些原则的目标是确认算法分析的最佳平衡点，在准确性和易用性之间实现平衡。
要想进行准确的运行时间分析，只有那些最简单的算法才有可能。在更多的情况下，我们需要妥协。另一方面，我们并不想在倒洗澡水的时候把婴儿一起倒掉。我们仍然希望自己的数学分析能够预测一种算法在实际使用中是快速的还是缓慢的。一旦我们找到了正确的平衡，就可以为数十种基本算法提供良好的运行时间保证。这些保证将为我们绘制一幅精确的图像，让我们明白哪种算法更为快速。
对于每个长度为n的输入数组，定理1.2中的运行时间上界log2 n + 6n都是适用的，不管数组的内容是什么。对于输入数组，除了它的长度n之外，我们并没有对它作其他任何假设。假想一下，如果有个充满恶念的人，他的生活目标就是编造一个恶意的输入数组，其目的是使MergeSort运行得尽可能地缓慢，但log2 n + 6n这个上界仍然可以被满足。这种类型的分析称为最坏情况分析，因为它给出了一个运行时间上界。即使遇到“最坏的”输入，这个上界仍然是有效的。
在MergeSort的分析中考虑最坏情况是再自然不过的事情，除此之外我们还可以考虑什么呢？另一种方法是“平均情况分析”，它对一种算法的平均运行时间进行分析，它需要对不同输入的相对频率作出一些假设。例如，在排序程序中，我们可以假设所有的输入数组都是相差不大的，这样就可以研究不同排序算法的平均运行时间了。还有一种替代方法是只观察一种算法在一个较小的“基准实例”集合上的性能，这些实例被认为是具有代表性的，可以代表“典型的”或“现实世界的”输入。
了解了问题的领域知识并理解哪些输入更具代表性之后，平均情况分析和基准实例分析都是非常实用的。最坏情况分析并不需要考虑输入，它更适用于通用目的的子程序，其设计目标就是范围很广的应用领域。为了使算法的适用性更广，它们更专注于通用目的的子程序，因此一般使用最坏情况来判断算法的性能。
最坏情况分析还有一个额外的优点。相比其他分析，它通常更容易用数学方法实现。这也是我们的MergeSort分析很自然地采用最坏情况分析的原因，即使我们根本没有专注于最坏情况的输入。
第2个和第3个指导原则是密切相关的。我们称第2个原则为全局分析（注意，它并不存在标准术语）。这个原则表示我们没必要在考虑运行时间上界时过多地关心较小的常数因子或低阶项。我们已经在MergeSort的分析过程中看到了这种思维：在分析Merge子程序的运行时间时（辅助结论1.1），我们首先证明操作数的上限是4 + 2（其中 是输出数组的长度），然后采用了更简化的上限6 ，尽管这样会导致常数因子比实际的更大。那么，为什么要采用这种粗放的常量因子表示方法呢？
便于数学处理。进行大局分析的第一个理由是它比那些需要确定精确的常数因子或低阶项的方法更容易进行数学处理。这个论点已经在我们对MergeSort的运行时间分析时得到了印证。
常数因子往往依赖于环境。第二个理由并不是那么显而易见，但它是非常重要的。在我们用来描述的算法（例如MergeSort）的粒度层中，我们很容易被误导从而过于重视常数因子的准确性。例如，在对Merge子程序进行分析时，对于循环的每次迭代所执行的“基本操作”的数量存在歧义（4个、5个，还是别的数量？），对同一段伪码的不同解释可能会导致不同的常数因子。当伪码被翻译为某种特定的编程语言的具体实现并进一步转换为机器代码时，这种歧义会进一步加深。常数因子不可避免地依赖具体所使用的编程语言、特定的实现以及编译器和处理器的细节。我们的目的是把注意力集中在那些与编程语言和计算机体系结构的细节无关的算法属性上，并且这些属性并不受到运行时间上界中的较小常数因子的变化的影响。
预测能力的损失有限。第三个理由也是我们决定忽略常数因子的根本原因。读者可能担心忽略常数因子会导致我们迷失，误以为自己的算法很快，但在实际使用中速度却要慢很多（或者反过来误以为很慢，实际上速度还可以）。我可以告诉读者一个愉快的消息，至少对于本书所讨论的算法，这种情况是不会发生的[21] 。即使我们忽略了低阶项和常数因子，我们所进行的数学分析的定性预测能力仍然是高度精确的。当算法分析告诉我们一种算法速度较快时，它在实际使用中也是比较快速的，反过来也是如此。因此，虽然全局分析忽略了一些信息，但它保留了我们真正需要的东西：关于哪些算法较之其他算法速度更快的指导方针[22]。
第三个也是最后一个原则是使用渐进性[23] 分析，把注意力集中在当输入长度n增长时算法的运行时间的增长率上。在我们解释MergeSort的运行时间上界6n log2 n + 6n（定理1.2）时，很显然可以看到运行时间对更大输入长度的倾斜。然后，我们就可以自豪地宣布MergeSort比那些运行时间与输入长度的平方呈正比的更简单排序算法（例如InsertionSort）要优越很多。但这个结论正确吗？
举一个具体的例子，假设有一种算法，它对一个长度为n的数组进行排序时最多执行
个操作，考虑下面这个比较：
在图1.6（a）中观察这两个函数的表现，我们可以看到当n较小时（不大于90），是个更小的表达式，但是当n较大时，6n log2 n + 6n就是那个更小的表达式。因此，当我们表示MergeSort比更简单的排序算法速度更快时，实际上有个前提，就是它所处理的数据足够大量。
我们为什么更关注大量数据而不是少量数据呢？因为大量数据才是优秀算法真正的用武之地。我们可以想到的几乎所有排序方法都可以在现代计算机上瞬间完成一个长度为1000的数组的排序，此时根本不需要学习什么分治算法。
由于计算机过度肯定会变得越来越快，读者可能会疑惑所有的计算问题最终是否都会变得很容易解决。事实上，计算机的速度越快，渐进性分析也就越重要。计算目标总是随着计算能力的增长而不断扩大。因此，随着时间的变迁，我们将会考虑越来越庞大的问题规模。随着输入长度的增加，具有不同的渐进性运行时间的算法之间的性能差距只会变得更大。例如，图1.6（b）显示了当n的值较大（但仍然不算特别巨大）时，函数6n log2 n + 6n和之间的差别。当n = 1500时，它们之间的差异大致达到10倍。如果我们把n的值再扩大10倍、100倍甚至1000倍，达到非常大的问题规模，这两个函数之间的性能差别会变得更加巨大。
（a）n的值较小
（b）n的值中等
图1.6 当n增长时，函数.的增长速度要比6n log2 n + 6n更快。（b）中的x轴和y轴的刻度分别是（a）中对应刻度的10倍和100倍
我们可以换种不同的思路来考虑渐进性分析，假设时间预算是固定的（例如一小时或一天），那么可解决的问题大小是如何随着计算能力的增加而扩大呢？如果一种算法的运行时间与输入长度成正比，当计算能力扩大为原先的4倍后，相同时间内可以解决的问题规模就是原先的4倍。如果一种算法的运行时间与输入长度的平方成正比，那么相同时间内可以解决的问题规模就只有原先的2倍。
我们的3个指导原则提供了“快速算法”的定义，具体如下。
“快速算法”就是指算法的最坏情况运行时间随着输入长度的增加而较慢增长。
对于第一个指导原则，我们想要保证运行时间并不需要任何领域知识为前提，这也是我们把注意力集中在算法的最坏情况运行时间的原因。第二个和第三个指导原则表示常数因子往往依赖于编程语言和计算机，并且我们感兴趣的是大型的问题，这是我们把注意力集中在算法的运行时间增长率的原因。
算法的运行时间“较慢增长”是什么意思呢？对于我们将要讨论的几乎所有问题，至高目标就是线性时间算法，即算法的运行时间与输入长度呈正比。线性时间甚至优于MergeSort的运行时间上界，后者是与n log n成正比，因此是一种温和的超线性。我们将会讨论某些问题的线性时间算法，但不会涵盖所有问题。在任何情况下，它是我们可以企及的最高目标。
无代价的基本算法
我们可以把具有线性或近线性运行时间的算法看成是可以在本质上“无代价”使用的基本算法，因为它所消耗的计算数量较之读取输入也多不了多少。排序是一种典型的无代价基本算法的例子，我们还会学习一些其他的无代价基本算法。如果有一种基本算法能够以令人炫目的速度解决问题，为什么不使用它呢？例如，我们总是可以在一个预处理步骤中对数据进行排序，尽管当时并不清楚这种排序是否真正有用。《算法详解》系列的目标之一就是在读者的算法工具箱中存储尽可能多的无代价基本算法，以让读者可以随时愉快地使用它们。
[21] 存在一个可能的例外，即第6.3节所讨论的确定性线性时间选择算法。
[22] 但是，了解相关的常数因子也是非常有益的。例如，在许多程序库所提供的一个MergeSort高度优化的版本中，当输入数组的长度较小时（例如只有7个元素），它就从MergeSort切换为InsertionSort（因为它的常数因子更小）。
[23] 渐进性这个翻译并不直观，也是犹豫很久才决定使用的。它表示算法的运行时间随着输入长度的变化而变化的速度。——译者注
问题1.1 假设我们对下面这个输入数组运行MergeSort：
我们把目光定位到最外层的两个递归调用完成之后，但在最后的Merge步骤执行之前。考虑把这两个递归调用所返回的包含5个元素的输出数组连在一起形成一个包含10个元素数组，它的第7个数是什么？
问题1.2 考虑对MergeSort算法进行下面的修改：把输入数组分为3个部分（而不是分成两半），采用递归的方式对每个部分进行排序，最终使用一个对3个数组进行操作的Merge子程序对结果进行组合。这种算法作为输入数组的长度n的函数，它的运行时间是什么呢？读者可以忽略常数因子和低阶项。【提示：在实现Merge子程序时仍然可以保证操作数量与输入数组的长度呈正比。】
（a）n
（b）n log n
（c）n(log n)2
（d）n2log n
问题1.3 假设有k个已经排序的数组，每个数组包含n个元素，我们需要把它们合并为一个包含kn个元素的数组。一种方法是反复使用第1.4.5节的Merge子程序，首先合并前两个数组，接着把合并后的数组与第三个数组合并，然后再与第四个数组合并，接下来依次类推，直到合并了第k个输入数组。这种连续的归并算法（作为k和n的函数）的运行时间是什么呢？忽略常数因子和低阶项。
（a）n log k
（b）nk
（c）nk log k
（d）nk log n
（e）nk2
（f）n2k
问题1.4 再次考虑把k个已经排序的数组归并为一个已经排序的长度为kn的数组这个问题。这次我们所使用的算法是把k个数组分为k/2对数组，然后使用Merge子程序合并每对数组，这样就生成了k/2个已经排序的长度为2n的数组。这个算法重复这个过程，直到最后只剩下一个长度为kn的已经排序的数组。这个过程（作为k和n的函数）的运行时间是什么？忽略常数因子和低阶项。
（a）n log k
（b）nk
（c）nk log k
（d）nk log n
（e）nk2
（f）n2k
问题1.5 假设有一个包含n个不同的数的未排序数组，其中n是2的整数次方。提供一种算法，确认数组中第二大的数，最多只能使用n + log2 n – 2次比较。【提示：在找到最大数之后遗留了什么信息？】
问题1.6 用自己所擅长的语言实现Karatsuba整数相乘算法[24]。为了充分利用这个问题，在读者的程序中，乘法运算符只有出现在一对个位整数之间时才会调用该语言的乘法运算符。
作为一个具体的挑战，下面这两个64位整数相乘的乘积是什么？[25]
3141592653589793238462643383279502884197169399375105820974944592
2718281828459045235360287471352662497757247093699959574966967627
[24] 深入思考：如果每个整数的位数是2的整数次方，事情会不会变得更加简单？
[25] 如果读者需要获得帮助，或者想与其他读者的作业进行比较，可以访问www.algorithmsilluminated.org的讨论区。
