为什么算法的定义非得要求它既有限又必须终止呢？

第一次学算法时，大多数人都会觉得课本里的定义有点“严格过头”： 为什么一定要有有限条指令？ 为什么一定要求对每个输入都终止？ 难道一个“很像算法”的过程，只要偶尔不结束，就不算算法了吗？最短路，并查集，排序，难道还有终止不了的算法？ 其实，这些要求不是为了咬文嚼字，而是为了把“算法”这个概念和一般的程序、搜索过程、模糊做法区分开。没有“有限性”和“终止性”，我们就很难保证一个过程真的是一种明确、可执行、可用于解题的方法。 算法定义里的关键词 算法通常包含这些核心要素： 它是一个过程（procedure） 它由有限条指令组成（finite set of instructions） 它接收输入（input） 它产生输出（output） 它的执行是系统化、明确的（systematic execution） 它对每个输入都应该停机（halt on every input） 每条指令都应在有限时间内完成 每个合法输入对应的输出应当是唯一的 其中，最容易让人疑惑的，正是有限性和终止性。 为什么要有“有限性” “有限性”可以理解为三个层面： 指令的数量是有限的 每条指令本身能在有限时间内完成 输入的长度是有限的 这些要求的核心目的，是保证算法是一个可描述、可执行的机械过程。 代码规则有限 没有有限性，规则可能根本写不完。设想一个“过程”是这样定义的： 第1步处理输入为1的情况 第2步处理输入为2的情况 第3步处理输入为3的情况 …… 看起来它似乎在“处理所有输入”，但问题在于：这需要一份无限长的代码。这就不再是我们想要的算法了。算法不应该给每一个输入单独写一条规则，而是用有限的规则统一处理无限多可能的输入。 单个步骤有限 再看另一种情况。假设某一步写成： “检查所有自然数都不满足某性质，然后再继续下一步。” 这条指令听起来很清楚，但它本身就需要无限时间，因为“检查所有自然数”永远做不完。 也就是说，即使总共只有三五步，只要其中某一步本身无法在有限时间内完成，这个过程也不能算算法。 为什么要有“终止性” 终止性指的是：对每一个输入，算法都必须在有限时间内结束。 这个要求的意义非常直接：如果一个过程永远不结束，那么你就永远得不到答案。比如下面这个过程： while x != 0: x = x + 1 如果输入 x = 1，那么变量会变成： 1 → 2 → 3 → 4 → 5 → ... 它永远不可能回到 0，因此程序永远不会结束。这个过程即使写得很明确、每一步都能执行，也仍然可能不终止。而一旦不终止，它就不满足严格意义上的算法定义。 更常见的反例：有解时能停，没解时不停 还有一种更有代表性的情况： 设想我们要判断某个方程是否有整数解，于是设计如下过程： 枚举所有可能的整数对 检查它们是否满足方程 一旦找到解就输出并停止 这个过程很有用，但它有个问题： 如果方程有解，它迟早能找到，于是停机 如果方程无解，它会一直枚举下去，永远不停 所以它并不满足“对每个输入都终止”的要求。 这类过程在理论计算机中很常见，它们不是严格意义上的算法，而更像是一种半判定过程。 有限性和终止性的意义 这两个要求，其实是在防止三类“伪算法”混进来。 第一类：无限长说明书：对每个输入单独写一条规则，导致整个“方法”无法用有限方式描述。 第二类：单步无限耗时：表面上步骤不多，但其中某一步本身就永远做不完。 第三类：永远不给答案的程序：过程确实开始执行了，也一步一步在跑，但在某些输入上会陷入无限循环，永远得不出结果。