1
算法与数据结构  C语言版
1.3.3.2 1.3.2 算法的特性
1.3.2 算法的特性

作为一个算法,一般应具有以下几个基本特征。

1.确定性

算法的每一种运算必须有确定的意义,该种运算应执行何种动作应无二义性,目的明确;这一性质反映了算法与数学公式的明显差别。在解决实际问题时,可能会出现这样的情况:针对某种特殊问题,数学公式是正确的,但按此数学公式设计的计算过程可能会使计算机系统无所适从,这是因为根据数学公式设计的计算过程只考虑了正常使用的情况,而当出现异常情况时,此计算过程就不能适应了。

2.可行性

要求算法中有待实现的运算都是基本的,每种运算至少在原理上能由人用纸和笔在有限的时间内完成;针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的,因此,算法在执行过程中往往要受到计算工具的限制,使执行结果产生偏差。

3.输入

一个算法有1个或多个输入,在算法运算开始之前给出算法所需数据的初值,这些输入取自特定的对象集合。

4.输出

作为算法运算的结果,一个算法产生一个或多个输出,输出是同输入有某种特定关系的量。

5.有穷性

一个算法总是在执行了有穷步的运算后终止,即该算法是可达的。数学中的无穷级数,在实际计算时只能取有限项,即计算无穷级数值的过程只能是有穷的。因此,一个数的无穷级数表示只是一个计算公式,而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应包括合理的执行时间的含义。因为如果一个算法需要执行千万年,显然失去了实用价值。

满足前四个特性的一组规则不能称为算法,只能称为计算过程,操作系统是计算过程的一个例子。在一个算法中,有些指令可能是重复执行的,因此指令的执行次数可能是远远大于算法中的指令条数。由有穷性可知,对于任何输入,一个算法在执行了有限条指令后一定要终止并且必须在有限的时间内完成,因此,一个程序如果对任何输入都不会陷入无限循环,即是有穷的,则它就是一个算法。