《算法设计与分析》一一1.2 抽象算法设计

1.2　抽象算法设计

算法设计源于我们面临一个有待解决的算法问题。为此，我们首先讨论算法问题的严格定义，其次讨论算法设计，主要讨论证明算法正确性的基本方法。

1.2.1　算法问题规约

基于ram模型，我们主要讨论这样的算法：它接受有限的数据作为输入，进行相应的处理，在有限步内终止，并给出输出。因此我们可以将算法问题严格地定义为精确限定输入/输出的“规约”(specification)形式。

定义1.1（算法问题规约）　一个算法问题的规约主要包括两部分：

●输入：明确规定了算法接受的所有合法输入。

●输出：明确规定了对于每一个合法的输入值，相应的输出值应该是什么。

例如，“求最大公约数问题”这一算法问题我们可以给出其规约如下：

●输入：任意两个非负整数a、b。

●输出：a、b的最大公约数 　≌饫锛偕枳畲蠊 约数这一数学概念的定义是明确的。 　?

针对上述明确定义的算法问题，我们可以设计相应的算法来解决它。这里给出著名的欧几里得算法，又叫“辗转相除法”，如算法1所示。算法1：euclid(a, b)

1　if b=0 then

2　return a;

3　else

4　return euclid(b, a mod b);1.2.2　算法正确性证明：数学归纳法

有了算法问题的严格定义，我们就有了讨论算法正确性的(唯一)标准。要证明算法的正确性，就是要证明对于任意的合法的输入，算法的输出总是满足规约的要求。以欧几里得算法为例，我们要证明该算法的正确性就是要证明：对于任意两个非负整数的输入，算法输出的结果一定是输入的两个数的最大公约数。

根据上面的讨论，我们发现证明算法正确性的核心挑战在于：算法可能的输入有无穷多种，我们需要保证无穷多种输入对应的输出都必然是对的。显然，具体工程实现中常用的测试技术无法证明算法的正确性。无论对多大规模的输入进行测试，始终有无穷多的输入是我们无法覆盖到的。众所周知，测试只能证明程序是有错的，而不能证明程序是无错的。测试只能尽量减少算法中的错误。

要证明一个可数无穷多的集合中的每个元素均满足某种性质，主要的手段是数学归纳法。在实际使用中，我们经常将数学归纳法分为强、弱两种形式。

定义1.2（弱数学归纳法）　假设p是一个定义在自然数集合n上的命题 ?∮械那榭鱿拢 我们会定义p是定义在非负整数上的命题，这本质上是一样的。 ?Ｈ绻：

●p(1)为true。

● ?∈n,p(k)→p(k+1)。

则对所有的自然数n，p(n)为true。

定义1.3（强数学归纳法）　假设p是一个定义在自然数集合n上的命题。如果：

● ?∈n,p(1)∧p(2)∧…∧p(k)→p(k+1)。

以数学归纳法为基本手段，证明算法正确性的关键是，将算法面对无穷多种输入，无穷多种可能的执行情况，按照某种原则变成关于自然数的无穷个命题p(1),p(2),…,p(n),…，然后再基于数学归纳法进行证明。需要指出的是这两种数学归纳法都可以看作源于更基本的良序原理(well-ordering principle)。强、弱数学归纳法和良序原理这3种形式不同的证明在本质上是等价的，只不过在不同的场景下，某一种证明方式使用起来更加便捷。关于数学归纳法与良序原理的详细讨论参见附录a。

下面以欧几里得算法为例，讨论算法的正确性证明。

定理1.4　euclid算法是正确的。

证明：要证明算法的正确性，就要证明：对于任意的非负整数输入a、b，算法输出的一定是a、b的最大公约数，记为gcd(a,b)。我们采用数学归纳法，对输入的第二个参数b进行归纳。为此，我们将要证明的结论转换成关于非负整数的无穷多个命题：p(0)= ?,算法对输入a、0给出正确输出

…

p(k－1)= ?,算法对输入a、k-1给出正确输出

p(k)= ?, 算法对输入a、k给出正确输出首先对基础情况p(0)进行证明。根据算法的实现，无论第一个参数a的取值是多少，euclid(a,0)总是返回a，这一结果符合我们对最大公约数的定义，所以p(0)为true。

归纳假设当第二个输入参数b≤k－1时，算法总是正确的，即 ?≤k－1,p(b)为true。下面考虑p(k)的情况。根据算法实现，对于输入(a,k)，算法将返回euclid(k,a mod k)。根据归纳假设，由于a mod k≤k－1，所以算法总能正确计算b和a mod b的最大公约数。根据最大公约数的性质，有gcd(a,k)=gcd(k,a mod k)。我们将上述相等关系串联起来，如下面的公式所示：euclid(a,k)　=　根据算法实现euclid(k,a mod k)　=　根据归纳假设gcd(k,a mod k)　=　根据最大公约数性质gcd(a,k)由此，我们就证明了对于任意的a，算法总能正确计算a、k的最大公约数，即证明了p(k)。　

根据数学归纳法，我们证明了对任意非负整数n，命题p(n)为true，即证明了euclid算法是正确的。