本节书摘来自异步社区《趣题学算法》一书中的第0章0.4节算法的正确性，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。

0.4　算法的正确性

解决一个计算问题的算法是正确的，指的是对问题中任意合法的输入均应得到对应的正确输出。大多数情况下，问题的合法输入无法穷尽，当然就无法穷尽输出是否正确的验证。即使合法输入是有限的，穷尽所有输出正确的验证，在实践中也许是得不偿失的。但是，无论如何，我们需要保证设计出来的算法的正确性。否则，算法设计就是去了它的应用意义。因此，对设计出来的算法在提交应用之前，应当说明它的正确性。这就需要借助我们对问题的认识与理解，利用数学、科学及逻辑推理来证实算法是正确的。例如，对于解决“计算逆序数”问题的算法0-1，其正确性可以表述为如下命题：

当第3～7行的for循环结束时，count已记录下了序列A[1..N]中的逆序数。

如果我们能说明上述命题是真的，那就说明了算法0-1是正确的。由于数组A[1..N]的长度N是任意正整数，所以这是一个与正整数相关的命题。数学中要证明一个与正整数相关的命题有一个有力的工具——数学归纳法。下面我们对本命题中的N进行归纳。

当N=1时第3～7行的for循环重复0次。count保持初始值0，这与A[1..N]=A[1]没有任何逆序相符，结论显然为真。

设N>1且可用算法计算出A[1..N−1]的逆序数count。在此假设下，我们来证明对A[1..N]利用算法0-1也能得到正确的逆序数count。

考虑算法中第3～7行的for循环在j=N时的第一次重复的操作：第4～6行内嵌的for循环从i=1开始到j−1为止，逐一检测是否A[i]>A[j]。若是，意味着找到一个关于A[N]的逆序，第6行count自增1。当此循环结束时count中累积了关于A[N]的逆序数。由于N>1，故第3～6行的外围for循环必定会继续对A[1..N−1]做同样的操作。根据归纳假设，我们知道第3～6行的for循环接下来的重复操作能将A[1..N−1]中个元素的逆序数累加到count中。所以第3～6行for循环结束时，count已记录下了序列A[1..N]中的逆序数。

这样，我们就从逻辑上证明了算法0-1能正确地解决“计算逆序数”问题的一个案例，即算法0-1是正确的。

应当指出，解决一个计算问题时，算法不必唯一。数据的组织方式、解题思路的不同，会导致不同的算法。

例如，将计数器count设置为全局变量，并初始化为0。解决“计算逆序数”问题一个案例的算法还可以表示为如下的形式。

GET-THE-INVERSION(A, N)            ▷A[1..N]表示一个序列1 if N<22     then return3 for i←1 to N-1 4   do if A[i]>A[N]                ▷检测到一个逆序5     then count←count+1           ▷累加到计数器6 GET-THE-INVERSION(A, N-1)

算法0-2　解决“计算逆序数”问题一个案例的递归算法伪代码过程

这是一个“递归”算法，它在定义的内部（第6行）进行了一次自我调用。受上述算法0-1正确性命题证明的启发，这个算法的思想是基于先计算出A[1..N-1]中关于A[N]的逆序数count，然后将问题归结为计算A[1..N-1]的逆序数的子问题。用相同的方法解决子问题（递归调用自身，注意表示A的长度的第2个参数变成N-1）把子问题的解与count合并就可得到原问题的解。其实，算法0-2与算法0-1仅仅是表达形式不同，本质上等价的：后者用末尾递归（第6行递归调用自身）隐式地替代算法0-1中第3～6行的外层for循环。所以，算法0-2也是正确的。