Python算法教程_中文版（高清PDF下载）

内容提要

Python 是一种面向对象、解释型计算机程序设计语言，其应用领域非常广泛，包括数据分析、自然语言处理、机器学习、科学计算以及推荐系统构建等。

本书用 Python 语言来讲解算法的分析和设计。本书主要关注经典的算法，但同时会为读者理解基本算法问题和解决问题打下很好的基础。全书共 11 章。分别介绍了树、图、计数问题、归纳递归、遍历、分解合并、贪心算法、复杂依赖、Dijkstra 算法、匹配切割问题以及因难问题及其稀释等内容。本书在每一章结束的时候均有练习题和参考资料，这为读者的自我检查以及进一步学习提供了较多的便利。在全书的最后，给出了练习题的提示，方便读者进行查漏补缺。

本书概念和知识点讲解清晰，语言简洁。本书适合对 Python 算法感兴趣的初中级用户阅读和自学，也适合高等院校的计算机系学生作为参考教材来阅读。

引言

让我们先来考虑一下下面这个问题∶我们想要访遍瑞典境内所有的城市、小镇和村庄，然后再返问出发地点。显然，这段旅程肯定要耗费掉不少时间（毕竟我们要访问 24 978个地方），因而我们希望能最小化该旅行路线。也就是说，我们既要能按计划逐个参观这些地方，又要尽可能地走出一条最短路线来。作为一个程序员，我们当然不屑于用手工方式来设计该路线，显然会更倾向于用写代码的方式来完成相关计划。然而，这似乎是一件不可能完成的任务。的确，想要写出一个针对少量城镇的简单程序并不难，但如果想要进一步用它来解决实际问题，相关的改进就会变得极其困难。这是为什么呢?

其实，早在 2004 年就已经有一个五人的研究团队发现了这个被称为瑞典之旅的问题，之后陆续有多个别的研究团队也都试图解决过这个问题，但是都失败了。该五人团队采用了一款带有智能优化技术的、能模拟交易技巧的软件，并将其运行在一组由 96 台机器（Xeon 2.6GHz）组成的工作站集群上。结果，该软件从 2003年3月一直运行到 2004年5 月。最终不得不在打印出该问题的最佳解决方案之前被中止运行。因为综合各方面的因素，他们估计程序所需要的总 CPU时间竟然长达 85年!

下面再来思考一个类似的问题∶我们想要在中国西部的喀什市到东海岸的宁波市之间找出一条最短路线*。目前，中国境内有 3 583 715千米长的公路和 77 834千米长的铁路，之间有着数以百万计的路口可【供我们考比，其中可供选择的路线千干万万，难以估算。这个间题侧平与前一个问题是密切相关的，都是希望通过 GPS 导航和在线地图服务找出最短路线的规划间题， 并且不能有太明显的滞后现象。也就是说，只要向您最爱的地图服务程序输入这两个城市，您就应该能在短时间内得到它们之间的最短路线。这又应该怎么做呢?

关于这些问题，读者将来都可以在本书中找到相关进一步的讨论。例如，第一个问题其实叫作旅行商问题（traveling salesman，或推销员问题（salesrep）），这将是本书第 11章所要涵盖的内容。而所谓的最短路径间题（shortest path），则是第 9 章中所要介绍的内容。但我们更希望读者能从中学会如何深入分析问题的困难所在，并且掌握那些已被承认的、高效的知名解决方案。更为重要的是，我们将在本书中传授一系列常用的算法处理技术，及一些与计算机运算相关的问题，以便帮助读者熟练掌握书中所介绍的技术和算法，以及所演示的针对困难问题而提出的最接近期望值的解决方案。在这一章中，我们将对本书的主要内容做简单介绍——我们可以期望什么，我们应该期望什么。另外，我们还会列举本书各章节所要介绍的具体内容，以便读者可以直接跳到自己想阅读的内容附近。

1.1 这是一本怎么样的书

简而言之，这是一本为 Python 程序员解决算法问题的书。正如书上所说，它的内容涵盖相关的面向对象模式和一些常见问题的处理方式——也就是相关的解决方案。对于一个算法设计者，我们需要的不是简单地实现或执行一些现有算法的能力。相反，我们期望能拿出一个新算法———个能解决一般性问题的、前人没有提过的全新解决方案。在本书中，我们要学习的就是此类解决方案的设计原则。

但这又不是一本传统意义上的算法书。毕竞，大部分这类题材的权威书第（例如 Knuth 那部经典著作，或是由 Cormen 等人合著的那本标准教科书"）都属于理论研究型的，显得有些过于严肃，尽管其中也不乏一些侧重于可读性的作品（例如 Kleinbeng 与 Tardos 合写的书就是其中之一）。当然，我们在这里并不是要取代这些优秀的作品，而只是希望能在此基础上做一些补充。我希望利用自己多年的算法教学经验，尽可能清楚地为读者诠释算法的工作方式，以及一些需要共同遵守的基本原则。对于一个程序员来说，这种程度的诠释可能就已经足够了，读者需要有更多的机会去理解为什么相关的算法是正确的、如何将这些算法运用到他们所面对的新问题中去。但这就需要去阅读一些更形而上的、百科全书式的教科书。我希望这本书能为读者打下一定的基础，这将有助于他们理解相关的定理以及其相应的证明。

除此之外，市面上还有另一种算法类书籍。它们通常以"（数据结构与）算法（blank 版）"为题，这里的 blank 通常为作者本人所使用的编程语言。有不少这样的书（而且似乎都是以 blank=Java 的情况为主），但其关注点多集中在与基本数据结构有关的东西上，以至于忽略了某些更为实质性的内容。如果说这是某一门数据结构基础课程的教科书，或许还可以理解，但对于 Python 程序员来说，学习单向或双向链表并不是一件能让所有人兴致勃勃的事情（尽管我们在下一章中还是会提到—些）。即便是哈希这样重要的技术，我们也可以通过 Python 中的字典类型免费得相应的哈希表，提全不需要再去考成重新实班它们。恰恰相反，我将注意力集中在申高级的一些算法。但这样一来，许多重要的概念在 Python 语言本身或标准库对相关算法（如查找、搜索、哈希等）的"黑盒"化实现中被淡化了。为此，我们在文中加入了一些特定的"黑盒子"专栏，以做补充。

当然，本书与那些"Java/C/C++/C#"算法流派还有一个显著的区别，即这里的 blank 为 Python。这使得本书更接近那些与语言无关的算法书（例如 KnuthP、Cormon 等人以及Kleinberg与Tardos的作品），这些书常常使用伪代码来说明问题。这实际上是一种侧重于可读性的伪编程语言，因而它不具备执行能力。而可读性正好是 Python 最显著的特点之一，因此它或多或少可以被视为是一种具有执行能力的伪代码。就算我们从没用过 Python，也能看懂绝大部分 Python 程序。总之，这本书中代码示例都是高度可读的——我们不需要成为 Python 方面专家，也能轻松读懂这些示例（尽管有时候还是需要读者去查阅一些与内置函数有关的资料）。当然，您也可以把这些示例当作伪代码来理解。综上所述…

1.1.1 本书将主要涉及以下内容

● 算法分析，主要侧重于渐近运行时间分析。

● 算法设计的基本原则。

● 如何用Python 描述那些常用的数据结构。

● 如何用 Python 实现那些知名算法。

1.1.2 本书还将简单或部分涉及以下内容

● Python 中直接可用的算法，它们通常是语言本身或其标准库的一部分。

● 纯思想性及形而上的内容（尽管本书会对它们做一些证明，并提供相关的证明示例）。

1.1.3 本书不会涉足以下领域

● 与数值计算或数学理论有关的算法（只有第 2 章中涉及了一些浮点运算）。

●并行算法与多核编程。正如大家所知，"用 Python 实现"只是整个拼图的一部分。我们所希望的是，读者能掌握其中的设计原则与理论基础，以便能设计出属于自己的算法与数据结构。

1.2 为什么要读这本书

当我们在工作中使用算法时，通常都是希望能更有效地解决问题、使程序运行得更快，并且让解决方案变得更为简短。但实际情况如何呢?我们获得所需要的效率、速度和简洁性了吗? 为什么人们在使用 Python 这种语言时依然要在乎这些事呢? 选择这种语言对于追求高速度的人来说是一个好的开端吗?为什么不选择C或 Java 这样的语言呢?

首先，可能是因为 Python 语言本身很讨人喜欢，以至于人们不想换别的语言，或者他们目前也没有更好的选择。但最为重要的可能还是第二点，即在这里，算法设计者们首先要担心的并不是常数级别的性能差异。 即便相关程序完成任务所需要的时间是另一程序的两倍， 甚至十倍，但这样的速度可能依然是够快的。况且，那个较慢的程序（或语言）中可能恰好有某些我们所需要的特性，如它可能有更好的可读性。而调整和优化程序在很多时候会非常费劲，其代价是不容小视的。然而，无论选择什么语言，我们都得考虑一下程序自身的弹性问题。也就是说，如果我们将程序的输入量翻倍， 会发生什么呢?程序运行时间会是之前的两倍? 四倍?还是更多? 或者即便增加那么一丁点的输入量也会导致程序运行时间的成倍增长?当您遇到的问题足够大的时候，这样的性能差异显然就不能再靠简单的语言选择或硬件选择来解决了。在面对一个"足够大"的问题（在某些情况下，当问题还没有特别大的时候，它就已经"足够大"了）时，我们能抑制运行时间增长的主要武器就只有——您猜对了———一份扎实的算法设计功底了。

下面让我们来做一个小小的实验，打开 Python 的交互解释器，并输入以下内容;

>>>count = 10**5>>>nums=[]
>>> for i in range(count):
nums.append(1)···1
>>>nums.reverse()

【下载地址】

链接：https://pan.baidu.com/s/173Qx1n_nuStNn3UrasZ62w

提取码：fyty