算法基础与大O表示法

#算法基础与大O表示法

• 什么是算法
• 排列整数的算法：选择排序
• 如何选择算法
• 运行时间的计算方法
• 大O表示法
• 常见的大O运行时间
• 旅行商问题

#什么是算法

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

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

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

#排列整数的算法：选择排序

来看一个具体的算法示例吧。这是一个以随意排列的整数为输入，把它们按从小到大的顺序重新排列的问题。这类排序问题属于排序算法的范畴。

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

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

7 13 4 5 8 1 11 9   →   1 13 4 5 8 7 11 9

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

1 13 4 5 8 7 11 9   →   1 4 13 5 8 7 11 9

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

这便是选择排序。不管输入的数字是什么、n 有多大，都可以用这个算法解决问题。

#如何选择算法

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

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

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

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

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

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

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

n 个数字有 n! 种不同的排列方法（n! = n×(n-1)×(n-2)×…×3×2×1）。n=50 时，50! 远大于 10^40。假设 1 台高性能计算机 1 秒能检查 1 万亿（=10^12）个数列，那么检查 10^40 个数列将花费 10^28 秒，超过 10^20 年。

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

而使用选择排序算法呢？总查询次数为 n+(n-1)+…+1 ≈ n²/2。n=50 时 n²=2500，0.0000000025 秒便能得出结果。

#运行时间的计算方法

使用相同的算法，输入数据的量不同，运行时间也会不同。最为现实的方法就是在计算机上运行程序测试其实际花费的时间，但不同计算机的偏差十分不便。所以在这里，我们使用「步数」来描述运行时间——通过测试「计算从开始到结束总共执行了多少步」来求得算法的运行时间。

以选择排序为例，如果把「确认 1 个数字的大小」作为操作的基本单位（时间 Tc），「对两个数字进行交换」需要的时间设为 Ts，那么总的运行时间经过化简后为：

(1/2)·Tc·n² + (1/2·Tc + Ts)·n

Tc 和 Ts 都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度 n，当 n 越大时，n² 项对式子影响最大。所以删掉其他部分，将结果表示成 O(n²)。

#大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。它指的并非以秒为单位的速度，而是操作数的增速——随着输入的增加，运行时间将以什么样的速度增加。

运行时间以不同的速度增加：假设检查一个元素需要 1 毫秒。列表包含 100 个元素时，简单查找需要 100 毫秒，二分查找需要 7 毫秒，看似只快 15 倍。但列表包含 10 亿个元素时，简单查找需要 10 亿毫秒（约 11 天），二分查找只需 30 毫秒——快了 3300 万倍！因为两者的运行时间增速有天壤之别。

大O表示法指出的是最糟情况下的运行时间：简单查找的运行时间总是 O(n)，即使在最糟情况下必须查看每个条目。这是一个保证——你知道简单查找不可能超过 O(n)。

O 这个符号的意思是「忽略重要项以外的内容」，读音同 Order。O(n²) 的含义就是「算法的运行时间最长也就是 n² 的常数倍」。

#常见的大O运行时间

按从快到慢的顺序：

大O运行时间	名称	示例算法
O(1)	常数时间	数组随机访问
O(log n)	对数时间	二分查找
O(n)	线性时间	简单查找
O(n log n)	线性对数时间	快速排序
O(n²)	平方时间	选择排序
O(n!)	阶乘时间	旅行商问题

画网格的例子理解不同运行时间：要画一个 16 格的网格。

• O(n) 算法：每次画一个格子，需要 16 步
• O(log n) 算法：将纸对折，每折一次格子数翻倍，折 4 次就得到 16 格

主要启示：

• 算法的速度指的并非时间，而是操作数的增速
• 谈论算法的速度时，说的是随着输入的增加，其运行时间以什么样的速度增加
• 算法的运行时间用大O表示法表示
• O(log n) 比 O(n) 快，需要搜索的元素越多，前者比后者快得越多

#旅行商问题

旅行商问题是一个运行时间为 O(n!) 的算法。有一位旅行商需要前往 5 个城市，同时要确保旅程最短。为此必须考虑各种可能顺序：

• 5 个城市有 120 种排列
• 6 个城市有 720 种
• 7 个城市有 5040 种

涉及 n 个城市时，需要执行 n! 次操作。如果涉及的城市超过 100 个，根本不能在合理时间内计算出结果——等你算完，太阳都没了。

这是计算机科学领域待解的问题之一，目前还没有找到更快的算法。面对这个问题，我们能做的只是找出近似答案（见贪婪算法）。