第1章　緒論

有兩種思想，就像擺放在天鵝絨上的寶石那樣熠熠生輝，一個是微積分，另一個就是算法。微積分以及在微積分基礎上建立起來的數(shù)學分析體系造就了現(xiàn)代科學，而算法則造就了現(xiàn)代世界。

——大衛(wèi)·柏林斯基

為什么要學習算法？如果你想成為一名計算機專業(yè)人士，無論從理論還是從實踐的角度，學習算法都是必需的。從實踐的角度來看，我們必須了解計算領域中不同問題的一系列標準算法。此外，我們還要具備設計新算法和分析其效率的能力。從理論的角度來看，對算法的研究（有時稱為“算法學”，英文為algorithmics）已經(jīng)被公認為是計算機科學的基石。大衛(wèi)·哈雷爾（David Harel）寫了一本非常好的書，他直截了當?shù)貙⑵涿麨椤端惴▽W——計算精髓》（Algorithmics: the Spirit of Computing）。書中是這樣闡述這個問題的：

算法不只是計算機科學的一個分支。它是計算機科學的核心。而且，可以毫不夸張地說，它與絕大多數(shù)科學、商業(yè)和技術都密切相關。（[Har92]，p. 6）

即使不是計算機相關專業(yè)的學生，學習算法的理由也是非常充分的。坦率地說，沒有算法，就沒有計算機程序。而且，隨著計算機日益滲透到我們日常工作和生活的方方面面，需要學習算法的人也越來越多。

學習算法的另一個理由是可以用它來培養(yǎng)人們的分析能力。畢竟，算法可以看作解決問題的一類特殊方法——它雖然不是問題的答案，但它是經(jīng)過準確定義以獲得答案的過程。因此，無論是否涉及計算機，特定的算法設計技術都能看作問題求解的有效策略。當然，算法思想天生固有的精確性限制了它能夠解決的問題種類。例如，我們找不到一種使人幸福快樂的算法，也找不到一種使人功成名就的算法。但另一方面，從教育角度來看，這種必要的精確性卻是很重要的。唐納德·克努特（Donald Knuth），算法學歷史上最卓越的計算機科學家之一，是這樣論述這個問題的：

受過良好訓練的計算機科學家知道怎樣處理算法：如何構造算法、操作算法、理解算法以及分析算法。這些知識遠不止為了寫出良好的計算機程序而準備的。算法是一種一般性的智能工具，它必定有助于我們對其他學科的理解，不管是化學、語言學或音樂，還是其他學科。為什么算法會有這種作用呢？我們可以這樣理解：人們常說，一個人只有把知識教給別人，才能真正掌握它。實際上，一個人只有把知識教給“計算機”，才能“真正”掌握它，也就是說，將知識表述為一種算法……比起簡單按照常規(guī)去理解事物，嘗試用算法將其形式化能使我們的理解更加深刻。（[Knu96]，p. 9）

我們從1.1節(jié)開始涉及算法的概念。作為例子，我們將針對同一問題（求最大公約數(shù)）使用三種不同的算法。這樣做有幾個理由。首先，這是大家在中學時代就非常熟悉的問題。其次，它揭示了一種重要的觀點：同樣的問題往往能用多種算法來解決。這三種算法之所以具有典型意義，是因為它們的解題思路不同，復雜程度不同，解題效率也各不相同。再次，我希望將其中一種算法作為本書最先介紹的算法，這不僅因為它歷史悠久（早在兩千多年前它就出現(xiàn)在了歐幾里得的著作中），還因為它不朽的力量和重要性。最后，對這三種算法的研究，能使我們從總體上觀察一種算法通常具有的若干重要特性。

1.2節(jié)講述算法解題的分析和計算問題。我們將討論有關算法設計和分析的一些重要內容。內容涉及算法解題的不同方面，包括問題的分析、如何正確表述算法以及算法的效率分析。這一節(jié)不能傳授秘方為任意問題設計算法。這是一個公認的事實，即這種秘方是不存在的。但當大家日后進行自己的算法設計和分析工作時，肯定會用到1.2節(jié)的內容。

1.3節(jié)專門討論幾種重要的問題類型。經(jīng)驗證明，無論對于算法教學還是對于算法應用，這些問題類型都是極其重要的。實際上，有些教材（例如[Sed88]）就是圍繞這些問題類型來組織內容的。盡管包括我在內的許多人都認為圍繞算法設計技術來組織內容更有優(yōu)勢，但無論如何，了解這些重要的問題類型都是十分必要的。一是因為這些類型是實際應用中最常見的，二是由于本書從頭到尾都會用它們來演示一些特殊的算法設計技術。

1.4節(jié)回顧基本的數(shù)據(jù)結構。安排這一節(jié)的目的與其說是為了討論這方面的內容，還不如說是希望把它作為讀者的參考材料。如果需要了解更詳細的內容，可以參考很多關于該主題的優(yōu)秀書籍，其中大多數(shù)都是和某一種編程語言相關的。