第1章 简介

本书的目标是研究一大类重要且有用的算法，即适合计算机实现的求解问题的方法。为实现该目标，本书做了以下工作：

• 介绍许多不同领域的应用，重点关注有趣且重要的基础算法；
• 花费足够的时间来理解每个算法的本质和展示相关细节；
• 使用C语言来描述算法，同时提供有用的实现；
• 关注算法的性能特征；

算法的性能分析很重要。
理解算法的性能特征可能同时需要实验和数学分析。

理解本书里展示的程序的方法是：

• 实现这些程序；
• 测试这些程序；
• 检查这些程序的变种；
• 讨论这些程序对小规模实例的操作；
• 在跟实际中遇到的类似的较大规模的实例上运行这些程序；

本书开发问题解的一般方法的步骤是：

• 先得到问题的一个简单的解；
• 后寻求理解该算法的性能特征；
• 重复若干次上述步骤后，得到求解该问题的一个有效率且有用的算法；

为什么要关注算法的性能特征？

• 帮助开发优化版本的算法；
• 比较执行同一任务的不同算法；
• 预测或者确保算法在大规模问题的性能；

第1.1节 算法

当我们编写一个计算机程序时，我们通常是正在实现一个先前设计好的用于解决某个问题的方法。这种方法通常跟使用的计算机无关，可能同等适用于许多计算机和计算机语言。为了学习问题是如何被解决的，我们必须要研究的正是这种方法，而不是计算机程序。

在计算机科学里，使用算法来描述一种适合用计算机程序来实现的问题解决方法。算法是计算机科学的基础：算法是许多计算机领域的核心研究对象。大部分算法都涉及跟计算相关的数据的组织方法。通过这种方式创建的对象被叫做数据结构。数据结构也是计算机科学的核心研究对象。因此，算法和数据结构密不可分。

本书的观点是数据结构是算法的副产品或者产品。因此，为了理解算法，必须要去研究数据结构。

简单的算法可以产生复杂的数据结构，同理，复杂的算法也可以使用简单的数据结构。在本书中，我们将研究许多数据结构的性质。

当我们使用计算来帮助我们解决一个问题时，我们通常会面临许多可能的不同的方法。对于小规模问题来说，只要我们有一种可以正确解决问题的方法就行，几乎跟使用哪一种方法无关。对于大规模问题来说，我们被激发去设计尽可能有效率地使用时间或者空间的方法。

我们学习算法设计的主要原因是这门学科给了我们一种获得巨大节省的潜力，甚至有可能去做一些原本不可能实现的任务。在一个需要处理上千万对象(数量级为)的应用里，使用一个设计良好的算法来使程序运行快上千万倍(数量级为)的事情很常见。比如，我们将在第1.2节里看到的一个这样的例子，在全书中看到许多其他的场景。作为对比，投资额外的钱和时间去够买和安装一台新的计算机给一个程序带来的速度提升可能只有或者。不管应用领域是什么，仔细的算法设计是求解大规模问题的过程中的非常重要的部分。

当要开发一个大型或者复杂程序时，必须花费大量努力去理解和定义要解决的问题、管理问题的复杂度、将该问题分解成更小的容易实现的子任务。
一般来说，许多算法分解之后的实现是平凡的。但是，在大部分情况里，总有一些算法的选择很关键，因为系统的大部分资源将花费在运行这些算法。我们将在本书中重点讲述这类算法，将研究各种各样的、对求解在许多应用领域里的大型问题有用的基础算法。

虽然在计算机中共享程序是越来越普遍，我们也期望在本书中尽可能多地共享使用算法，但是我们可能还是不得不实现一小部分算法。实现简单版本的基础算法可以帮助我们更好地理解它，从而更有效地使用它的高级版本。更重要的是，会多次出现重新实现基础算法的机会。
主要原因有两个：

• 我们经常会面临完全新的计算环境(软件或者硬件)，该计算环境有着之前旧的实现可能不会完全利用的新特征。换句话说就是，我们经常根据问题来裁剪实现基础算法，使得我们的解具有更好的可移植性和存在更长的时间，而不是依赖系统函数。
• 在许多计算上的共享软件机制通常并没有强大到允许我们裁剪标准程序使其对特定任务更有效率地执行，所以做一个新的实现更容易。

计算机程序经常被过度优化。可能并不值得花费努力去保证一个特定算法的实现是可能最有效率的，除非该算法被使用许多次或者被用于一个大型任务。除此之外，一个仔细的、相对简单的实现就够了：我们自信该该实现能工作，且最差情形的运行时间可能比最好情形慢上5到10倍，这意味着最差情形可能要多运行额外的若干秒时间。作为比较，在最开始就选择合适的算法会产生100倍或者1000甚至更多的差别，换算成运行时间就是分钟、小时甚至更长。在这本书里，我们重点关注最好算法的最简单合理的实现。

针对某个特定任务去选择最好的算法是一个复杂的过程，可能包含高级的数学分析。在计算机科学中，算法分析就是研究这样过程的分支。我们要研究的许多算法已通过分析表明性能良好的，其他算法可通过经验就可简单地知道其运行良好。

虽然我们的主要目标是学习重要任务的合理算法，但是我们也会关注这些方法的相对性能。如果我们不了解一个算法使用了哪些资源，则我们就不应该使用该算法。我们要努力去了解我们的算法是如何按照预期运行的。

第1.2节 连通性问题

假设给定一个整数对序列，其中每个整数都表示某种类型的对象。
整数对p-q表示整数p跟整数q之间是连通的。
假设连通关系具有传递性：如果整数p和整数q是连通的，整数q和整数r是连通的，则整数p和整数r是连通的。
我们的目标是编写一个程序来从集合中过滤额外的整数对：只有该程序截止目前所看到的整数对并不能推导出整数p和q是连通的，该程序才会输出整数对p-q。如果之前的整数对确实可推导出整数p和整数q是连通的，则该程序就忽略整数对p-q，然后继续处理下一个整数对。

分析：
我们的问题是要设计一个能判断新的整数对是否连通的程序，其中该程序能记忆足够多的有关其已看到的整数对的信息。

连通性问题的一个难点：如何安排节点和连接来快速判断在一个大型网络里任意给定的两个节点之间是否是连通的？

连通性问题有许多重要的应用，这里简要地考虑3个实例来表明连通性问题的本质。

例1 连接计算机
假设每个整数表示在一个大型网路中的一个计算机，每个整数对表示两个计算机之间的连接。
则我们的问题可用来判断：为了p和q之间能够通信，是否要直接新增一条p和q之间的连接，或者是否可以利用现有的连接建立一条p和q之间的通信链路。
在这类应用中，我们可能需要处理的节点数有千万个(数量级为)，连接数为百亿个(数量级)，或者更多。如果没有一个有效率的算法，则该应用是不可能有解的。

例2 连接电路
假设每个整数表示一个电路网路里的一个节点，每个整数对表示连接两个节点的电线。
在这里，如果可能的话，可使用我们的程序来找到一种方式来连接所有的节点，同时不增加额外的连接。
并不能保证在列表中的边足以连接所有的点。
后面将看到：判断一个列表里的边是否足以连接所有的点将成为我们的程序的一个主要应用。

例3 变量名等价
在某种编程环境中，经过一系列的变量声明后，如何来判断给定的两个变量名是不是等价的？
变量名等价应用是一个很早的应用，激发了我们将要考虑的若干个算法。
变量名等价应用将我们的问题直接和一个简单的抽象关联起来，该简单的抽象为我们提供了一种可以使得我们的算法对一大类应用都适用的方式。

变量名等价应用要求我们给每个不同的变量名关联一个整数，电路连接应用里要求为每个节点关联一个整数，计算机连接应用里要求为每个计算机关联一个整数。我们将在第10章到第16章里考虑一系列的、以有效率的方式提供这类关联的算法。因此，在这一章，为了不失一般性，我们假设总共有N个整数，从0到N-1。

我们寻求的程序应该是一个做具体且定义良好的任务的程序。同时，我们还有许多其他相关的问题要解决。

在开发一个算法时要面对的首要任务之一就是确保我们已用合理的方式描述了问题。我们对一个算法要求的太多，可能期望需要完成任务所需的时间和空间就越多。由于这种关系是不可能先验地知道的，所以一旦发现某个问题很难解决或者解决起来代价很高时，我们就修改问题的描述。一旦发现算法提供的信息要比原始问题描述要求的信息更有用时，我们就修改问题的描述。比如，我们的连通性问题描述仅要求我们的程序能判断任意给定的整数对p-q是不是连通的，而没要求我们的程序能打印任何一种或者所有使得整数p与整数q连通的方式。添加这样一种描述会使得问题更难，会导致一个不同家族的算法，这些算法我们会在第5章简要介绍和第7部分详细论述。

上一段里添加的描述对我们比原始描述要求更多的信息，我们也可以添加描述使得问题比原始描述要求更少的信息。比如，我们可能想简单地解决问题：M个连接是否足以将N个对象都连接起来？这个问题表明：为了开发出有效率的算法，我们通常需要对我们正在处理的抽象对象做高级的推理。在这里，来自图论的一个基本的结果意味着所有N个对象都连通当且仅当通过连通算法输出的整数对的个数为N-1。换句话说，一个连通算法永远都不会输出超过N-1个整数对，因为一旦连通算法已经输出了N-1个整数对，则之后连通算法遇到的任何一个整数对将是连通的。因此，我们可以得到一个回答yes-no的程序，该程序是通过修改解决连通性问题的程序为一个递增计数器的程序得到的：

• 不输出每个之前不连通的整数对；
• 如果计数器的值不为N-1，输出no；当计数器值为N-1时，输出yes。

这个问题只是我们可能想要解决的有关连通性的许多问题中的一个。
输入的每个整数对的集合是一个图，输出的每个整数对的集合是该图的生成树，该生成树连接了所有对象。我们将在第7部分考虑图、生成树及相关的算法。

为了使得我们为连通性问题开发的算法适用更多的类似问题，尝试去确认我们将要执行的基本操作是有价值的。每次得到一个新的整数对，首先要判断给整数对是否表示一个新的连接，如果是，然后将该新连接信息整合到已有的对象连接信息里，以便程序能对未来看到的连接进行检查。先用输入的整数值表示在抽象集合里的元素，然后设计算法和数据结构，我们将这两步封装为抽象操作：

• find：查找集合中是否包含一个给定的数据项；
• union：用数据项的并集替换包含两个给定数据项的集合；

用这两个抽象操作来组织我们的算法似乎并不妨碍对连通性问题的求解。
这两个抽象操作可能对求解其他问题有帮助。
通常，在计算机科学和算法设计中，开发功能更强大的抽象层是一个必需的过程。在本书中会无数次遇到这种情形。在本章里，我们非正式地使用抽象思维来指导我们设计求解连通性问题的程序，在第4章里，我们将看到如何使用C代码来封装抽象操作。

使用find和union两个抽象操作可以轻松地求解连通性问题。
从输入中读取一个新的整数对p-q后，我们对该整数对的每个成员执行find操作。如果该整数对的所有成员在同一个集合里，我们将跳过该整数对开始处理下一个整数对；否则，我们做一次union操作，并输出该整数对。这里的集合表示的是连通组件：该集合的元素是对象；任何两个对象都是连通的。这种方法将连通性问题算法解的开发简化为定义一个数据结构来表示连通组件的集合以及开发有效率地使用该数据结构的find与union算法。

有许多可行的方式来表示和处理抽象集合，我们会在第4章中考虑详细的细节。在本章里，我们的关注点是寻找一种能支持有效率的find和union操作的表示。

第1.3节 Union-Find算法

开发一个求解给定问题的有效的算法的第一步是实现求解该问题的一个简单的算法。如果我们要解决的是若干个容易的特定问题实例，则该简单实现可能就能完成这个任务。如果需要更高级的算法，则该简单实现可以为我们提供一个对小规模情形的正确性检查和评估性能特征的基准。虽然我们经常关心性能，但是我们对求解问题的第一个程序的主要关心是保证该程序是这个问题的正确的解。

容易想到的第一个办法是以某种形式保存所有的输入整数对，然后编写一个遍历这些整数对的函数来尝试发现下一个输入对是否连通。
我们使用的是另一种办法。首先，在实际应用中，整数对的个数可能足够大，以助于不能将它们全保存在内存里。其次，即使我们把输入对全保存下来了，也没有简单的方法能从所有连通的集合快速判断出两个对象是否连通。虽然我们考虑的是在第5章里采用的办法，但是我们在本章里考虑的办法更简单，因为这些办法求解的是难度更小的问题，且更有效率，因为这些办法不要求保存所有的整数对。这些办法都使用一个整数数组来持有实现union和find所必需的信息，其中一个整数对应一个对象。

数组是我们将在第3.2节讨论的基础的数据结构。在这里，我们使用数组的最简单形式：比如，我们期望使用100个整数，我们就声明a[100]；我们使用a[i]来引用第i个整数，其中0<=i<100。

程序1.1是求解连通问题的一个简单实现，名叫quick-find算法。该算法的基础是一个整数数组，该数据有这样的性质：p和q连通当且仅当数组的第p个元素和第q个元素相等。我们将该数组第i个元素初始化为i，其中0<=i<N。为了实现对p和q的union操作，我们遍历整个数组，修改所有值等于p的数组元素的值为q。

图1.3展示了图1.1中的实例的union操作的变化情况。一方面，为了实现find操作，我们仅需测试下标索引的数组元素的相等性即可。另一方面，对每个输入对，union操作都需要遍历整个数组。

性质1.1
对于有N个对象连通性问题，如果需要M次union操作，则quick-find算法至少要执行MN条指令。

由于在现代计算机上每秒钟可以执行上亿()条或者上十亿()条指令，所以如果M和N比较小时，则开销是可以忽略的。但是我们可能会在一个现代应用里遇到有上千万个对象和上百亿个输入对。一个不可逃避的结论是使用quick-find算法来求解这样的问题是不可行的。我们将在第2章里考虑精确量化这个结论。

图1.4是图1.3的一个图形化表示。我们将某个对象看做是它们所属的集合的代表，其他对象都指向的其在集合中的该代表。很快就会知道转移到数组的这种图形化表示的原因。观察到：用这种表示展示的对象之间的连接不一定跟输入对之间的连接一样。这种表示是算法选择用来记忆的信息，该信息能知道将来的输入对之间是否连通。