下载掌阅APP，畅读海量书库
立即打开
算法（Algorithm）是对解题方案准确而完整的描述，是一系列解决问题的清晰指令，是用系统的方法描述解决问题的策略机制。算法能够对符合约束条件的、确定的输入，在有限时间内获得所要求的输出。一般来说，问题陈述说明了期望的输入/输出关系。算法则描述了一个特定的计算过程来实现该输入/输出关系。如果一个算法有缺陷或不适合解决某个问题，那么执行这个算法将不会解决问题。下面用一个例子来进一步解释算法的基本概念及设计要点。
【例1-1】 求任意两个非负整数的最大公约数。
求最大公约数（Greatest Common Divisor，GCD）是一个经典问题，它有很多的解法，如质因数分解法、欧几里得算法（辗转相除法）、更相减损法等。它们共同的特点就是使用公约数不断进行约简，约简（迭代）的次数越少，算法的效率就越高。因此，算法设计的要点在于约数的选择上。这里分别采用穷举法和欧几里得算法来进行求解，并对比两种算法的执行效率。
设 a ， b >0且 a > b 。
（1）穷举法
若式（1-2）成立，则 r 是 a 、 b 的最大公约数，否则执行式（1-3），然后再用式（1-2）进行测试。反复执行式（1-3）、式（1-2），直到式（1-2）成立为止，则 r 即为所求。
（2）欧几里得算法
设 r = a mod b 。当 r ≠0时，依据欧几里得定理，有：
首先执行式（1-4），若 r =0，则 b 为 a 、 b 的最大公约数，否则运用式（1-5）变换 a 、 b 的值为 a = b 、 b = r 。反复迭代式（1-4）和式（1-5），直到使 r =0时，则 b 即为所求。
本例用了两种算法求解两个数的最大公约数，那么，哪种更好呢？现在用一组实例来测算一下两种算法，比较哪种效率更高。设 a =21、 b =14，按“算法设计与描述”中的步骤，执行过程如下。
（1）穷举法
① r =14, 21 mod 14=7 and 14 mod 14=0, r =14-1=13；
② 21 mod 13=8 and 14 mod 13=1, r =13-1=12；
③ 21 mod 12=9 and 14 mod 12=2, r =12-1=11；
④ 21 mod 11=10 and 14 mod 11=3, r =11-1=10；
⑤ 21 mod 10=1 and 14 mod 10=4, r =10-1=9；
⑥ 21 mod 9=3 and 14 mod 9=5, r =9-1=8；
⑦ 21 mod 8=5 and 14 mod 8=6, r =8-1=7；
⑧ 21 mod 7=0 and 14 mod 7=0，输出 r 。
（2）欧几里得算法
① r =21 mod 14=7, a =14, b = r =7；
② r =14 mod 7=0，输出 b 。
通过上述实例的测试可知，欧几里得算法只用了2步，而穷举法用了8步，显然欧几里得算法要快很多！然而，这个结论并不客观。因为变量 a 、 b 有无穷多个取值， a =21、 b =14只是其中的一组，我们称之为求 a 、 b 最大公约数问题的一个输入实例。严格来说，要想用这种举例的方法来证明“欧几里得算法比穷举法更快”这一结论，需要把所有可能的输入实例全部测试完毕，但这是不可能的。而且即使能够穷举完毕，也不能得出上述结论。如 a =21、 b =7，两种算法运算的步数是一样的。显然，通过穷举实例的方法来评价算法效率并不合适。算法效率分析是需要借助一些数学工具的，相关的基础理论知识将在第2章中介绍，这里我们直接给出它们的分析方法及结论，供大家参考。
（1）穷举法算法分析
若 a 、 b 互质，则公约数测算的取值范围为 b , b -1, b -2,…,1，否则，不妨设测算至 b - i 时结束，那么，可能的测试次数为：
其中， p i 为测算所取到值的概率。若每个取值的概率相等，则 p i =1/ b ，由式（1-6）可得平均运算次数为：
（2）欧几里得算法分析
设
a
>
b
≥1，构造数列
，其中
k
≥2。
若算法需要 n 次模运算，则有：
比较数列{ u n }和斐波那契数列{ F n }，可得：
因为
，可得
（
m
为商，
u
k+2
为余数），从而可得
。由数学归纳法容易得到
，于是得到
。
如果欧几里得算法需要做
n
次模运算，则
b
必定不小于
F
n-1
。换句话说，若
，则算法所需模运算的次数必定小于
n
（对应
F
n
-2或
F
n-3
……，必然小于
n
次运算）。
斐波那契数列的通项公式为：
比较式（1-7）与式（1-8）可知，当 b >11时，式（1-8）的值开始小于式（1-7）的值。 b 值越大，两式的差值越大。这符合两种算法运算效率的走势。事实上，在分析算法效率时，一般不考虑系统及常数项，那么，对数级别运算效率的算法要远好于线性级别运算效率的算法。
为什么能用斐波那契数列去评估欧几里得算法的运算效率（运算次数）呢？观察两个算法的表达式：
不难看出它们所具有的相似性，尽管计算效率不同，但是求到第 n 项时的运算次数是相同的，因此可以用斐波那契数列项数来估算欧几里得算法的运算次数。不过，在实际使用中，这种估算还是存在一定差异的，但它可以反映出斐波那契数列是欧几里得算法复杂度的界函数的特性（详见第2章）。
通过上述例子，可以得到以下要点。
（1）必须确定算法所输入的取值范围。
（2）对于输出有明确的要求，输出= f （输入）并在有限步骤内结束。
（3）算法设计必须是严谨、可行且正确的。
（4）算法每一个步骤都有确切的含义。
（5）同一算法可以用几种不同的形式来描述。
（6）同一问题，可能存在几种不同的求解算法。
（7）针对同一问题的不同算法，其运算效率也可能不一样。