一個人在接受科技教育時，最有價值的收獲是能使其終身受益的通用智能工具。
喬治福賽斯
（譯注：原文為The most valuable acquisitions in a scientific or technical education are the general-purpose mental tools which remain serviceable for a life-time，出自1968年發(fā)表的What to do till the computer scientist comes。福賽斯(George Forsythe，19171972)1939年在布朗大學獲得博士學位，二戰(zhàn)后供職于斯坦福大學數(shù)學系，后來在該校創(chuàng)辦計算機系。他先后培養(yǎng)的博士生超過190名。他與MATLAB之父莫勒合著的《線性代數(shù)系統(tǒng)的計算機求解》出版于1967年。）

算法在計算科學和計算實踐中發(fā)揮著核心作用。基于這樣的認知，涌現(xiàn)出大量相關的著述，尤其是教材。它們在介紹算法時基本上選擇遵循兩種方案。一種是根據(jù)問題類型對算法進行分類。這樣的書用單獨的章節(jié)介紹排序、查找以及圖等算法。這種方案的優(yōu)點在于，能立即對比同一問題場景下不同算法的效率。缺點在于，它強調(diào)的是問題類型，忽略了算法設計技術。
第二種方案是圍繞算法設計技術進行組織。采用這種組織方式，如果來自不同計算領域的算法采用的是相同的設計方法，就把它們歸為一組。我和許多人一樣(例如[BaY95])，認為這種組織方式更適合算法設計與分析基礎課程。強調(diào)算法設計技術主要有三個原因。第一，這些技術為學生提供了工具來為新的問題設計算法。這使學習算法設計技術具有實踐意義上的價值。第二，它們根據(jù)基本的設計理念來對眾多已知的算法進行分類。尋找不同應用領域的算法之間的共性，這應該是計算機科學教育的一個主要目標。畢竟，每一門學科都將其主要課題的分類視為其學科的要點甚至是中心點。第三，在我看來，算法設計技術作為一般的問題解決策略具有實用性，適用于計算以外的問題。
遺憾的是，無論從理論還是教育的角度，算法設計技術的傳統(tǒng)分類法都有幾個重大的缺陷。最重要的是沒有對許多重要的算法進行分類。這一不足迫使其他教科書的作者背離設計技術的組織形式，在書中加入相應的章節(jié)來處理具體的問題類型。這樣的轉(zhuǎn)換導致算法課程喪失連貫性，注定會導致學生覺得亂。
算法設計技術的新分類法
傳統(tǒng)算法設計技術分類法的缺陷讓人感到失望，所以我開發(fā)了一套新的分類法[Lev99]，這也是本書的基礎。新的分類法主要有下面幾個優(yōu)點。
新的分類法比傳統(tǒng)分類法更全面。新加入的蠻力法、減治法、變治法、時空權衡和迭代改進等策略很少(甚至從未)被認為是重要的設計范式(design paradigm)。
新的分類法自然涵蓋傳統(tǒng)分類法無法歸類的許多經(jīng)典算法(歐幾里得算法、堆排序、查找樹、散列法、拓撲排序、高斯消去法和霍納規(guī)則等)，所以，新的分類法使我們能以統(tǒng)一和連貫的方式呈現(xiàn)經(jīng)典算法的標準體系。
它自然適應幾種設計技術的重要變化形式。例如，它能夠涵蓋減治法的三個變種和變治法的三個變種。
進行效率分析時，新的分類法與分析方法更適合(參見附錄B)。
設計技術作為問題求解的一般性策略
本書主要是將算法設計技術應用于計算機科學的經(jīng)典問題。唯一的創(chuàng)新是加入了一些關于數(shù)值算法的內(nèi)容，這些內(nèi)容涵蓋在同一個通用框架內(nèi)。但是，這些設計技術可以用作通用問題求解工具，其應用并不限于傳統(tǒng)的計算和數(shù)學問題。有兩個因素使這一點顯得特別重要。首先，越來越多的計算應用超越了傳統(tǒng)領域，而且有理由相信這種趨勢在未來會進一步加強。其次，培養(yǎng)學生解決問題的能力被認為是大學教育的一個主要目標。在計算機科學課程體系中安排一門算法設計與分析課程是非常合適的，因為它可以教會學生如何應用一些特定的策略來解決問題。
我并不是說要把算法設計與分析課程變成一門常規(guī)性的問題求解課程。但我真心覺得不宜錯過研究算法設計與分析所帶來的獨特機會�；�于此，我在本書中加入了謎題和謎題風格類游戲的應用。雖然在算法教學中使用謎題不是什么新鮮事，但本書力求以系統(tǒng)化的方式通過幾個遠遠高于標準的例子來做到這一點。
如何使用本書
我的目標是寫一本既不泛泛而談但又可供學生獨立閱讀的教材。為了實現(xiàn)這個目標，本書做了如下努力。
根據(jù)喬治福賽斯的觀點(參見之前的引文)，我試圖著重強調(diào)隱藏于算法設計和分析背后的主要思想。在選擇特定的算法來闡述這些思想的時候，我并不傾向于涉及大量的算法，而是選擇那些最能揭示其基本設計技術或分析方法的算法。值得慶幸的是，大多數(shù)經(jīng)典算法都滿足這個要求。
第2章主要分析算法的效率，該章有意區(qū)分了用于分析非遞歸算法的方法和通常用于分析遞歸算法的方法。這一章還花了一些篇幅來介紹算法經(jīng)驗分析和算法可視化。
書中以系統(tǒng)化的方式穿插了一些面向讀者的提問，其中有些問題是我們精心設計的，而且答案緊隨其后，其目的是引起讀者的注意或引發(fā)疑問。其余問題的用意是防止讀者走馬觀花而無法充分理解本書的內(nèi)容。
每章結尾處都會對當前這一章中最重要的概念和結論做一個總結。
本書包含600多道習題。有些習題供大家練習用，另外一些則是想要指出書中正文部分所涉及內(nèi)容的重要意義，或是想要介紹書中沒有涉及的一些算法。有一些習題利用了網(wǎng)上的資源。較難的習題數(shù)量不多，在教參中用一種特殊的記號標注出來(有的學生可能沒有勇氣做那些有難度標注的習題，所以本書沒有為習題標注難度)。謎題類的習題用一種特殊的圖標做標注。
本書全部習題都附有提示。除了編程練習，習題的詳細解法都能在教師資源中找到。請發(fā)送郵件到coo@netease.com，申請教師相關資源(也可聯(lián)系培生的當?shù)劁N售代表，或者訪問www.pearsonhighered.com/irc)。
第3版的變化
第3版有若干變化，其中最重要的變化是介紹減治法和分治法的先后順序。第3版先介紹減治法，后介紹分治法，這樣做可以帶來以下優(yōu)勢。
相比分治法，減治法更簡單。
相比分治法，減治法能解決的問題更多。
新的編排順序便于先介紹插入排序，后介紹合并排序和快速排序。
數(shù)組劃分的概念通過選擇問題引入，這次利用Lomuto算法的單向掃描來實現(xiàn)，而將Hoare劃分方法的雙向掃描留到后文與快速排序一并介紹。
折半查找歸入介紹減常量算法的章節(jié)。
另一個重要變化是重新編排了第8章關于動態(tài)規(guī)劃的內(nèi)容，具體是指導述部分的內(nèi)容是全新的。在前兩版中用計算二項式系數(shù)的例子來引入動態(tài)規(guī)劃這一重要技術，但第3版介紹了三個基礎性示例，效果更好一些；8.1節(jié)的習題是全新的，包括前兩版中沒有涉及的一些流行應用；第8章其他小節(jié)的順序有調(diào)整，以便達到由淺入深、循序漸進的效果。
此外，還有其他一些變化。增加了不少與本書所述算法相關的應用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的范疇，因為我認為這樣更合理。在介紹生成組合對象的算法時，新增了格雷碼算法。對求解最近對問題的分治法有更深入的探討。改進的內(nèi)容包括算法可視化和求解旅行商問題的近似算法，當然參考文獻也有相應的更新。
第3版大約新增70道習題，涉及算法謎題和常見的算法面試題。
先修課程
本書假定讀者已經(jīng)學過離散數(shù)學的標準課程和一門基礎性的編程課程。有了這樣的知識背景，讀者應該能夠掌握本書的內(nèi)容而不會遇到太大的困難。盡管如此，1.4節(jié)、附錄A和附錄B仍然對基本的數(shù)據(jù)結構以及肯定會用到的求和公式與遞推關系進行復習和回顧。只有3個小節(jié)(2.2節(jié)、11.4節(jié)和12.4節(jié))會用到一些簡單的微積分知識，如果讀者缺少必要的微積分知識，完全可以跳過這3個涉及微積分的小節(jié)，這樣做并不妨礙大家對本書其余部分的理解。
課程進度安排
如果打算開設一門基礎課來聚焦于算法設計技術，講解算法設計和分析理論，可以采用本書作為教材。但要想在一個學期內(nèi)完成該課程，本書的內(nèi)容可能就太豐富了。大體上來說，跳過第3章到第12章的部分內(nèi)容不會影響讀者對后面部分的理解。本書的任何一個部分都可以安排學生自學。尤其是2.6節(jié)和2.7節(jié)，它們分別介紹經(jīng)驗分析和算法可視化，這兩個小節(jié)可以結合課后練習一起布置給學生，讓他們課后完成。
以下教學計劃用于一個學期的課程，按照40課時的全日制教學計劃來設計。
課次 主題 小節(jié)
1 課程簡介 1.1～1.3
2，3 分析框架；常用符號O、和 2.1，2.2
4 非遞歸算法的數(shù)學分析 2.3
5，6 遞歸算法的數(shù)學分析 2.4，2.5( 附錄B)
7　 蠻力算法 3.1，3.2( 3.3)
8 窮舉查找 3.4
9 深度優(yōu)先查找和廣度優(yōu)先查找 3.5
10～11 減一算法：插入排序、拓撲排序 4.1，4.2
12 折半查找和其他減常量算法 4.4
13 減變量算法 4.5
14～15 分治法：合并排序、快速排序 5.1～5.2
16 其他分治法示例 5.3、5.4或5.5
17～19 實例化簡：預排序、高斯消去法、平衡查找樹 6.1～6.3
20 改進性能：堆和堆排序或者霍納法則和二進制冪 6.4或6.5
21 問題化簡 6.6
22～24 時空權衡：串匹配、散列法、B樹 7.2～7.4
25～27 動態(tài)規(guī)劃算法 8.1～8.4(選學3節(jié))
28～30 貪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法 9.1～9.4
31～33 迭代改進算法 10.1～10.4(選學3節(jié))
34 下界的參數(shù) 11.1
35 決策樹 11.2
36 P、NP和NP完全問題 11.3
37 數(shù)值算法 11.4( 12.4)
38 回溯法 12.1
39 分支定界法 12.2
40 NP困難問題的近似算法 12.3
致謝
我要向本書的審閱人員表達衷心的感謝，還要感謝本書前面兩個版本的許多讀者，他們提供了許多寶貴的意見和建議來幫助改進和完善本書。本書第3版尤其得益于下列審閱人員：芝加哥洛約拉大學的Andrew Harrington、圣文德大學的David Levine、加州大學河濱分校的Stefano Lombardi、賓州曼斯菲爾德大學的Daniel McKee、弗吉尼亞州立聯(lián)邦大學的Susan Brilliant、菩及海灣大學的David Akers以及兩名匿名評審。
我要感謝培生出版社為本書付出不懈努力的所有工作人員和相關人員。尤其要感謝本書編輯Matt Goldstein、編務助理Chelsea Bell、市場經(jīng)理Yez Alayan和產(chǎn)品總監(jiān)Kayla Smith-Tarbox。我還要感謝Richard Camp為本書審稿，感謝Windfall Software的Paul Anagnostopoulos和Jacqui Scarlott為本書排版并提供項目管理支持，感謝MaryEllen Oliver擔任本書校對。
最后，我要感謝我的兩位家人。相比自己寫書，另一半天天忙著寫書更讓人崩潰，我的妻子Maria包容我多年并任勞任怨地幫助我完成書中400多個公式或插圖以及教師手冊。女兒Miriam是我多年的英語老師，她不但閱讀了本書大部分內(nèi)容，還幫著我為每章找到了恰如其分的名人名言。

阿納尼樂維汀(Anany Levitin)