序章
算法的基本知识

0-1 什么是算法

算法与程序的区别

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

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

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

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

排列整数的算法：排序

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

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

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

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

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

我们将这样的一次交换称为“1轮”。到了第k轮的时候，就把剩下的数字中最小的一个，与左边开始第k个数字进行交换。于是在结束第k轮后，从左数的k个数字便都按从小到大的顺序排列了。只要将这个步骤重复n次，那么所有的数字都将按从小到大的顺序排列。

这便是我们将在2-3节中介绍的选择排序。不管输入的数字是什么、n有多大，都可以用这个算法解决问题。

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

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

计算机是以这些基本命令的组合为基础运行的，面对复杂的操作，也是通过搭配组合这些基本命令来应对的。上文中提到的“对n个数字进行排序”对计算机来说就是复杂的操作。如何设计算法来解决这个排序问题，也就等同于构思如何搭配组合计算机可以执行的那些基本命令来实现这个操作。

如何选择算法

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

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

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

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

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

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

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

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

n个数字有n！种不同的排列方法（n! =n（n-1）（n-2）…3·2·1）。现在，我们来看看n=50时是怎样一种情况吧。

公式①中，50！即为数字1到数字50的乘积。为了便于计算，我们通过公式②③将结果近似转换为10的n次方的形式。公式②右边部分去掉了10以下的数字，因此小于50!。公式③左右都是40个数字的乘积，但左边数字都大于10，因此大于右边的1040。接下来我们就用1040近似代表50个数字的所有排列情况来进行计算。

假设1台高性能计算机1秒能检查1万亿（=1012）个数列，那么检查1040个数列将花费的时间为1040÷1012=1028秒。1年为31536000秒，不到108秒。因此，1028秒＞1020年。

从大爆炸开始宇宙已经经历了约137亿年，即便如此也少于1011年。也就是说，仅仅是对50个数字进行排序，若使用全排列算法，就算花费宇宙年龄的109倍时间也得不出答案。

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

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

首先，为了在第1轮找到最小的数字，需要从左往右确认数列中的数字，只要查询n个数字即可。在接下来的第2轮中，需要从n-1个数字中寻找最小值，所以需要查询n-1个数字。将这个步骤进行到第n轮的时候，需要查询的次数如下。

n=50的时候n2=2500。假设1秒能确认1万亿（=1012）个数字，那么2500÷1012=0.0000000025秒便能得出结果，比全排列算法的效率高得多。