对于“算法”一词给以精确的定义不是一件容易事，有一些意义相近的同义语，就是一些其他的名词，它们（有时）会给出差不多同样的东西，例如"法则""技巧”“程序”还有“方法”等等都是这种同义语。也可以给出一些例子，如长乘法，就是小学生学的把两个正整数相乘的竖式乘法。然而，虽然非形式的解释和恰当的例子对于什么是算法给出了很好的感觉，但算法一词中所深藏的思想却经历了一个很长的演化历程，直得到20世纪才得到了令人满意的形式定义，而关于算法的观念，直到如今还在演进。

算盘家和算法家

回到关于乘法的例子，有一点是显然的：怎样把两个数相乘？表示这些数的方法极大地影响了乘法的具体作法。为了弄明白这点，试着把两个罗马数字CXLVII 和XXIX相乘，但不要先把它们译成等价的十进数字147和29。这件事既难弄明白，明白了以后进行计算也极其花时间，而这就可以解释何以留存至今的罗马帝国关于乘法的材料极为零散。记数制可以是"累加的"，如罗马记数法：

C表示100。X表示10。L表示50，但是X放在L左方表示要从L中减去X，所以就是40，V 表示5，I表示1，两个I放在V的右方，表示要把它们加到V上，所以是7。把所有以上的解释“累加”起来，就是罗马数学的147。

记数制度也可以是进位的，如我们今天所用的那样。如果是进位的，可以使用一个或多个基底。

在很长的时期中，进行计算可以使用一种计算工具"算盘（abacus）"。这些计算工具可以表示一定基底下的进位制的数。例如，如果以10为基底、则一个标记物可以代表1个单位、或者10。或者100等等，视它是放在哪一横行或竖列而定。按照精确的规则移动这些标记物，就可以进行算术四则运算。中国的算盘就是 abacus 的一种。

到12世纪，阿拉伯数学著作被翻译为拉丁文以后，十进制就在欧洲流行开来了。这种进位制特别适合于算术运算，并且引导到许多新的计算方法。这些方法就通称为算法（algoritmus），而与在算盘上用标记物进行计算相区别。

虽然数字符号，就是数码，来自印度人的实践，而后来才为阿拉伯人所知，现在这些数码却叫做阿拉伯数码．算法（algorithm）的字源却是阿拉伯文，它是阿拉伯数学家阿尔·花拉子米的名字的变体。花拉子米是现在已知的最古老的数学书的作者，这一著作名为 《通过补全和还原做计算的纲要》（al-Kitab al-mukhtasar f hisib al-jabr wod ll-mugi balo），其中的 al-jabr后来就变成了“代数”（algebra）一词。

有限性

我们已经看到“算法”一词在中世纪是指以整数的十进制表示为基础的计算程序。但是到了17世纪，在达朗贝尔主编的《百科全书》中，算法一词被赋予了更广泛的意义，不只用于算术，还用于关于代数方法以及其他的计算程序，诸如"积分学的算法""正弦的算法"等等。

算法这个词又逐渐地被用来表示任意的具有精确规则的系统的计算程序。最后，随着计算机的作用越来越大，有限性的重要性被充分认识到了，很本质的要求是，这个过程在有限时间以后就会停止，而给出结果。所以就得到了下面的朴素的定义：

一个算法就是有限多个规则的集合，用以对数量有限的数据进行操作，而在有限多步以后产生结果。

注意，在这里一直强调有限性，在写出算法时的有限性，以及在执行算法时的有限性。

上面的陈述算不上是在经典意义下的数学定义。我们将会看到，把它进一步形式化是重要的。但是我们现在暂时也就满足于这个"定义"了，而且来看一下数学中的算法的一些经典例子。

三个历史上的例子

算法具有一种我们尚未提到的特性：迭代，也就是简单程序的反复执行。为了看清迭代的重要性，我们再一次来看一下长乘法这个例子，这是一个对任意大小的正整数都适用的方法。数字变得越大、程序也就越长。但是最关紧要的是，方法是“同样的”，如果会把两个三位数相乘，也就会把两个137位的数字相乘，而不必再去学什么新的原理，理由在于长乘法的方法里面包含了大量的仔细构造好的小得多的任务的重复执行，例如把两个一位数相乘的九九表。我们将会看到，迭代在我们所要讨论的算法中起了重要作用。

欧几里得算法：迭代

欧几里得算法是说明算法本质的最好也是最常用的例子。这个算法可以追溯到公元前3世纪。欧几里得用它来计算两个正整数的最大公约数（gcd）。

当我们最开始遇到两个正整数a和b的最大公约数时，它是定义为一个正整数，而且同为a和b的因数。然而，为了很多目的，定义它为具有以下两个性质的唯一的整数d更好。这两个性质就是：

1. 首先，d是a和b的一个因数；

2. 其次，如果c是a和b的另一个因数，则d可以被c所整除。

欧几里得的《几何原本》卷VII的前两个命题给出了求d的方法，其中第一个命题如下："给定了两个不相等的数、从较大的一数不断地减去较小的一数，如果余下的数位，都不能量度前数，直到余下的数为一单位为止，这时，原来的数为互质。"换句话说，如果辗转相减得到了数1，则gcd为1。这时，就说原来的两个数互质（或互为素数）。

辗转相减法

现在我们来一般地描述欧几里得算法，它是基于以下两点观察的：

（1）如果 a=b，则a和b的gcd就是b（或 a）。

（2）d是a和b的公约数，当且仅当它也是a-b和b的公约数。

现在设要求a和b的gcd，而且设a≥b。如果a=b，则观察（1）告诉我们，gcd就是b。若不然，观察（2）告诉我们，如果求a-b和b的gcd也会得到同样的答案。现在令a_1是a-b和b中较大的一个，而b_1则为其中较小的一个，然后再求两数的gcd。不过，现在两数中较大的一个，即a_1，小于原来两数中较大的一个，即 a。这样我们就可以把上面的程序再重复一遍：若 a_1=b_1，则a_1和b_1的gcd，亦即a和b的gcd 是b_1，若不然，就把a_1换成a_1-b_1，再来组织a_1-b_1和b_1，总之，较大的一个要放在前面，然后再继续下去，这就叫做"辗转相减"。

为了使这个程序能够进行下去，还有一个观察是需要的，这就是下面的关于正整数的一个基本事实，有时称为良序原理：

• 严格下降的正整数序列 a_0 > a1 > a2 >… 必为有限序列。

因为上面的迭代程序恰好产生了一个严格下降序列，这个迭代最终一定会停止，这就意味着在某一点上必有 a_k=b_k，而这个公共值就是a和b的gcd。

• 欧几里得算法的流程图

欧几里得除法

通常对于欧几里得算法的陈述与此稍有不同。可以应用一种较复杂的程序，称为欧几里得除法（也就是带余除法），它可以大大减少算法的步数，这种算法也称为辗转相除法。这个程序的基本事实是：若a和b是两个正整数，则必存在唯一的整数q和r，使得

数q称为商，而 r 称为余数。上面的两点说明（1）和（2）现在要代以

• 若r=0，则a和b的gcd就是b。

• a和b的gcd与b和r的gcd是相同的。

这一次，在第一步要用（b，r）代替（a，b）。如果r≠0，则还要做第二步，并用（r，r_1）来代替（b，r），r1是用r去除b所得的余数，所以r_1<r，并仿此以往。这样，就得到余数的序列是严格下降的（b>r>m>r1>r2≥0）。再用一次良序原理，即知这个程序经过有限步后一定停止，而最后一个非零的余数就是a和b的gcd。

不难看到，这两种方法，就求 gcd 而言是等价的，但就算法而言则有很大区别。例如，设 a=103 438，b=37。如果用辗转相减法，就要从103 438中累次减去37，一直到余下的差数小于37为止。这个差数与103438除以37的余数是一样的，而如果用第二种方法，一次就可以得到它。这样，使用第二种方法的理由就在于用累次减法来求除法的余数是非常低效率的。效率上的收益在实践上是很重要的，第二种方法给出的是多项式时间算法，而第一种方法所需的则是指数长的时间。

推广

欧几里得算法可以推广到许多其他背景下，只要有加法、减法和乘法的概念就行。例如它有一个变体，可以用于高斯整数环。就是形如 a＋ bi，而其中 a，b为整数的复数所成的环，它也可以用于系数为实数的多项式环中（就此而论，系数在任意域中也行）。但有一个要求，就是要能够定义带余除法的类比物，有了这一点以后、算法就与正整数情况的算法基本上相同了。例如下面的命题：设A 和B是两个任意多项式，而且B不是零多项式、则必存在两个多项式Q和R。使得或者R=0，或者 R的次数小于B的次数。

正如欧几里得在《几何原本》中提到的那样，也可以对于一对数（a，b）当a和b不一定是整数时实行这个程序。容易验证，当且仅当比 a/b是有理数时，这个程序会停下来。这个观点引导到连分数的概念。在17世纪以前，没有特别地研究过它，但是其中的思想根源可以追溯到阿基米德。

阿基米德计算π的方法：逼近和有限性

圆周长和圆的直径的比值是一个常数，而自从18世纪以来就记作π。现在我们来看一看阿基米德怎样在公元前3世纪就得到了这个比值的经典的近似值22/7。若在圆内作一个内接的正多边形（其顶点都在圆周上），又作其外切的正多边形（其边都是圆周的切线），再计算这些多边形的周长，就会得到x的下界与上界，因为圆的周长必定大于任意内接多边形的周长，而小于任意外切多边形的周长。阿基米德从正六边形开始，然后，每次把多边形的边数加倍，得到了越来越精确的上下界。他做到九十六边形为止，得到了

• π的逼近

这个过程中显然涉及迭代。但是称它为一个算法对不对？严格地说，它不是一个算法，不论取多少边的多边形，所得到的仅是 π 的近似值，所以这个过程不是有限的。然而我们确实得到了一个可以近似计算π到任意精确度的算法。例如。如果想得到π的一个准确到小数十位的近似值，经过有限多步以后，这个算法会给出一个我们想要的近似值。重要的是，这个过程是收敛的。就是说，重要的在于由迭代得出之值可以任意地接近于π。这个方法的几何来源可以用来证明这个收敛性，而1609年德国人作到了202边形（基本上用阿基米德的方法），得到π的精确到小数35位的近似值。

然而，逼近π的算法与阿基米德计算两个正整数的 gcd 的算法有一个明显的区别。如欧几里得那样的算法时常称为离散算法，而与用来计算非整数值的数值算法相对立。

牛顿-拉夫森方法：递推公式

1670年前后、牛顿提出了一个求方程之根的方法，而且就方程x^3-2x-5=0解释了他的方法。他的解释从下面的一个观察开始：根x近似地等于2。于是他写出x=2+p，并用2＋p代替原方程的x，而得到了一个关于p的方程。这个新方程算出来是

因为x接近于2，所以p很小，而他就略去了p^3和 6p^2来估计p。这就给了他p的方程10p-1=0，即p=1/10。这当然不是一个准确解，但是，给了牛顿关于根的新的更好的近似值：x=2.1。然后牛顿就重复这个过程，令x=2.1＋q，代入原方程以后又给出了一个关于q的方程，近似地解这个方程，又把他的近似解精确化了，于是得到q的估计为-0.0054，所以x的下一个近似值是2.0946。

尽管如此，我们怎么能确定这个过程会收敛于x呢？让我们更仔细地考察这个方法。

切线和收敛性

牛顿的方法可以从几何上用函数f的图像来解释，虽然牛顿本人并没有这样做。f（x）=0的每一个根x都对应于函数y=f（x）的曲线和x轴的一个交点。如果从根 x的一个近似值 a 开始，而且和上面做的一样，设 p=x- a，于是可以用a+p代替x而得到一个新的函数g（p），也就是说把原点（0，0）有效地移到了（a，0）处。然后把p的所有高次幂都略去，只留下常数项和线性项，这样就得到了函数 g 的最佳的线性逼近——从几何上说，这就是g在点（0，g（0））处的切线。

这样，对于p所得到的近似值就是函数y在点（0，g（0））处的切线与x轴的交点。再在横坐标上加一个 a，也就是让原点回到原来的（0，0）处，这样 a＋p就给出了f 的根的新近似值。这就是牛顿的方法称为切线法的原因。

• 牛顿方法

从上图可以看到，再作一次切线的逼近，如果曲线y=f（x）与x轴的交点在a点以及f在点（a，f（a））处的切线与x轴的交点（即上图中的横坐标为a+p的点，即根的近似值）之间，则第二次的近似值（即a＋p＋q）肯定比第一次的近似值a＋p好（这里称a 为根的零次近似）。

回到牛顿的例子，可以看到牛顿选取 a=2并不是上面所说的情况。但是从下一个近似值2.1开始，以下所有的近似值就都是这个情况了。从几何上看，如果点（a，f（a））位于x轴的上方，而且y=f（x）的曲线在凸部与x轴相交，或者点（a，f（a））在x轴的下方，而且y=f（x）曲线在凹部与x轴相交，就会出现这种有利的情况。

初始的逼近（即零次近似）的选择显然是很重要的，而且提出了微妙的未曾想到的问题。如果我们考虑复多项式的复根，这就更加清楚了。牛顿的方法很容易适应这个更广泛的背景。设z是一个复多项式的复根，而z_0是初始的逼近，于是牛顿方法将给出一个序列 z_0，z_1，z_2……它可能收敛于 z，也可能不收敛。我们定义根z的吸引区域为这样的初始逼近z_0的集合，使得所得到的序列确实收敛于z，并且记这个区域为A（z）。怎样来决定A（z）呢？

第一个问这个问题的人是凯莱，时间是1879年。他注意到，对于二次多项式，这个问题是很容易的，但当次数为3或者更大时，问题就很困难了。例如多项式z^2-1的根±1的吸引区域分别是复平面上以铅直轴为界的两个半平面，但是z^3-1的三个根1，w，w^2的相应的吸引区域就是极复杂的集合。这些集合是由儒利亚在1918年描述的，而现在称为分形集合。

递推公式

牛顿方法的每一阶段都会产生一个新方程。但是拉夫森指出实际上并无必要。他就特殊的例子给出在每一步都可以使用的单一一个公式。但是他的基本的观察可以一般地适用，导出可以用于每一个情况的一般公式，而这个公式用切线的解释就可以容易得出。事实上，曲线y=f（x）在x坐标为a处的切线方程是

它与x轴的交点的横坐标是a-f（a）/f'（a）。我们现在所说的牛顿-拉夫森方法就是指的这个公式。我们从一个初始逼近 a_0=a开始再用这个递推公式得出

这样就得到一个逼近的序列，在复情况下，也就是前面说的 z_0，z_1，z_2，…。

作为一个例子，考虑函数f（x）=x^2-c。这时，牛顿方法就给出c的平方根根号c 的一串近似值，递推公式现在成了

在上面的一般公式中把f 换成x^2-c即得。这个近似平方根的求法，公元1世纪的亚历山大里亚的海伦就已经知道。