算法学习指南

版权信息

书名：算法学习指南

ISBN：978-7-115-59244-6

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

著    [美] 乔治•海涅曼（George Heineman）

译    徐 波

责任编辑 郭 媛

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

读者服务：

微信扫码关注【异步社区】微信公众号，回复“e59244”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。

版权声明

Copyright © 2021 George T. Heineman. All rights reserved.

Simplified Chinese Edition, jointly published by O’Reilly Media, Inc. and Posts & Telecom Press, 2022. Authorized translation of the English edition, 2021 O’Reilly Media, Inc., the owner of all rights to publish and sell the same.

All rights reserved including the rights of reproduction in whole or in part in any form.

本书中文简体字版由O’Reilly Media, Inc.授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式复制或抄袭。

版权所有，侵权必究。

内容提要

本书介绍算法领域的一些常见算法，如搜索、排序、散列、查找最短路径和检测环路等；讨论与算法密切相关的一些数据结构与数据类型，如数组、链表、二叉树、散列表、堆栈和图等；重点阐述算法和数据结构之间的选择。除此之外，本书还深入浅出地阐述算法复杂度的原理，并通过大量的实验数据帮助读者理解各种不同时间复杂度的算法的行为。

本书在解释算法的工作原理时，就像讲故事一样娓娓道来，并提供大量的实验数据，对不同算法的运行时间性能进行比较。本书所提供的算法实现，采用的是实际代码而不是伪码，读者可以直接在自己的计算机上运行这些代码，切身感受算法的行为和性能。书中描述算法的Python代码并没有使用任何复杂的语法结构，因此对Python稍有了解甚至不了解的读者（当然至少要熟悉一种其他编程语言），在阅读本书的代码时应该也不会感到困难。

本书尤其适合计算机相关专业的大学生和其他相关领域的编程爱好者学习算法时使用，可为读者深入学习算法打下坚实基础。

O'Reilly Media，Inc.介绍

O' Reilly以“分享创新知识、改变世界”为己任。40多年来我们一直向企业、个人提供成功所必需之技能及思想，激励他们创新并做得更好。

O' Reilly业务的核心是独特的专家及创新者网络，众多专家及创新者通过我们分享知识。我们的在线学习（Online Learning）平台提供独家的直播培训、图书及视频，使客户更容易获取业务成功所需的专业知识。几十年来，O' Reilly图书一直被视为学习开创未来之技术的权威资料。我们每年举办的诸多会议是活跃的技术聚会场所，来自各领域的专业人士在此建立联系，讨论最佳实践并发现可能影响技术行业未来的新趋势。

我们的客户渴望做出推动世界前进的创新之举，我们希望能助他们一臂之力。

业界评论

“O' Reilly Radar博客有口皆碑。”

　　　　　　——Wired

“O' Reilly凭借一系列非凡想法（真希望当初我也想到了）建立了数百万美元的业务。”

　　　　　　——Business 2.0

“O' Reilly Conference是聚集关键思想领袖的绝对典范。”

　　　　　　——CRN

“一本O' Reilly的书就代表一个有用、有前途、需要学习的主题。”

　　　　　　——Irish Times

“Tim是位特立独行的商人，他不光放眼于最长远、最广阔的领域，并且切实地按照Yogi Berra的建议去做了:‘如果你在路上遇到岔路口，那就走小路。’回顾过去，Tim似乎每一次都选择了小路，而且有几次都是一闪即逝的机会，尽管大路也不错。”

　　　　　　——Linux Journal

序

算法是计算机科学的核心，对于信息时代的发展是至关重要的。它们驱动着搜索引擎，对每天数以十亿计的互联网搜索请求做出响应，并在人们通过互联网进行通信时提供隐私保护。从定制广告到在线价格查询的许多领域中，算法在消费者面前不断展现它们的身影。新媒体中涌现了许多对什么是算法以及算法可以做什么的讨论。

STEM（科学、技术、工程、数学）的快速发展推动了全球经济的可持续增长和革新的新浪潮。但是，还没有足够多的计算机科学家去发现医学、工程学甚至政府部门所需要的算法并对它们进行应用。我们需要让更多的人知道如何把算法应用于自己的领域和解决学科内的各种问题。

读者并不需要完成计算机科学专业4年的学习才能开始学习算法。遗憾的是，关于算法的大多数在线材料和教科书都是为大学毕业生而设计的，重点介绍数学证明和计算机科学的概念。算法教科书很容易让人心怀畏惧，因为它们讨论了众多不同的算法，其中包含无数的变型和高度特定的案例。读者往往还没有读完这类教科书的第1章就打起了退堂鼓。

使用这类教科书类似于通过阅读一本完整的字典来提高英语拼写能力。如果有一本专门的参考书，总结了最容易拼错的100个英语单词，并解释了这些单词的组成规则（或特例），显然能够带来更大的帮助。类似地，要在自己的工作中使用算法的不同背景和经验的人们需要这样一本更重视他们需求的参考书。

本书对一些算法进行了通俗易懂的介绍，使读者可以迅速提高自己的代码运行效率。本书所有的算法都是用Python描述的，它是特别流行的也是对用户特别友好的编程语言之一，其运用的范围涵盖了数据科学、生物信息和工程学等。本书对每个算法进行了详细的解释，并用大量的插图帮助读者理解算法本质。本书的代码是开源的，可以免费从所提供的代码库中获取。

本书将会讲述计算机科学中的基本算法和数据结构，帮助读者编写更加高效的代码。如果读者正在寻找一份需要编程技巧的技术型工作，本书有可能帮助其在面试中表现优异。我希望本书能够激发读者进一步学习算法的兴趣。

Zvi Galil

佐治亚理工学院计算机系荣誉主任

Frederick G. Storey计算项目负责人

亚特兰大，2021年5月

前　　言

本书的目标读者

对于正准备阅读本书的读者，我希望你已经有一些编程语言（例如Python）的基础；如果你之前从来没有接触过编程，建议首先学习一门编程语言，然后进行本书的学习！我在本书中使用了Python，因为它对程序员和初学者来说都很容易使用。

算法的目标是解决软件应用程序中经常出现的问题。为大学生讲授算法时，我试图在学生的背景知识和我所讲授的算法概念之间架起一座桥梁。许多教科书虽然编写得非常精美，但在算法解释方面还是太过简单。如果没有一份指南向学生解释如何浏览算法材料，学生们常常无法自学算法。

我将通过一段文字和图P-1来说明本书的目标。我将介绍一些数据结构，并解释如何使用基本的固定长度的数据类型（例如32位的整型或64位的浮点型）对数据进行组织。有些算法，例如二分数组搜索，是直接在数据结构上工作的。更复杂的算法，尤其是图的算法，依赖于一些基本的抽象数据类型。对于抽象数据类型，我会在必要的时候进行介绍，例如堆栈或优先队列。这些数据结构提供了基本操作，可以通过选择正确的数据结构来高效实现。在本书的最后，我将带领读者理解各种不同的算法是如何实现它们的性能的。对于这些算法，我要么用Python展示完整的实现，要么介绍提供了高效实现的第三方Python程序包。

在本书所提供的相关代码资源中，读者将会看到每一章都有一个名为book.py的Python文件，执行这个文件能够生成书中的所有表格。

图P-1　本书技术内容的总结

在本书第1～7章的章末有挑战练习，为读者提供测试自己所学习的新知识的机会。我希望读者在查看我所提供的示例解决方案之前尝试自己完成这些练习。我所提供的解决方案可以在本书配套的代码库中找到。

关于代码

本书的所有代码都可以在相关联的GitHub代码库http://github.com/heineman/ LearningAlgorithms中找到。这些代码兼容了Python 3.4或更高版本。在相关的时候，我将遵循 Python 的典型做法，使用双下画线方法，例如__str()__和__len()__。在本书的代码实例中，我使用了两个空格的缩进以减少代码占据页面的宽度，而在代码库中使用了标准的4个空格的缩进。在一些代码清单中，我采用了简洁的单行代码格式，例如if j == lo:break这样的if语句。

本书的代码使用了3个外部的、开放源代码的Python程序库，具体如下。

● NumPy 1.19.5。

● SciPy 1.6.0。

● NetworkX 2.5。

NumPy和SciPy都是极为常见的开源Python程序库，具有极广泛的用户。我使用这两个程序库对算法的运行时间性能进行分析。NetworkX提供了许多适用于图的不同高效算法（详见第7章），它还提供了一种可以直接使用的图数据结构的实现。这些程序库使我不必“事必躬亲”。如果读者没有安装这些程序库，也不会有什么问题，因为我提供了一些应急措施。

本书使用timeit模块所生成的所有计时结果都是通过反复运行代码片段所得的。代码片段常常需要重复运行多次，以保证它所测量的时间是正确的。在运行一定的次数之后，最短的时间（而不是所有运行时间的平均值）被当作运行时间性能。这通常被认为是生成准确计时方案的有效方式，因为多次运行的平均时间在运行受到外部影响（例如操作系统所执行的其他任务）时会影响计时结果。

当一种算法（例如第5章的插入排序）的性能对它的输入高度敏感时，我将会清楚地说明采用所有计时结果的平均时间。

本书的代码库所包含的Python代码超过10,000行，读者可以通过脚本执行本书中的所有测试用例并计算书中的所有表格数据。本书的许多图表可以重新生成。本书的代码按照Python的Docstring约定进行文档说明，代码的覆盖率使用Coverage.py网站检验达到了95%。

如果读者发现技术问题，或者在使用代码示例时遇到问题，可以通过异步社区中的本书页面与我们联系。

本书是为了帮助读者更好地完成工作。一般而言，对于本书所提供的示例代码，读者可以在自己的程序和文档中使用它们，并不需要联系我们以获得许可，除非读者复制了大块的代码。例如，在编写程序时使用了本书的几段代码并不需要许可，但是，销售或发布O’Reilly图书的示例代码需要得到我们的许可；引用本书以及书中的示例代码并不需要获得许可，但是把本书的大量示例代码复制到自己产品的文档中需要获得许可。

我们赞赏注明出处，但一般情况下并不要求。出处注明通常包括书名、作者、出版商和ISBN。例如，《算法学习指南》（Learning Algorithms: A Programmer’s Guide to Writing Better Code），作者George Heineman（O’Reilly）。

如果读者觉得自己对本书的示例代码的使用超出了正常范围或者超出上面的许可，可以通过permissions@oreilly.com与我们联系。

本书所使用的约定

下面是本书所采用的印刷约定。

黑体：表示新的术语及我想要强调的要点。

等宽字体：在程序清单中使用，也用于在段落中表示程序内容，例如变量或函数名、数据类型和关键字。

这种由环尾狐猴所提示的内容是提示或建议。我使用这幅图像的原因是环尾狐猴的联合视野最大可达280°，大于一般的灵长类动物（例如人类）。当出现这个提示图标时，我一般要求读者拓宽自己的视野，去了解一个新的概念或一个新的Python功能。

这种由乌鸦所提示的内容为基本的备注。大量的科研人员发现乌鸦是非常聪明的，是一种能够解决问题的动物，有些乌鸦甚至能够使用工具。我使用这一图标来表示定义新术语或向读者展示一个实用概念，读者在阅读接下来的内容之前应该理解这个术语或实用概念。

这种由蝎子所提示的内容为警告。我使用蝎子图标来提醒读者在应用算法时必须处理的关键挑战。

O’Reilly在线平台学习（O’Reilly Online Learning）

近40年来，O’Reilly Media致力于提供技术和商业培训、知识和卓越见解，来帮助众多公司取得成功。

我们拥有独一无二的专家和革新者组成的庞大网络，他们通过图书、文章、会议和我们的在线学习平台分享知识和经验。O’Reilly的在线学习平台允许你按需访问现场培训课程、深入的学习路径、交互式编程环境，以及O’Reilly和200多家其他出版商提供的大量文本和视频资源。更多相关信息请访问http://oreilly.com。

联系我们

如果读者对本书有任何的评论或疑问，可以与出版社联系。

美国：

O’Reilly Media, Inc.

1005 Gravenstein Highway North

Sebastopol, CA 95472

中国：

北京市西城区西直门南大街2号成铭大厦C座807室（100035）
奥莱利技术咨询（北京）有限公司

我们为本书提供了一个网页，其中包含勘误表、示例和其他的额外信息，读者可以通过https://oreil.ly/learn-algorithms进行访问。

如果你对本书有什么评论或技术上的建议，请发送电子邮件到 bookquestions@oreilly.com。

关于我们的图片和课程的新闻和信息，可以访问http://oreilly.com。

致谢

我认为，算法的研究是计算机科学最精华的部分。感谢读者给我机会展示本书的内容。我还想感谢我的妻子Jennifer，感谢她在本书以及我的另一本著作的编写过程中所给予的支持。感谢我的两个儿子Nicholas和Alexander，他们现在已经长大，已经可以开始学习编程了。

感谢O’Reilly的编辑Melissa Duffield、Sarah Grey、Beth Kelly和Virginia Wilson，感谢他们在组织本书的概念及解释的过程中对我的帮助，他们的帮助有效地提高了本书的质量。感谢本书的技术审稿人员Laura Helliwell、Charlie Lovering、Helen Scott、Stanley Selkow和Aura Velarde，感谢他们减少了书中的不一致之处，提高了算法实现及其解释的质量。如果书中还存在任何缺陷，那肯定都是我自己的责任。

服务与支持

本书由异步社区出品，社区（https://www.epubit.com）可为您提供后续服务。

您还可以扫码右侧二维码， 关注【异步社区】微信公众号，回复“e59244”直接获取,同时可以获得异步社区15天VIP会员卡，近千本电子书免费畅读。

提交错误信息

作者、译者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。

当您发现错误时，请登录异步社区，按书名搜索，进入本书页面（见下图），单击“提交勘误”，输入错误信息后，单击“提交”按钮即可。本书的作者、译者和编辑会对您提交的错误信息进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。

扫码关注本书

扫描下侧的二维码，您将会在异步社区微信公众号中看到本书信息及相关的服务提示。

与我们联系

我们的联系邮箱是contact@epubit.com.cn。

如果您对本书有任何疑问或建议，请您发电子邮件给我们，并请在电子邮件标题中注明书名，以便我们更高效地做出反馈。

如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发电子邮件给我们；有意出版图书的作者也可以到异步社区在线投稿（直接访问www.epubit.com/contribute即可）。

如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发电子邮件给我们。

如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发电子邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。

关于异步社区和异步图书

“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网。

“异步图书”是由异步社区编辑团队策划出版的精品IT图书的品牌，依托于人民邮电出版社近40年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的Logo。异步图书的出版领域包括软件开发、大数据、人工智能、测试、前端、网络技术等。

异步社区

微信服务号

第1章　解决问题

学习目标

● 学习解决一个入门级问题的多种算法。

● 对于一个规模为N的问题实例，学习如何分析算法的性能。

● 当解决一个特定的问题实例时，学习如何对一个关键操作的调用次数进行统计。

● 当一个问题实例的规模扩大一倍时，学习如何确定运行时间的增长级数。

● 对于一个规模为N的问题实例，学习如何通过对一个算法所执行的关键操作的次数进行统计来评估它的时间复杂度。

● 对于一个规模为N的问题实例，学习如何通过确定一个算法所需要的存储空间大小来评估它的空间复杂度。

现在，让我们开始本章的学习之旅！

1.1　什么是算法？

解释算法的实现逻辑就像讲故事一样。算法会在普通的解决方案中引入新颖的思路或进行某种创新。在本章中，我们将讨论一个简单问题的几个解决方案，解释影响算法性能的一些因素。在这个过程中，我将介绍一些用于分析算法性能的技巧。这些技巧与算法的实现无关，尽管我在讨论中总是会提供实际实现的实验证据。

算法是一种逐步解决问题的方法，可实现为计算机程序的形式，能够在可预测的时间内返回正确的结果。算法的研究既要关注正确性（它对于所有的输入是否都能发挥作用？），也要关注性能（它是解决这个问题的最有效方法吗？）。

下面我们详细观察一个算法的例子，看看它实际上是怎么处理问题的。如果我们想在一个无序列表中查找最大值，应该怎么办？图1-1中的每个Python列表都是一个问题实例（problem instance），也就是算法（用圆柱体显示）所处理的输入。正确答案出现在算法的右边。这个算法是如何实现的？它在不同的问题实例上是如何执行的？我们能不能预测在一个包含1,000,000个值的列表中查找最大值所需要的时间？

图1-1　一个算法所处理的3个不同的问题实例

算法不仅仅是一种问题解决方法。实现算法的程序还需要在可预测的时间内完成任务。Python的内置函数max()已经解决了上面这个问题。现在，对于包含随机数据的问题实例，预测算法的性能可能比较困难，因此找到精心构建的问题实例是极有价值的。

表1-1显示了在两种类型的规模为N的问题实例上执行max()需要的时间。一种是以升序排列的整数列表，另一种是以降序排列的整数列表。由于读者所使用的计算机系统的配置不同，得到的执行结果可能与表中的不同，但仍然符合下面这两个结论：

● 当N足够大时，在递增的值上执行max()需要的时间总是要多于递减的值需要的时间；

● 当后面每一行的N值都为前一行的10倍时，max()的对应时间尽管稍有偏差，但大致也是原来的10倍，这也与我们的生活经验相符。

上述问题实例中，max()返回最大值，输入并没有被修改。在有些情况下，算法会直接更新问题实例而不是计算一个新值，我们将在第5章学习的对一个值列表进行排序的算法就是这样的。在本书中，N表示问题实例的规模。

表1-1　在两种类型的规模为N的问题实例上执行max()需要的时间　　单位：ms

关于执行算法所需要的时间：

● 我们无法事先预测T(100000)的值（即算法处理一个规模为100,000的问题实例所需要的时间）是多少，因为计算平台可能并不相同，实现算法所使用的编程语言也可能不同；

● 但是，一旦通过实验确定了T(10000)所需要的时间，就可以对T(100000)，也就是解决一个10倍规模的问题实例所需要的时间进行预测，尽管这种预测不可避免地和准确时间有所出入。

在设计算法时，基本的挑战是保证它的正确性，使之适用于所有的输入。我将在第2章使用更多的篇幅解释如何对解决同一个问题的不同算法的行为进行分析和比较。算法分析这个领域与现实生活中发生的有趣的、重要的问题的研究息息相关。由于算法所蕴含的数学知识理解起来具有一定的难度，我将提供一些特定的例子，实现抽象的概念与现实世界的问题的关联。

计算算法效率的标准方法是对它所需要的计算操作进行计数，但这是极难做到的！计算机中执行机器指令的中央处理器（CPU），负责执行数学计算（例如加法和乘法）、CPU寄存器的赋值、两个值的比较等任务。有些现代的编程语言（例如C或C++）被编译为机器指令，还有一些编程语言（例如Python或Java）被编译为中间字节码表示形式。Python解释器（本身是C语言程序）执行字节码，而像min()和max()这样的内置函数是用C语言实现的，最终会被编译为机器指令而执行。

强大的数组

数组是指在一块连续的内存中存储N个值的集合。它是程序员存储多个值时所使用的最“古老”也最可靠的数据结构之一。图1-2表示一个包含8个整数的数组。

图1-2　包含8个整数的数组

数组A有8个值，可根据位置进行索引。例如，A[0]=31、A[7]=5。A中的值可以是任何类型，例如字符串或者更为复杂的对象。

下面是与数组有关的一些重要知识：

● 第1个值A[0]的索引位置是0，最后一个值的索引位置是A[N–1]，其中N表示数组的长度；

● 每个数组都具有固定的长度，Python和Java允许程序员在运行时确定数组的长度，但C语言不允许；

● 可以通过索引位置i读取或更新数组中的一个单独值A[i]，i是一个0～N − 1范围内的整数；

● 数组无法直接被扩展（或收缩），但是我们可以分配一个目标大小的新数组，并把旧数组中应该保留的值复制到这个新数组。

数组非常简单，它在组织数据时具有极广的用途和极高的效率。在Python中，list（列表）对象可以看成数组，它的功能更加强大，因为它能够随时扩展和收缩。

要对一个算法所执行的机器指令的总数进行统计几乎是不可能的，何况现代的CPU每秒可以执行数十亿条指令！我将改而对每个算法所调用的关键操作的数量进行统计，这可能是“数组中两个值的比较次数”或“一个函数的调用次数”。在max()函数的讨论中，关键操作是“小于操作（<）被调用了多少次”。我将在第2章中解释这个计数原则。

现在，是时候揭开max()算法的面纱了。

1.2　在一个任意的列表中查找最大值

观察程序清单1-1展示的存在缺陷的Python实现，它试图在一个至少包含1个值的任意列表中查找最大值。它所采用的方法是把A中的每个值与my_max进行比较，如果发现一个更大的值就更新my_max。

程序清单1-1　在列表中查找最大值的算法的一种存在缺陷的实现

def flawed(A):
  my_max = 0          ❶
  for v in A:         ❷
    if my_max < v:
      my_max = v      ❸
  return my_max

❶ my_max是保存最大值的变量，在这里my_max被初始化为0。

❷ for循环定义了变量v，用于对A中的每个元素进行迭代。对v的每个值均执行一次if语句。

❸ 如果v更大，就更新my_max。

这个实现的核心是对两个数进行比较以确定其中一个值是否小于另一个值的小于操作。在图1-3中，当v依次从A中取连续的值时，我们可以看到my_max被更新了3次，从而确定了A中的最大值。flawed()函数用于确定A中的最大值，调用了6次小于操作，对每个值各调用1次。在一个规模为N的问题实例中，flawed()调用N次小于操作。

图1-3　flawed()的执行示意

这个实现存在缺陷，因为它假设A中至少有一个值大于0。计算flawed([–5,–3,–11])时将返回0，这是不正确的。一种常见的弥补方法是把my_max初始化为可能出现的最小值，例如my_max =float('-inf')。这个方法仍然存在缺陷，因为如果A是空列表[]，它就会返回这个值。现在，让我们修正这个缺陷。

Python语句range(x, y)可以产生x～y（包括x，但不包括y）的整数。我们也可以采用range(x,y,–1)的形式，它将产生从x向下计数到y（但不包括y）的整数。因此，list(range(1,7))的结果是[1,2,3,4,5,6]，list(range(5,0,–1))的结果是[5,4,3,2,1]。我们可以按照任意的步长进行计数，比如list (range(1,10,2))采用差值为2的步长，结果是[1,3,5,7,9]。

1.3　对关键操作进行计数

由于最大值实际上肯定包含在A中，因此程序清单1-2中正确的largest()函数先选择A的第1个值作为my_max，再对其他值进行检查，查找是否有其他值比它更大。

程序清单1-2　在列表中查找最大值的正确函数

def largest(A):
  my_max = A[0]                   ❶
  for idx in range(1, len(A)):    ❷
    if my_max < A[idx]:
      my_max = A[idx]             ❸
  return my_max

❶ 把my_max设置为A中位于索引位置0的第1个值。

❷ idx取1～len(A)（不包括后者）的整数。

❸ 如果A[idx]的值更大，就更新my_max。

如果对空列表调用largest()或max()，将会触发一个异常“ValueError：List index out of range exception”。这类运行时异常是程序员所犯的错误，说明他们没有理解largest()所操作的列表至少要包含一个值。

既然我们已经拥有了这个算法的一种正确的Python实现，能不能确定这个新算法调用小于操作的次数呢？能！就是N−1次。我们修正了算法的缺陷，并提高了它的性能（当然，只是提高了微不足道的一点）。

为什么对小于操作的使用进行计数很重要呢？因为它是对两个值进行比较时所使用的关键操作。其他所有程序语句（例如for或while循环）在不同的实现中可以根据实际所使用的编程语言任意选择。我们将在第2章对这个思路进行扩展，目前只要对关键操作进行计数就足够了。

1.4　可以预测算法性能的模型

如果有人向我们展示同一问题的不同算法怎么办？我们如何确定应该使用哪一种算法呢？观察程序清单1-3的alternate()算法，它反复地检查A中的每个值是否大于或等于同一个列表中的其他所有值。这个算法是否返回了正确的结果？对于规模为N的问题实例，它调用了多少次小于操作？

程序清单1-3　在A中查找最大值的另一种算法

def alternate(A):
  for v in A:
    v_is_largest = True         ❶
    for x in A:
      if v < x:
        v_is_largest = False    ❷
        break
    if v_is_largest:
      return v                  ❸
  return None                   ❹

❶ 对A进行迭代时，假设A中每个值v都可能是最大的。

❷ 如果v小于另一个值x，就停下来并记录v不是最大值。

❸ 如果v_is_largest为True，就返回v，因为它是A中的最大值。

❹ 如果A是一个空列表，就返回None。

alternate()试图在A中找到一个值v，使A中的其他值x都不会比它更大。这个算法使用了两个嵌套的for循环。现在对小于操作的调用进行计数不是很简单，因为对x进行迭代的内层for循环在发现x大于v时就会停止。另外，对v进行迭代的外层for循环一旦找到最大值也会停止。图1-4描述了alternate()在我们的列表实例上的执行过程。

图1-4　alternate()的执行过程

在这个问题实例中，小于操作被调用了14次。但是，我们可以看到这一总数取决于列表A中的特定值。如果这些值处于不同的顺序会怎么样呢？我们能不能找出小于操作的调用次数最少的值排列方式？这样的问题实例被认为是alternate()的最佳情况。如果A的第1个值是所有N个值中最大的，则调用小于操作的次数总是N。总结如下。

1．最佳情况

算法对于规模为N的问题实例需要的工作量最少。

2．最坏情况

算法对于规模为N的问题实例需要的工作量最大。

下面我们来看alternate()需要调用最多次数的小于操作的最坏情况问题实例。alternate()的最坏情况问题实例不仅要保证最大值是A的最后一个值，而且A中的值必须以升序排列。

图1-5（a）描述了最佳情况，此时A = [9,5,2,1,3,4]；图1-5（b）描述了最坏情况，此时A = [1,2,3,4,5,9]。

图1-5　alternate()在最佳情况和最坏情况下的执行示意

在最佳情况下，共调用了6次小于操作。如果在最佳情况下共有N个值，则调用小于操作的次数就是N。最坏情况则有点儿复杂。在图1-5中，我们可以看到当列表中的N个值以升序排列时，总共需要调用26次小于操作。稍微运用一些数学知识，就可以理解对于有N个值的列表，这个计数总是(N² + 3N − 2)/2。

表1-2显示了largest()和alternate()在规模为N的最坏情况问题实例上的实验数据。

表1-2　最坏情况问题实例下比较largest()和alternate(``)

对于规模较小的问题实例，alternate()的数据看上去并不是很糟糕。但是，当问题的规模倍增时，alternate()调用小于操作的次数几乎是原先的4倍，远远超过largest()中的增长幅度。表1-2的最后两列显示了这两种实现在问题规模为N时100次随机实验的运行时间。alternate()的运行时间随着输入规模的倍增而扩大约4倍。

对算法处理规模为N的随机问题实例所需要的时间进行测量时，从这组运行结果中，我选择了最快的（即最短的完成时间）。这种方法优于简单地对所有的运行时间求平均值，因为后者可能会受到各种因素的影响。

在本书中，我会提供一些像表1-2这样的表格，展示关键操作（如这个例子的小于操作）的调用次数和运行时间性能。每一行表示一个不同的问题实例的规模N的数据。从上到下阅读表格可以看到每一列的值随着问题实例的规模的倍增是如何变化的。

对小于操作的调用次数进行统计可解释largest()和alternate()的行为。当N倍增时，在largest()中小于操作的调用次数也几乎倍增，但是在alternate()中却呈几乎4倍的增长。无论N增大到多少这个规律都成立，因此这个行为具有一致性，我们可以使用这些数据预测这两个算法处理规模巨大的问题时的运行时间性能。图1-6描绘了alternate()调用小于操作的次数与它的运行时间性能的比较，显示了彼此之间的直接关联。

图1-6　小于操作调用次数和运行时间性能之间的关系

恭喜！我们已经完成了算法分析中的一个关键步骤：通过对一项关键操作的调用次数进行统计来预测两个算法的相对性能。我们当然可以接着实现这两种算法的变型（我就是这么做的），并预测这两个算法在规模倍增后的问题实例上各自的运行时间性能。但实际上这是不必要的，因为图1-6的模型已经预测了这个行为，证实了largest()是两个算法中效率更高的那个。

largest()和max()是用相同的算法实现的，但是如表1-3所示，largest()明显比max()要更慢，一般要慢3/4。原因是Python是一种解释型语言，意味着它会被编译为中间字节码再由Python解释器执行。像max()这样的内置函数的性能总是优于实现了相同功能的Python代码，因为内置函数是在解释器内部实现的。我们应该关注的是，当问题实例的规模倍增时，largest()和max()的对应运行时间性能不管在最佳情况还是在最坏情况下都会倍增。

表1-3说明了当问题实例的规模扩大之后对解决问题所需要的时间进行预测是可能的。一旦我们知道了largest()或max()在规模为N的问题实例上的最佳情况或最坏情况下的运行时间性能，就可以预测当N倍增之后的运行时间性能。现在，我们对问题稍加修改，使之更加有趣。

表1-3　largest( )和max()在最佳情况和最坏情况下的运行时间性能　　单位：ms

1.5　在一个随机列表中查找两个最大值

设计一种算法，在一个随机列表中查找两个最大值。也许我们只需要对largest()算法进行少量修改。读者可以尝试自己解决这个修改后的问题，并把自己的解决方案与程序清单1-4进行比较。程序清单1-4展示了我的解决方案。

程序清单1-4　对largest()进行修改，查找两个最大值

def largest_two(A):
  my_max,second = A[:2]                 ❶
  if my_max < second:
    my_max,second = second,my_max

  for idx in range(2,len(A)):
    if my_max < A[idx]:                 ❷
      my_max,second = A[idx],my_max
    elif second < A[idx]:               ❸
      second = A[idx]
  return (my_max, second)

❶ 保证my_max和second是A中降序排列的前两个值。

❷ 如果A[idx]是新找到的最大值，就把my_max设置为A[idx]，second就设置为旧的my_max。

❸ 如果A[idx]大于second，但小于my_max，只更新second。

largest_two()看上去与largest()相似：使my_max和second为A中的前两个值，并具有正确的顺序；然后，检查A中的每个剩下的值（剩下几个值？对！就是N − 2个）；如果发现A[idx]大于my_max，就同时更新my_max和second，否则就检查是否只有second需要更新。

对小于操作的调用次数进行统计要更加复杂，因为它还依赖于问题实例中的值。

当for循环内部的if语句的条件为真时，largest_two()调用小于操作的次数最少。当A包含以升序排列的值时，这个小于条件总是为True，因此调用次数为N − 2。不要忘了加上1，因为函数一开始就调用了1个小于操作。因此在最佳情况下，我们只需要N– 1次的小于操作调用来确定最大的两个值。elif条件中的小于条件在最佳情况下始终不会被用到。

对于largest_two()，我们能不能构建一个最坏情况的问题实例？读者可以自己尝试一下，如当for循环中的if条件中的小于条件总是False时。我相信读者肯定已经知道当A中的值以降序排列时，largest_two()调用的小于操作的次数最多。具体地说，在最坏情况下，for循环的每次迭代需要调用2次小于操作，总共就是1 + 2 × (N − 2) = 2N − 3次。这个结果看上去很符合预期，如果我们需要N − 1次的小于操作来查找A中的最大值，可能还需要另外的N − 2次小于操作（当然可以排除那个最大值）来查找第二大的值。

下面对largest_two()的操作进行总结。

● 在最佳情况下，它在N − 1次调用小于操作之后找到这两个值。

● 在最坏情况下，它在2N − 3次调用小于操作之后找到这两个值。

现在是不是完成任务了？它是解决在一个任意的列表中查找两个最大值问题的“最佳”算法吗？我们可以根据以下因素在几个算法中选择最合适的一种。

1．需要的额外的存储空间

算法是否需要创建原问题实例的一份拷贝？

2．编程复杂性

程序员至少需要编写多少行的代码？

3．可修改的输入

算法是在适当的位置对问题实例所提供的输入进行修改，还是让它保持不变？

4．速度

与问题实例所提供的输入无关的情况下，算法是否能够在速度竞争中胜出？

下面我们研究解决同一个问题的3种不同的算法，如程序清单1-5所示。①sorting_two()创建了一个新列表，包含A中以降序排列的值，然后抓取前两个值并把它们以元组的形式返回。②double_two()使用max()查找A中的最大值，将它从A的一份拷贝（copy）中删除，然后对修改后的列表再次使用max()找到第二大的值。③mutable_two()查找A中最大值的索引位置并把它从A中删除，然后把second设置为A中剩下的那个最大值，再把my_max值重新插入到原先的位置。前两种算法需要额外的存储空间，第3种算法则修改了它的输入。这3种算法都只适用于值的数量超过1个的问题实例。

程序清单1-5　使用Python工具库的3种不同算法

def sorting_two(A):
  return tuple(sorted(A,reverse=True)[:2])       ❶

def double_two(A):
  my_max = max(A)                                ❷
  copy = list(A)
  copy.remove(my_max)                            ❸
  return (my_max, max(copy))                     ❹

def mutable_two(A):
  idx = max(range(len(A)), key=A.__getitem__)    ❺
  my_max = A[idx]                                ❻
  del A[idx]
  second = max(A)                                ❼
  A.insert(idx, my_max)                          ❽
  return (my_max, second)

❶ 按降序对A进行排序，并以它的前两个值创建一个新列表。

❷ 使用内置的max()函数查找最大值。

❸ 创建原先的A的一份拷贝，并删除my_max。

❹ 返回一个元组，其中包含my_max和copy中的最大值。

❺ 这个Python技巧是查找A中最大值的索引位置，而不是查找最大值本身。

❻ 记录my_max值并把它从A中删除。

❼ 现在，在剩余的值中用max()查找最大值。

❽ 把my_max插入到原先的位置，恢复列表A。

这3种不同的算法并没有直接使用小于操作，因为它们依赖于现有的Python库函数。sorting_two()和double_two()都创建了列表A的一份拷贝，这看上去是不必要的，因为largest_two()并没有这样做。另外，为了查找两个最大值而对整个列表进行排序似乎“用力过猛”。与分析运行时间性能时对关键操作调用次数进行统计的方法相似，我将对算法所使用的额外的存储空间进行评估。对于前两种算法，额外存储空间的大小直接与N成正比。第3种算法mutable_two()通过删除A的最大值并在以后将其插入，对A进行简单的更新。这个函数的调用者可能会对原始列表被修改而感到惊讶。

如果熟悉Python技巧，就可以使用一个特殊的类RecordedItem^[1]对小于操作的调用次数进行准确的统计。表1-4说明了在列表中的值以升序排列时double_two()调用小于操作的次数最多，而在值以降序排列时largest_two()调用小于操作的次数最多。在“交替排列值小于操作调用次数”列中，524,288个值的排列方式是偶数以升序排列，而奇数以降序排列，比如当N = 8时，输入是[0,7,2,5,4,3,6,1]。

表1-4　不同算法在处理524,288个升序值、降序值和交替排列值时的小于操作调用次数

1.6节所描述的tournament_two()算法不管输入如何都具有最少数量的小于操作调用。篮球爱好者应该会非常熟悉它的逻辑。

如果确定了解决一个特定问题的算法的最坏情况问题实例，也许换种算法来解决同一个问题所受到的负面影响不会这么大。不同的算法可能具有不同的弱点，我们可以通过详尽的分析阐明这一点。

1.6　锦标赛算法

在理想情况下，参与锦标赛的队伍的数量是2的整数次方，例如16或64。锦标赛包含几个轮次，所有队伍配对进行淘汰赛，比赛负者就被淘汰，胜者进入下一轮，最终剩下的那支队伍就是锦标赛的冠军。

考虑一个N = 8的问题实例，即p = [3,1,4,1,5,9,2,6]。图1-7显示了这个锦标赛的过程，第一轮使用小于操作在8个值中取4组相邻的值进行比较，值较大的那支队伍进入下一轮^[2]。在八强战中，有4支队伍被淘汰，因此剩下的值是[3,4, 9,6]。在四强战中，[4,9]成功晋级。最后，值为9的队伍被认定为冠军。

图1-7　共8个初始值的锦标赛

在这个锦标赛中，共有7次小于操作的调用（即每场比赛调用1次），这无疑令人满意，因为这意味着和前面讨论的一样，经过N − 1次的小于操作之后就可以找到最大值，然后就可以快速找到第二大的值，如下所述。

当9被认定为最终的冠军值时，第二大的值“隐藏”在哪里呢？首先考虑4为候选的第二大值，因为它是在最终的冠军争夺战中失利的。但是，最大值9之前还赢过两场，因此我们还必须考虑另外两个失利值，它们分别是四强战的6和八强战的5。因此，第二大的值是6。

对于8个初始值，我们只需要2次额外的小于操作——（4 < 6？）和（6 < 5？）就可以确定6是第二大的值。8 = 2³并且需要3 − 1 = 2次的比较绝非巧合。结果显示，对于N = 2^K，我们需要额外的K − 1次比较，其中K表示轮次数。

当一共有8 = 2³个初始值时，算法将创建一个由3个轮次组成的锦标赛。图1-8描述了由32个初始值所组成的5轮次锦标赛。锦标赛的参赛值扩大一倍，比赛只需要增加一个轮次。换句话说，对于每个新的轮次K，可以增加2^K个参加比赛的值。想要在64个值中找到最大值，只需要6个轮次，因为2⁶ = 64。

图1-8　共32个初始值的锦标赛

为了确定任何N的轮次数，可以使用对数函数log()，它是指数函数的逆操作。当N = 8时，锦标赛需要3个轮次，因为2³ = 8并且log₂(8)=3。与计算机科学的传统相同，本书中log()操作符的底数为2。

大多数手持式计算器计算log()时所使用的底数为10。函数ln()表示底数为e（大约为2.718）的自然对数。要用计算器（或Microsoft Excel）快速计算底数为2的log(N)，可以计算log(N)/log(2)。

当N是2的整数次方时，例如64或65,536，锦标赛的轮次数是log(N)，意味着需要的小于操作的调用次数是log(N) − 1。程序清单1-6所实现的算法使用额外的存储空间记录所有比赛的结果，从而最大限度地减少了小于操作的调用次数。

程序清单1-6　使用锦标赛的方式在A中查找两个最大值的算法

def tournament_two(A):
  N = len(A)
  winner = [None]*(N-1)          ❶
  loser = [None]*(N-1)
  prior = [-1]*(N-1)             ❷

  idx = 0
  for i in range(0, N, 2):       ❸
    if A[i] < A[i+1]:
      winner[idx] = A[i+1]
      loser[idx] = A[i]
    else:
      winner[idx] = A[i]
      loser[idx] = A[i+1]
    idx += 1

m = 0                            ❹
while idx < N-1:
  if winner[m] < winner[m+1]:    ❺
    winner[idx] = winner[m+1]
    loser[idx] = winner[m]
    prior[idx] = m+1
  else:
    winner[idx] = winner[m]
    loser[idx] = winner[m+1]
    prior[idx] = m
  m += 2                         ❻
  idx += 1

largest = winner[m]
second = loser[m]                ❼
m = prior[m]
while m >= 0:
  if second < loser[m]:          ❽
    second = loser[m]
  m = prior[m]

return (largest, second)

❶ 这些数组存储第idx场比赛的胜者和负者，锦标赛中共有N − 1场比赛。

❷ 当一个值在第m场比赛中晋级时，prior[m]记录它的前一场比赛，如果这是它的第1场比赛，前一场比赛就记录为−1。

❸ 调用N/2次的小于操作，初始化前N/2对值的胜者和负者。它们表示第一轮比赛的结果。

❹ 将胜者进行配对以决出下一轮的胜者，并记录前一场比赛的索引。

❺ 需要调用额外的N/2 − 1次的小于操作。

❻ 把m向前推进2个位置，找到下一对进行比赛的胜者。当idx到达N − 1时，winner[m]就是最大值。

❼ 第二大值的初始候选者，但它必须与最大值的其他所有对战负者进行比较，找到实际的第二大值。

❽ 额外的小于操作的调用次数不会超过log(N) − 1次。

图1-9显示了这个算法的执行过程。在初始化步骤之后，原始数组A中的N个值被划分为N/2的胜者和N/2的负者。在图1-7的例子中，共有4对参赛值。在while循环的每个晋级步骤中，m和m+1前后两场比赛的胜者/负者分别被保存到winner[idx]和loser[idx]中，而prior[idx]则记录了胜者晋级之前的那场比赛（如图1-9中从右到左的箭头所示）。在经历3个晋级步骤之后，所有的比赛信息都已经被存储，然后这个算法就在最终胜者所战胜的所有对手中查找第二大值。为了直观地看到这一点，我们可以跟着箭头回溯直到结束。我们可以看到第二大值初始候选者是在loser[6]中找到的，只需要与loser[5]和loser[2]进行2次小于比较，就可以确定哪个值是最大的。

我刚刚完成了对查找A的最大值和次大值的算法的描述，对于任何值为2的整数次方的N，这种算法只需要N − 1+log(N) − 1=N+log(N) − 2次的小于调用。tournament_two()是不是很实用？它的性能是否优于largest_two()？如果只对小于操作的调用次数进行统计，tournament_two()应该更快一些。当问题规模N = 65,536时，largest_two()需要131,069次的小于操作，而tournament_two()只需要65,536 + 16 − 2 = 65,550次，约为前者的一半。但这个故事并没有结束。

表1-5显示tournament_two()比它的所有竞争者都要慢得多！我们可以记录它解决100个随机的问题实例所需要的总时间（问题规模为1,024～2,097,152）。为了清楚地说明这一点，我在表1-5中展示了程序清单1-5的不同算法的运行时间性能。注意，如果读者在自己的计算机上运行示例代码，得到的结果可能有所不同，但每一列的总体趋势却是不会改变的。

图1-9　锦标赛算法的逐步执行示意

表1-5　比较全部5种算法的运行时间性能　　单位：ms

表1-5中存在一些出乎意料的情况，注意double_two()一开始是5个解决方案中速度最快的那个，但（当N > 262,144时）largest_two()“笑到了最后”。灵活的tournament_two()算法到目前为止是最慢的。原因很简单，因为它需要分配更大的存储数组来完成处理。它的速度实在太慢，在问题规模最大的时候，我甚至没有运行它，因为它所需要的时间实在太长。

为了帮助读者理解这些数字，图1-10展示了当问题实例的规模不断扩大时这些算法的运行时间变化趋势。

图1-10　运行时间性能的比较

这张图揭示了这5种方法的运行时间性能的更多细节。

● 我们可以看到，与另外两种方法相比，mutable_two()、double_two()和largest_two()的性能更为相似。它们几乎可以看成同一个“家族”，它们都位于相当容易预测的直线轨迹上。

● tournament_two()的效率最低，并且它的行为与其他方法存在显著的不同。由于图1-10中的数据点太少，尚不清楚它会形成极低效率的缓慢上升曲线还是会最终形成一条直线。

● sorting_two()要优于tournament_two()，但比其他3种方法要慢。它的轨迹是一条向上弯曲的曲线还是一条直线？

为了理解这几条线为什么会显示为图1-10中的形状，我们需要学习两个基本概念，它们能够解释一个算法的内在复杂度。

1.7　时间复杂度和空间复杂度

对基本操作（例如加法、变量赋值或控制逻辑）进行计数可能非常困难，因为不同编程语言之间存在一些区别，再加上在Java和Python这样的语言中，算法是由解释器所执行的。但是，如果我们可以对一个算法所执行的基本操作进行计数，就可以看到操作总数在问题实例的规模的基础上各不相同。时间复杂度的目标就是用一个函数C(N)对算法所执行的基本操作进行计数，其中N表示问题实例的规模。

假设在CPU执行操作的基础上，每个基本操作需要固定数量的时间t，我可以把执行算法所需要的时间建模为T(N)= t × C(N)。程序清单1-7证实了程序的结构是极为关键的。对于函数f0()、f1()、f2()和f3()，我们可以根据输入规模N，准确地计算出每个函数执行ct = ct + 1这个操作所需要的时间。表1-6展示了一些不同N值的不同函数的操作计数结果。

程序清单1-7　具有不同性能的4个不同函数

def f0(N):    def f1(N):           def f2(N):           def f3(N):
  ct = 0        ct = 0               ct = 0               ct = 0
  ct = ct + 1   for i in range(N):   for i in range(N):   for i in range(N):
  ct = ct + 1     ct = ct + 1          ct = ct + 1          for j in range(N):
  return ct     return ct              ct = ct + 1            ct = ct + 1
                                       ct = ct + 1        return ct
                                       ct = ct + 1
                                       ct = ct + 1
                                       ct = ct + 1
                                       ct = ct + 1
                                     return ct

f0()的计数总是相同的，与N的大小无关。f2()的计数总是f1()的7倍，它和f1()都随着N的倍增而倍增。与f1()和f2()的倍增行为形成鲜明对照的是，f3()的计数增长要快得多。如表1-6所示，当N倍增时，f3()的计数呈4倍的增长。在这里，与f3()相比，f1()和f2()彼此更加相似。在第2章中，当我们对算法的性能进行评估时，将会解释for循环和嵌套的for循环的重要性。

表1-6　4个不同函数的操作计数

对算法进行评估时，我们还需要考虑空间复杂度，也就是考虑算法处理规模为N的问题实例所需要的额外的存储空间。内存是表示存储在文件系统或计算机RAM中的数据的通用术语。程序清单1-5中，largest_two()在这几个算法中具有最少的内存需求：它使用了2个变量my_max和second，再加上一个迭代变量idx。不管问题实例的规模如何变化，它所需要的额外的存储空间都不会改变。这意味着它的空间复杂度与问题实例的规模无关，或者说空间复杂度为常数级。mutable_two()具有相似的行为。而tournament_two()分配了3个数组：winner、loser和prior。它们的长度都是N − 1。当N增长时，额外的存储空间^[3]的大小与问题实例的规模直接成正比。与largest_two()相比，创建锦标赛结构会拖慢tournament_two()的速度。double_two()和sorting_two()都会创建输入A的一份拷贝，这意味着它们的空间复杂度与tournament_two()（而不是largest_two()）更为相似。在本书中，我将会评估每种算法的时间复杂度和空间复杂度。

观察表1-5，可以发现largest_two的计时结果的每一行大致比前一行扩大一倍。根据观察，double_two()和mutable_two()的结果与之相似。这意味着它们的计时与问题实例的规模直接成正比，每向下一行大约扩大一倍。这是一个重要的现象，因为前述这些函数的效率要高于sorting_two()，后者在图1-10中呈现为一条效率更低的轨迹。tournament_two()仍然是效率最低的，其运行时间性能比largest_two()的还要糟糕，其运行时间相比问题实例的规模的增长速度使我不忍心在规模很大的问题实例上执行它。

作为计算机科学家，我不能简单地宣称largest_two()和mutable_two()的性能曲线“看上去相同”。我需要依靠正式的理论和概念证实这个思路。在第2章中，我将介绍对算法的行为进行适当的分析所需要的数学工具。

1.8　总结

本章对算法这个丰富多彩的领域进行了简单的介绍。我展示了如何根据问题实例的规模N对算法所执行的基本操作进行计数，从而对它的运行时间性能进行建模。我们还可以根据经验评估一种算法实现的运行时间性能。不管采用什么方法，我们可以确定当问题实例的规模N倍增时算法运行时间的增长级数。

我在本章中介绍了一些关键的概念，包括：

● 根据算法在规模为N的问题实例上所执行的基本操作的数量评估它的时间复杂度；

● 根据算法在执行规模为N的问题实例时所需要的内存大小评估它的空间复杂度。

在第2章中，我将介绍渐进性分析的数学工具，它们可以解释对算法进行适当的分析所需要的技巧。

1.9　挑战练习

1．回文单词检测器：回文单词就是顺读和倒读结果相同的单词，例如madam。设计一种算法，检测一个包含N个字符的单词是否为回文单词。根据实验证实它的性能要优于程序清单1-8中的两个其他算法。

程序清单1-8　两种其他回文算法^[4]

def is_palindrome1(w):
  """创建w的一个反向列表，并证实它与w是否相等"""
  return w[::-1] == w

def is_palindrome2(w):
  """如果最外层的两个字符相同就去除它们，如果不同就返回False"""
  while len(w) > 1:
    if w[0] != w[-1]:     # 如果不同，就返回False
      return False
    w = w[1:-1]           # 去除两端的各一个字符；重复进行操作

  return True             # 肯定是回文

当读者所设计的算法可以解决问题时，对它进行修改，使它可以检测带空格符、标点符号和混合大小写的回文。例如，下面的字符串应该被认为是回文字符串：" A man, a plan, a canal. Panama! "。

2．中位值查找（线性时间）：有一种精妙的算法可以高效地查找一个任意列表的中位值（简单起见，假设列表的长度为奇数）。观察程序清单1-9的代码并使用本章介绍的RecordedItem类，对小于操作的调用次数进行统计。当这个算法实现对任意列表进行处理时，会对它进行重新排列。

程序清单1-9　一种计算无序列表中位值的算法（线性时间）

def partition(A, lo, hi, idx):
  """使用A[idx]作为值进行划分"""
  if lo == hi: return lo

  A[idx],A[lo] = A[lo],A[idx]         # 交换位置
  i = lo
  j = hi + 1
  while True:
    while True:
      i += 1
      if i == hi: break
      if A[lo] < A[i]: break

    while True:
      j -= 1
      if j == lo: break
      if A[j] < A[lo]: break

    if i >= j: break
    A[i],A[j] = A[j],A[i]

  A[lo],A[j] = A[j],A[lo]
  return j

def linear_median(A):
  """返回任意列表的中位值的高效实现，假设A具有奇数数量的值。注意，这个算法会重新排列A中的值"""
  lo = 0
  hi = len(A) - 1
  mid = hi // 2
  while lo < hi:
    idx = random.randint(lo, hi)      # 随机地选择合法的索引
    j = partition(A, lo, hi, idx)

    if j == mid:
      return A[j]
    if j < mid:
      lo = j+1
    else:
      hi = j-1
  return A[lo]

实现使用一种不同的算法（需要额外的存储空间），根据输入创建一个有序的列表并选择中位值。生成一个运行时间性能表，把它的运行时间性能与linear_median()进行比较。

3．计数排序：如果我们知道一个任意的列表A只包含0～M的非负整数，则下面这个算法可以只使用大小为M的额外的存储空间就可以对A进行正确的排序。

程序清单1-10具有嵌套的循环，在一个while循环的内部有一个for循环。但是，我们可以证明A[pos+idx] = v只执行了N次。

程序清单1-10　一种线性时间的计数排序算法

def counting_sort(A, M):
  counts = [0] * M
  for v in A:
    counts[v] += 1

  pos = 0
  v = 0
  while pos < len(A):
    for idx in range(counts[v]):
      A[pos+idx] = v
    pos += counts[v]
    v += 1

进行性能分析，证明对0～M的N个整数进行排序所需要的时间随着N的倍增而倍增。

我们可以利用Python，使用sublist[left:right] = [2,3,4]替换一个子列表来消除内层的for循环，从而提高这个算法的性能。进行这个修改后，根据经验可知，虽然修改后的算法所需要的时间也是随着N的倍增而倍增的，但它大约可以提升30%的速度。

4．修改锦标赛算法，使它适用于奇数数量的值。

5．程序清单1-11中的代码能否正确地查找A中的两个最大值？

程序清单1-11　在一个无序列表中计算两个最大值的另一种算法

def two_largest_attempt(A):
  m1 = max(A[:len(A)//2])
  m2 = max(A[len(A)//2:])
  if m1 < m2:
    return (m2, m1)
  return (m1, m2)

解释这种算法在什么情况下可以成功？在什么情况下将会失败？

[1]　包装类RecordedItem重写了__lt__()小于操作符，对它（或__gt__()大于操作符）的调用次数进行统计。

[2]　如果一场比赛的双方的值相等，只有一支队伍能够进入下一轮。

[3]　也就是除了表示问题实例的数据之外所需要的存储空间，任何算法的空间复杂度都不会把前者计算在内。

[4]　原文明显是复制粘贴程序清单1-7之误，译文根据实际内容补充。——译者注

读者服务：

微信扫码关注【异步社区】微信公众号，回复“e59244”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。