我的第一本算法书

1

算法与程序的区别

算法就是计算或者解决问题的步骤。我们可以把它想象成食谱。要想做出特定的料理，就要遵循食谱上的步骤；同理，要想用计算机解决特定的问题，就要遵循算法。这里所说的特定问题多种多样，比如“将随意排列的数字按从小到大的顺序重新排列”“寻找出发点到目的地的最短路径”，等等。

食谱和算法之间最大的区别就在于算法是严密的。食谱上经常会有描述得比较模糊的部分，而算法的步骤都是用数学方式来描述的，所以十分明确。

算法和程序有些相似，区别在于程序是以计算机能够理解的编程语言编写而成的，可以在计算机上运行，而算法是以人类能够理解的方式描述的，用于编写程序之前。不过，在这个过程中到哪里为止是算法、从哪里开始是程序，并没有明确的界限。

就算使用同一个算法，编程语言不同，写出来的程序也不同；即便使用相同的编程语言，写程序的人不同，那么写出来的程序也是不同的。

排列整数的算法：排序

▶ 查找最小的数字并交换：选择排序

来看一个具体的算法示例吧。这是一个以随意排列的整数为输入，把它们按从小到大的顺序重新排列的问题。这类排序问题我们将在第 2 章详细讲解。

只解决这一个问题很简单，但是算法是可以应对任意输入的计算步骤，所以必须采用通用的描述。虽然在这个示例中输入的整数个数

为 8，然而不管

多大，算法都必须将问题解决。

那么，你首先想到的方法，是不是先从输入的数字中找出最小的数字，再将它和最左边的数字交换位置呢？在这个示例中就是找到最小数字 1，然后将它和最左边的 7 交换位置。

这之后 1 的位置便固定下来，不再移动。接下来，在剩下的数字里继续寻找最小数，再将它和左边第 2 个数字交换位置。于是，4 和 13 也交换了位置。

我们将这样的一次交换称为“1 轮”。到了第

轮的时候，就把剩下的数字中最小的一个，与左边开始第

个数字进行交换。于是在结束第

轮后，从左数的

个数字便都按从小到大的顺序排列了。只要将这个步骤重复

次，那么所有的数字都将按从小到大的顺序排列。

这便是我们将在 2-3 节中介绍的选择排序。不管输入的数字是什么、

有多大，都可以用这个算法解决问题。

▶ 用计算机能理解的方式构思解法：算法的设计

计算机擅长高速执行一些基本命令，但无法执行复杂的命令。此处的“基本命令”指的是“做加法”或者“在指定的内存地址上保存数据”等。

计算机是以这些基本命令的组合为基础运行的，面对复杂的操作，也是通过搭配组合这些基本命令来应对的。上文中提到的“对

个数字进行排序”对计算机来说就是复杂的操作。如何设计算法来解决这个排序问题，也就等同于构思如何搭配组合计算机可以执行的那些基本命令来实现这个操作。

2

如何选择算法

能解决排序问题的算法不止选择排序这一个。那么，当有多个算法都可以解决同一个问题时，我们该如何选择呢？在算法的评判上，考量的标准也各有不同。

比如，简单的算法对人来说易于理解，也容易被写成程序，而在运行过程中不需要耗费太多空间资源的算法，就十分适用于内存小的计算机。

不过，一般来说我们最为重视的是算法的运行时间，即从输入数据到输出结果这个过程所花费的时间。

对 50 个数字排序所花的时间竟然比宇宙的历史还要长吗

▶ 使用全排列算法进行排序

为了让大家体会一下低效率算法的效果，这里来看看下面这个排序算法。

① 生成一个由

个数字构成的数列（不和前面生成的数列重复） ② 如果①中生成的数列按从小到大的顺序排列就将其输出，否则回到步骤①

我们就把这个算法称为“全排列算法”吧。全排列算法列出了所有的排列方法，所以不管输入如何，都可以得到正确的结果。

那么，需要等多久才能出结果呢？若运气好，很快就能出现正确排列的话，结果也就立马出来了。然而，实际情况往往并不如我们所愿。最差的情况，也就是直到最后才出现正确排列的情况下，计算机就不得不确认所有可能的排列了。

个数字有

种不同的排列方法

。现在，我们来看看

时是怎样一种情况吧。

公式①中，50! 即为数字 1 到数字 50 的乘积。为了便于计算，我们通过公式②③将结果近似转换为 10 的

次方的形式。公式②右边部分去掉了 10 以下的数字，因此小于 50!。公式③左右都是 40 个数字的乘积，但左边数字都大于 10，因此大于右边的

。接下来我们就用

近似代表 50 个数字的所有排列情况来进行计算。

假设 1 台高性能计算机 1 秒能检查 1 万亿（

）个数列，那么检查

个数列将花费的时间为

秒。1 年为 31 536 000 秒，不到

秒。因此，

秒＞

年。

从大爆炸开始宇宙已经经历了约 137 亿年，即便如此也少于

年。也就是说，仅仅是对 50 个数字进行排序，若使用全排列算法，就算花费宇宙年龄的

倍时间也得不出答案。

▶ 使用选择排序算法进行排序

那么，使用前文提到的选择排序算法，情况又将如何呢？

首先，为了在第 1 轮找到最小的数字，需要从左往右确认数列中的数字，只要查询

个数字即可。在接下来的第 2 轮中，需要从

个数字中寻找最小值，所以需要查询

个数字。将这个步骤进行到第

轮的时候，需要查询的次数如下。

的时候

。假设 1 秒能确认 1 万亿（

）个数字，那么

秒便能得出结果，比全排列算法的效率高得多。

No. 0-2　运行时间的计算方法

了解输入数据的量和运行时间之间的关系

上一节在结尾说明了算法的不同会导致其运行时间产生大幅变化，本节将讲解如何求得算法的运行时间。

使用相同的算法，输入数据的量不同，运行时间也会不同。比如，对 10 个数字排序和对 1 000 000 个数字排序，大家很容易就想到后者的运行时间更长。那么，实际上运行时间会长多少呢？后者是前者的 100 倍，还是 1 000 000 倍？就像这样，我们不光要理解不同算法在运行时间上的区别，还要了解根据输入数据量的大小，算法的运行时间具体会产生多大的变化。

3

如何求得运行时间

那么，如何测算不同输入所导致的运行时间的变化程度呢？最为现实的方法就是在计算机上运行一下程序，测试其实际花费的时间。但是，就算使用同样的算法，花费的时间也会根据所用计算机的不同而产生偏差，十分不便。

所以在这里，我们使用“步数”来描述运行时间。“1 步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。

作为示例，现在我们试着从理论层面求出选择排序的运行时间。选择排序的步骤如下。

① 从数列中寻找最小值 ② 将最小值和数列最左边的数字进行交换，排序结束。回到①

如果数列中有

个数字，那么①中“寻找最小值”的步骤只需确认

个数字即可。这里，将“确认 1 个数字的大小”作为操作的基本单位，需要的时间设为

，那么步骤①的运行时间就是

。

接下来，把“对两个数字进行交换”也作为操作的基本单位，需要的时间设为

。那么，①和②总共重复

次，每经过“1 轮”，需要查找的数字就减少 1 个，因此总的运行时间如下。

虽说只剩最后 1 个数字的时候就不需要确认了，但是方便起见还是把对它的确认和交换时间计算在内比较好。

4

运行时间的表示方法

虽说我们已经求得了运行时间，但其实这个结果还可以简化。

和

都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度

，所以接下来考虑

变大的情况。

越大，上式中的

也就越大，其他部分就相对变小了。也就是说，对式子影响最大的是

。所以，我们删掉其他部分，将结果表示成下式右边的形式。

通过这种表示方法，我们就能大致了解到排序算法的运行时间与输入数据量

的平方成正比。同样地，假设某个算法的运行时间如下。

那么，这个结果就可以用

来表示。如果运行时间为

这个结果就可以用

来表示。

这个符号的意思是“忽略重要项以外的内容”，读音同 Order。

的含义就是“算法的运行时间最长也就是

的常数倍”，准确的定义请参考相关专业书籍。重点在于，通过这种表示方法，我们可以直观地了解算法的时间复杂度 1。

1时间复杂度是一个可以描述算法运行时间的函数，常用大

符号来表述。——译者注

比如，当我们知道选择排序的时间复杂度为

、快速排序的时间复杂度为

时，很快就能判断出快速排序的运算更为高速。二者的运行时间根据输入

产生的变化程度也一目了然。

关于算法的基本知识就介绍到这里了。从下一章开始，我们就来具体学习各种算法吧。

本文来自《我的第一本算法书》