1.1.2　算法的定义及特性

算法的历史可以追溯到9世纪的古波斯。最初它仅表示“阿拉伯数字的运算法则”。后来，它被赋予更一般的含义，即所谓的一组确定的、有效的、有限的解决问题的步骤。这是算法的最初定义，注意，这个定义里面没有包括“正确”一词。

推动算法传播的是生活在美索不达米亚的Al Khwarizmi。他于9世纪以阿拉姆语著述了一本教科书。该书列举了加、减、乘、除、求平方根和计算圆周率数值的方法。这些计算方法的特点是：简单、没有歧义、机械、有效和正确，这就是算法。注意，这个定义加上了“正确”一词。几百年后，当十进制记数法在欧洲被广泛使用时，“算法”（Algorithm）这个单词被人们创造出来以纪念Al Khwarizmi先生。当代著名计算机科学家D.E. Knuth在他撰写的The Art of Computer Programming一书中写道：“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”

由上面所述可推知，任何解决问题的过程都是由一定的步骤组成的，通常把解决问题的确定方法和有限步骤称为算法。对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列，并且它具有以下特性：

（1）输入。有零个或多个输入，由外界提供或自己产生。

（2）输出。有一个或多个输出。算法是为解决某问题而设计的，其最终目的就是获得问题的解，没有输出的算法是无意义的。

（3）确定性。组成算法的每条指令必须有确定的含义，必须无歧义。在任何条件下，对于相同的输入只能得到相同的输出结果。

（4）有限性。算法中每条指令的执行次数都是有限的，执行每条指令的时间也是有限的。也就是说，在执行若干条指令之后，算法将结束。

（5）可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次后实现。换句话说，要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。