算法的性质

一个算法是对一种计算过程的一个严格描述,人们i通常认为的算法具有以下性质:

  有穷性(算法描述的有穷性):一个算法的的描述由有限多条指令或语句构成。也就是说,算法必须能用有限长的描述说清楚。

  能行性:算法中的指令(语句)的含义严格简单明确,所描述的操作(计算)过程可以机械的进行。

  确定性:作用于所求解的问题的给定输入(以某种描述形式给出的要处理问题的具体实例),根据算法的描述将产生出唯一的确定的一个动作序列。使用算法就是把问题实例(的表示)送给它,通过确定的操作序列,最终得到相应的解。

  终止性(行为的有穷性):对问题的任何实例,算法产生的动作序列有穷的,它或者终止并给出该问题实例的解;或者终止并指出给定的输入无解。

  输入/输出:有明确定义的输入和输出

满足确定性的算法也称为确定性算法。

人们关注并不要求终止的计算描述,这种描述有时被称为过程。