對于“算法”一詞給以精确的定義不是一件容易事，有一些意義相近的同義語，就是一些其他的名詞，它們（有時）會給出差不多同樣的東西，例如"法則""技巧”“程序”還有“方法”等等都是這種同義語。也可以給出一些例子，如長乘法，就是小學生學的把兩個正整數相乘的豎式乘法。然而，雖然非形式的解釋和恰當的例子對于什麼是算法給出了很好的感覺，但算法一詞中所深藏的思想卻經曆了一個很長的演化曆程，直得到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_1r>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世紀的亞曆山大裡亞的海倫就已經知道。