1.1.3 算法

### 1.1.3 算法 如前所述，程序是解决某个问题的指令序列。编程解决一个问题时，首先要找出解决问 题的方法，该解决方法一般先以非形式化的方式表述为由一系列可行的步骤组成的过程，然 后才用形式化的编程语言去实现该过程。这种解决特定问题的、由一系列明确而可行的步骤 组成的过程，称为算法（algorithm①）。算法表达了解决问题的核心步骤，反映的是程序的解 题逻辑。 算法其实并不是随着计算机的发明才出现的东西。例如，早在两千多年前，古希腊数学 家欧几里德就发明了一种求两个自然数的最大公约数的过程，这个过程被认为是史上第一个 算法②： 【欧几里德算法】 ``` 输入：自然数 a、b 输出：a、b 的最大公约数 步骤： 第 1 步：令 r 为 a / b 所得余数 第 2 步：若 r = 0，则算法结束，b 即为答案；否则置 a←b，b←r，转到第 1 步。 ``` 又如，我们在小学学习的竖式乘法、长除法等等其实也都是算法的例子，都是通过明确 定义的一步一步的过程来解决问题。 利用计算机解决问题的关键就在于设计出合适的算法，当今计算机在各行各业中的成功 应用从根本上说都取决于高效算法的发现。例如，数学家发明了“充电放电”算法，从而利 用计算机证明了著名的四色定理。又如，谷歌公司的创建者发明了更合理的网页相关性排名 算法，从而使 Google 成为最成功的搜索引擎。其他如 MP3 播放器等便携式电子产品依靠聪 明的音频视频压缩算法来节省存储空间，GPS 导航仪利用高效的最短路径算法来规划最短路 线等等，不一而足。 算法是由一系列步骤构成的计算过程，但并不是随便用一些步骤都能构成合格的算法 的。我们对算法有两个要求：第一，每个步骤必须具备明确的可操作性；第二，构成算法的 所有步骤必须能在有限时间内完成。 先看算法步骤的可操作性。从最底层来看，计算机指令集中的基本指令显然具有可操作 性，因为 CPU 确定无疑地能够执行这些指令。然而，由于用简单的机器指令来表达算法步骤 会使得算法琐碎冗长，不能凸显算法表达的解题逻辑，所以实际上我们会用更高级别的操作 来表达算法步骤。打个比方，如果在菜谱中使用非常细节化的指令，那么在很多菜的菜谱中 都会看到这样的步骤： ``` …… 冷水入锅 点火将水烧开 某蔬菜入锅 等水再次烧开 捞出蔬菜备用 …… ``` 这种步骤虽然详细，但太琐碎了。几乎没有菜谱会在这样的细节级别上表达操作步骤，一般 都会将这个过程写做： ``` …… 将某蔬菜绰水 …… ``` > ① 这个词源自 9 世纪波斯数学家 Muhammad ibn Musa al-Khwarizmi 的姓（拉丁语写法 Algorismus）。 > ② 中国称为辗转相除法。 其中“绰水”是一个较高级别的指令，它本身又由若干更细节化的步骤组成，但它显然是一 个明确定义的步骤，按照这样的菜谱去做菜，完全是可操作的。 再以数学为例，“计算 b2 - 4ac”作为算法中的一个步骤显然是可操作的，没有必要细化 为“先计算 b2，再计算 4ac，再两者相减”的步骤；而“作一条平行于直线 AB 的直线”就 不是一个明确的步骤。至于“用尺规作图来三等分角ÐAOB”，则根本就是一个不可能做到的 操作，尽管其意义是明确的。 总之，在设计算法时，要选择合适的细节级别的步骤，不但要确保所有步骤处于计算机 能力范围之内，还应该使算法的读者容易理解算法的逻辑。 再看算法的有限性。只满足算法步骤的可操作性是不够的，一个合格的算法还必须能在 有限时间内执行完毕。例如，具备一点数论知识的人都知道“检查自然数 n 是不是质数”是 可行的步骤，例如可以逐个检查从 2 到 n/2 的自然数是不是 n 的因子。那我们能不能设计如 下“算法”来生成所有质数呢？ ``` 第 1 步：令 n = 2 第 2 步：检查 n 是不是质数 第 3 步：如果是就输出 n 第 4 步：n = n + 1，转到第 2 步 ``` 很遗憾，这不是一个合格的算法，因为自然数有无穷多个，导致“算法”的第 4 步是可 以无限进行下去的。 那么对一个给定的问题，能不能找到符合上述要求的算法呢？这其实正是计算机科学要 回答的一个基本问题：什么是可计算的？如果能够为某个问题找到算法，该问题就称为可计 算的。当然，如果没能找到算法，并不意味着该问题不可计算，那也许只是因为我们不够聪 明而已。事实上，计算机科学还从理论上对可计算性和计算复杂性进行分析。本书第 x 章会 告诉大家，有一些看似简单的问题实际上不存在算法，而另一些问题虽然有算法但需要天文 数字的时间和空间来完成计算，从而毫无实际价值。