2.1 如何描述计算机算法

将计算机算法描述成一个可执行程序可以有多种选择，例如使用通用的编程语言表示，像Java、C、C++、Python或Fortran。诚然，许多教科书上的算法都是这么表示的。但是使用实际的编程语言来表示算法所带来的问题是你可能会在语言细节上越陷越深，而对算法本身的认识反而模糊不清。另一种表示算法的方式是“伪代码”，就像我们在《算法导论》中使用的一样，它听起来像是多种编程语言和英语的混合表示。如果你曾用一种实际的编程语言编写过程序，那么你就能很容易地搞清楚伪代码。但是如果你从来没有编写过程序，那么对你而言，伪代码可能是带些神秘感的。

10

本书中我所采取的描述算法的方式并不是将算法描述在硬件或者软件上，而是描述在“湿件”上，即类似耳朵间的灰质。我也假定你从来没有编写过一个计算机程序，所以我不会使用任何实际的编程语言或者是伪代码来表示算法。反之，我将用通用的文字来描述算法，尽可能地使用现实世界中的情境来模拟算法。为了表示发生的事（编程中我们称之为“控制流”），我将使用列表和嵌套列表方式表示。如果你想在一个实际的编程语言中实现算法，并能将我的描述转化为可执行代码，我将为此给你加分。

虽然我会尽可能地以一种通用的、非技术的方式描述算法，但是本书本身是关于计算机算法的，所以必定会涉及计算技术。例如，计算机程序包含 程序 （procedures，也称为实际编程语言中的函数或方法），它用来指定如何执行步骤。为了真正实现假定要执行的程序，我们 调用 它。当调用一个程序时，我们需要提供输入（通常一个程序至少包含一个输入，但是有些程序不需任何输入）。这些输入被称为 参数 ，位于程序名之后的括号内。例如，为了求一个数的平方根，可以定义一个程序为SQUARE-ROOT（ x ）；这里，程序的输入是参数 x 。任何被调用程序可能会产生输出，也可能不会产生输出，这取决于如何指定程序。如果程序产生输出，通常我们认为输出是返回给调用者的。计算术语中称作程序 返回 了一个值。

许多程序和算法都对数组进行操作。 数组 是将类型相同的数据聚集成一个实体。你可以把数组看作一个表格，给定表格中一个 条目 的 索引 ，我们就可以访问该索引所指数组中的 元素 。例如，以下是一个由美国前5位总统组成的表格。

例如，表中索引为4的元素是James Madison。我们并不将该表看作是5个独立的实体，而是将它们看作是由5个条目所组成的一个表。数组和表类似。数组中的索引是可从任意值开始的连续数字，但是我们通常将索引设为从1开始。 给定数组名和索引，我们用方括号将它们组合起来以表示一个特定的数组元素。例如，我们将数组 A 的第 i 个元素表示为 A [ i ]。

11

数组还有另外一个重要的特性：访问数组中的任意元素均会花费同样长的时间。一旦你指定数组中的一个索引 i ，那么计算机能像访问第一个元素那样，以同样时间迅速地获取第 i 个元素，即速度与 i 值无关。

让我们看看我们的第一个算法：在数组中查找一个特定的值。也就是说，给定一个数组，我们想知道数组中哪个条目或者哪些条目等于给定的值。为了观察在数组进行查找操作的过程，我们将数组看作是一个装满书的长长的书架，并且假定你想知道书架上哪个位置可以找到一本由Jonathan Swift写的书。现在，书架上的书可以以某种方式陈列，可以按作者名的字母顺序排序，也可以按书名的字母顺序排序，或者像图书馆中按图书的书号顺序陈列。这个书架也可以像我自家的书架一样，并没有按照任何特定的方式陈列着。

如果假定书架上的书并没有以某种特定顺序陈列，那么你如何查找到由Jonathan Swift写的书呢？这便是我要讲解的算法。我将从书架的最左侧开始查找，并查看这本书是否是Swift写的。如果它是Swift写的书，那么我便找到了这本书。如果它不是Swift写的书，那么我将继续向右查找，依次向右查看当前的书是否是Swift写的，一直到找到Swift写的书或者已经查找到了书架的最右侧，在查找到书架的最右侧这种情况下，我就可以断定书架上没有Jonathan Swift写的任何书。（在第3章中，我们将看到当书架上的书按某种顺序陈列时，我们是如何进行查找的。）

下面将该查找问题描述为一个计算问题。我们将书架上的书看作是以书为元素的数组。最左侧的书位于位置1处，该书右侧的书位于位置2处，以此类推，如果书架上有 n 本书，那么最右侧的书就位于位置 n 处。我们想要查找由Jonathan Swift所写的任意一本书在书架上所处的位置。

12

作为一个泛化的计算问题，即给定一个具有 n 个元素（每本书）的数组A（要查找装满书的整个书架），我们想要查找数组 A 中是否存在一个值 x （一本由Jonathan Swift所写的书）。如果存在，那么我们想要确定满足 A [ i ]= x （一本由Jonathan Swift所写的书在书架上的位置 i ）的索引 i 的值。同时，我们也需要一些方法来表明数组 A 中不存在 x （书架上不包含由Jonathan Swift所写的书）。我们并不假定 x 在数组中最多出现一次（可能你某些书有多本），因此如果数组 A 中存在 x ， x 可能会出现多次。我们想要从一个查找算法中得到的是数组中能够得到元素 x 的任意一个索引值。我们将假定该数组中索引从1开始，因此它的元素是从 A [1]到 A [ n ]。

如果查找由Jonathan Swift所写的书是从最左侧开始查找，依次向右检查当前书是否是由Jonathan Swift所写，该方法被称为 线性查找 。计算机中的线性查找等价于：从数组的开始端开始查找，依次检查每个数组元素（ A [1], A [2], A [3]… A [ n ]），若找到 x ，则记录下 x 所在的位置。

下面这个线性查找程序（LINEAR-SEARCH）以3个参数作为输入，各参数之间以逗号隔开（规范表示）。

除了参数 A 、 n 和 x 之外，LINEAR-SEARCH程序还使用一个称为 answer 的 变量 。这个程序在第1步将 answer 赋值为NOT-FOUND。第2步逐步检查 A [1]到 A [ n ]项并判断该项是否等于值 x 。当 A [ i ]等于 x 时，第2A步将 answer 赋值为当前的 i 值。如果数组中包含 x ，那么第3步会返回输出值，即最后一次出现 x 的索引位置。如果数组中不包含 x ，那么第2A步的等式始终不成立，那么最后返回的输出值是NOT-FOUND，即第1步中 answer 被赋予的值。

13

在继续讨论线性查找之前，需说明一个词，即如何指定重复操作，例如程序的第2步。这种对一个变量在一定范围内取各种值的操作在算法中非常常见。当我们执行重复操作时，我们称它为一个 循环 ，并且我们将每次循环操作称为循环的一次 迭代 。对于第2步的循环，我写道“For each index i ，going from 1 to n ，in order”（对每个索引值 i ，按顺序从1取到 n ）。取而代之，之后我将简写为“For i =1 to n ”，该语句与上一句表示相同的意思。请注意，当我以这种方式写循环时，我们必须给 循环变量 （这里指 i ）指定一个初始值（这里是1），并且在循环的每次迭代过程中，我们必须判断循环变量的值是否超界（这里界是 n ）。如果当前循环变量的值小于或等于这个界，那么我们就执行循环 主体 （这里指第2A步）。当执行完循环主体的一次迭代后，我们就 增加 循环变量的值——将循环变量的值自增1——再返回循环条件判断那步，此时将更新的循环变量和界进行比较，再次执行循环体，并增加循环变量的值，直到循环变量超界为止。之后执行操作转到紧接着循环体的那步（这里指第3步）。形为“For i =1 to n ”的循环执行 n 次迭代和 n +1次判断是否越界的操作（因为循环变量在第 n +1次测试比较时越界）。

希望你能很清楚地发现LINEAR-SEARCH程序总能返回一个正确的结果。然而，你可能也注意到，这个程序不够高效：即使它已经找到了一个令 A [ i ]= x 成立的索引 i ，它还会继续在数组中查找 x 。通常情况下，一旦你在书架上找到了你要找的书，你就不会再继续再找那本书了。因此，我们可以设计出另外一个线性查找程序（BETTER-LINEAR-SEARCH），使得一旦在数组中找到 x ，它便会停止查找。我们假定当我们说返回一个值时，程序会立即将该值返回给起控制作用的调用者。

14

信不信由你，我们能设计出更高效的线性查找算法。观察一下，BET-TER-LINEAR-SEARCH程序每进行第1步的循环时，会做出两个测试：一个测试是在第1步，用来测试 i ≤ n 是否成立（如果成立，执行循环的又一次迭代）；另一个测试是第1A步的“是否相等”的判断。类似在书架上查找书这个例子，这两个测试相当于你必须对每本书做两个判断操作：你现在查找到书架的末端了吗？如果没有，下本书是不是Jonathan Swift写的呢？当然，如果你查找时越过了书架的末端，也不会造成巨大的损失（除非在你查找过程中，你的脸离书太近，以至于当你到达在书架的末端时，你的脸会撞到书架末端的墙上），但是在计算机程序中，当你试图访问越过数组末尾的元素时，结果通常是糟糕的。你的程序可能会崩溃，也可能会损坏数据。

如果你不确定书架上是否包含Jonathan Swift所写的书，为了避免访问越界，你须对每本书执行一次检查操作。要是你确定书架上包含Jonathan Swift的书又如何呢？那么你就可以放心地查找它了，而且你从不必担心会检查到超过书架末端书的位置。你仅仅需要依次检查当前这本书是否是Swift写的即可。

但是有可能你将Jonathan Swift所写的书都借出去了或者也有可能你以为你的书架上有Jonathan Swift写的书，但是实际上并没有，所以你并不能确定你的书架上是否包含Jonathan Swift写的书。这时你可以将最右边的书替换成一个跟书大小一样的空盒子且在它的窄边（即书脊位置）写上“ Gulliver ’ s Travels by Jonathan Swift”。那么，当你沿着书架从左向右查找书时，你仅仅需检查当前这本书是否是Jonathan Swift写的。你不需要再检查你是否越过了书架的最右侧，因为你 知道 你一定会找到Jonathan Swift所写的书。唯一的问题是你是否真的找到了Swift所写的书，还是你找到了那个被标记为Jonathan Swift所写的空盒子？如果你找到了空盒子，那么你并不是真的有一本由Swift所写的书。那么，你需要做的事情很简单，你仅仅需在查找的最后再添加一次对最右边那本书的检查操作，而不必添加对书架上的每本书均再检查一遍的操作。

这里还有一个细节必须注意：要是书架上仅有的一本由Jonathan Swift所写的书就是放在书架最右端呢？如果你将这本书替换成了空盒子，那么你的查找会终止于空盒子，你可能得出你没有Jonathan Swift所写的书的结论。所以你必须针对这种可能性再进行一次检查操作，但这也仅仅是对一本书进行一次检查，而不是对书架上的每本书均进行一次检查。

15

转化为计算机算法，即是先将最后一个位置的元素 A [ n ]的内容保存到一个变量中，再将要查找的值 x 赋值给 A [ n ]。一旦找到了 x ，就可以验证我们是否真正找到了 x 。其中， x 被称作 信号量 ，你也可以将它看成空盒子。

第3步是一个循环，但是循环变量实际取的值并非循环变量可取范围内的所有值。反之，只有当循环条件成立时，循环迭代才会执行；这里，循环条件是 A [ i ]≠ x 。执行这个循环相当于首先执行判断（这里指代 A [ i ]≠ x ），之后如果条件成立，那么才能执行循环体的内容（这里，指第3A步，即 i 值自增1）。然后返回到再次执行循环条件判断部分，即第3步，如果条件成立，则执行循环体。循环迭代中，首先测试条件是否成立，然后执行循环体，直到条件不成立时结束循环。然后执行紧接循环体的步骤（这里指第4步）。

SENTINEL-LINEAR-SEARCH程序相对于前两个查找程序而言略显复杂。因为它首先在第1步中将 x 赋值给 A [ n ]，这样我们确保了当执行到 i = n 时，必有 A [ i ]等于 x 成立（第3步）。一旦 A [ i ]= x 成立，那么第3步的循环必定可以结束，且随后索引 i 的值不会再改变。在继续执行其他操作前，第4步又将 A [ n ]的原始初值重新赋给了 A [ n ]。（正如妈妈教导我的，玩耍完后，要将所有物品物归原位。）随后我们需要判定是否在数组中真的找到了 x 。由于第1步， A [ n ]被赋为 x ，可以得知如果我们发现 A [ i ]= x 且 i ＜ n ，那么我们确实真的找到了 x 并且可返回索引 i 。如果我们发现 A [ n ]中存放的是 x 呢？那就意味着我们在 A [ n ]之前的元素中并没有找到 x ，所以我们需要判定 A [ n ]是否真的等于 x 。如果 A [ n ]的真值确实等于 x ，那么我们要返回索引 n ，此时 n 也等于当前的 i ，故返回当前的 i 即可。若 A [ n ]的真值不是 x ，那么返回NOT-FOUND。第5步进行了相关的判断操作并且如果数组中存在 x ，那么第5步会返回正确的索引值。如果数组中包含 x 仅仅是因为在第1步中将 x 赋值给 A [ n ]，那么就会执行第6步，即返回NOT-FOUND。尽管SENTINEL-LINEAR-SEARCH在循环结束后必须执行两个测试，但是它在每次循环迭代中仅仅会执行一个条件判别，因此相对于LINEAR-SEARCH和BETTER-LINEAR-SEARCH，SENTINEL-LIN-EAR-SEARCH的效率更高。 SU2S+KNlo+XsaD1rT/DLajtCZfk42whLorBctjMhKl+BOjrkYqjAt8tQB9geNFno

16