1.2 算法和算法的表示

1.2.2 算法的基本特征

算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。对于该类问题的任何初始输入值，它都能机械地一步一步地执行计算，经过有限步骤后终止计算并产生输出结果。归纳起来，算法具有以下基本特征：

(1) 有穷性：一个算法必须在执行有限个操作步骤后终止；

(2) 确定性：算法中每一步的含义必须是确切的，不可出现任何二义性；

(3) 有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数被0除的操作就是无效的，应当避免这种操作。

(4) 有零个或多个输入：这里的输入是指在算法开始之前所需要的初始数据。这些输入的多少取决于特定的问题。例如，例l-1的算法中有2个输入，即需要输入a和b两个初始数据，而例l-2的算法中则需要输入四个初始数据。有些特殊算法也可以没有输入。

(5) 有一个或多个输出：所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。如上述关于算法的三个例子中，每个都有输出。试想，如果例1-3中没有 "输出n的当前值"这一步，这个算法将毫无意义。

通常算法都必须满足以上五个特征。需要说明的是，有穷性的限制是不充分的。一个实用的算法，不仅要求有穷的操作步骤，而且应该是尽可能有限的步骤。例如，对线性方程组求解，理论上可以用行列式的方法。但是我们知道，要对n阶方程组求解，需要计算n+1个n阶行列式的值，要做的乘法运算是（n！）（n-l）（n+1）次。假如n取值为20，用每秒千万次的计算机运算，完成这个计算需要上千万年的时间。可见，尽管这种算法是正确的，但它没有实际意义。由此可知，在设计算法时，要对算法的执行效率作一定的分析。

上一页  [1] [2] [3] [4]  下一页