在計(jì)算機(jī)出現(xiàn)之前，就有了算法。現(xiàn)在有了計(jì)算機(jī)，就需要更多的算法，算法是計(jì)算的核心。
　　本書提供了對(duì)當(dāng)代計(jì)算機(jī)算法研究的一個(gè)全面、綜合的介紹。書中給出了多個(gè)算法，并對(duì)它們進(jìn)行了較為深入的分析，使得這些算法的設(shè)計(jì)和分析易于被各個(gè)層次的讀者所理解。我們力求在不犧牲分析的深度和數(shù)學(xué)嚴(yán)密性的前提下，給出深入淺出的說(shuō)明。
　　書中每一章都給出了一個(gè)算法、一種算法設(shè)計(jì)技術(shù)、一個(gè)應(yīng)用領(lǐng)域或一個(gè)相關(guān)的主題。算法是用英語(yǔ)和一種“偽代碼”來(lái)描述的，任何有一點(diǎn)程序設(shè)計(jì)經(jīng)驗(yàn)的人都能看得懂。書中給出了244幅圖，說(shuō)明各個(gè)算法的工作過(guò)程。我們強(qiáng)調(diào)將算法的效率作為一種設(shè)計(jì)標(biāo)準(zhǔn)，對(duì)書中的所有算法，都給出了關(guān)于其運(yùn)行時(shí)間的詳細(xì)分析。
　　本書主要供本科生和研究生的算法或數(shù)據(jù)結(jié)構(gòu)課程使用。因?yàn)闀�中討論了算法設(shè)計(jì)中的工程問(wèn)題及其數(shù)學(xué)性質(zhì)，所以，本書也可以供專業(yè)技術(shù)人員自學(xué)之用。
　　本書是第3版。在這個(gè)版本里，我們對(duì)全書進(jìn)行了更新，包括新增了若干章、修訂了偽代碼等。
　　致使用本書的教師
　　本書的設(shè)計(jì)目標(biāo)是全面、適用于多種用途。它可用于若干課程，從本科生的數(shù)據(jù)結(jié)構(gòu)課程到研究生的算法課程。由于書中給出的內(nèi)容比較多，只講一學(xué)期一般講不完，因此，教師們應(yīng)該將本書看成是一種“緩存區(qū)”或“瑞典式自助餐”，從中挑選出能最好地支持自己希望教授的課程的內(nèi)容。
　　教師們會(huì)發(fā)現(xiàn)，要圍繞自己所需的各個(gè)章節(jié)來(lái)組織課程是比較容易的。書中的各章都是相對(duì)獨(dú)立的，因此，你不必?fù)?dān)心意想不到的或不必要的各章之間的依賴關(guān)系。每一章都是以節(jié)為單位，內(nèi)容由易到難。如果將本書用于本科生的課程，可以選用每一章的前面幾節(jié)內(nèi)容；用于研究生的課程中，則可以完整地講授每一章。
　　全書包含957道練習(xí)和158道思考題。每一節(jié)結(jié)束時(shí)給出練習(xí)，每一章結(jié)束時(shí)給出思考題。練習(xí)一般比較短，用于檢查學(xué)生對(duì)書中內(nèi)容的基本掌握情況。有一些是簡(jiǎn)單的自查性練習(xí)，有一些則要更充實(shí)，可以作為家庭作業(yè)布置給學(xué)生。每一章后的思考題都是一些敘述較為詳細(xì)的實(shí)例研究，它們常常會(huì)介紹一些新的知識(shí)。一般來(lái)說(shuō)，這些思考題都會(huì)包含幾個(gè)小問(wèn)題，引導(dǎo)學(xué)生逐步得到問(wèn)題的解。
　　鑒于本書前幾版使用的反饋，我們?cè)诒緯�配套網(wǎng)站上公布了其中一些練習(xí)和思考題的答案（但不是全部）。我們會(huì)定期更新這些答案，因此需要教師每次授課前都到這個(gè)網(wǎng)站上來(lái)查看。
　　在那些不太適合本科生、更適合研究生的章節(jié)和練習(xí)前面，都加上了星號(hào)（?）。帶星號(hào)的章節(jié)也不一定就比不帶星號(hào)的更難，但可能要求了解更多的數(shù)學(xué)知識(shí)。類似地，帶星號(hào)的練習(xí)可能要求有更好的數(shù)學(xué)背景或創(chuàng)造力。
　　致使用本書的學(xué)生
　　希望本教材能為學(xué)生們提供關(guān)于算法這一領(lǐng)域的有趣介紹。我們力求使書中給出的每一個(gè)算法都易于理解和有趣。為了在同學(xué)們遇到不熟悉或比較困難的算法時(shí)提供幫助，我們逐個(gè)步驟地描述每一個(gè)算法。此外，為了便于大家理解書中對(duì)算法的分析，對(duì)于其中所需的數(shù)學(xué)知識(shí)，我們給出了詳細(xì)的解釋。如果對(duì)某一主題已經(jīng)有所了解，會(huì)發(fā)現(xiàn)根據(jù)書中各章的編排順序，可以跳過(guò)一些介紹性的小節(jié)，直接閱讀更高級(jí)的內(nèi)容。
　　本書是一本大部頭著作，讀者所修的課程可能只講授其中的一部分。我們?cè)噲D使它能成為一本現(xiàn)在對(duì)讀者有用的教材，將來(lái)在讀者的職業(yè)生涯中，也能成為一本案頭的數(shù)學(xué)參考書或工程實(shí)踐手冊(cè)。
　　閱讀本書需要哪些預(yù)備知識(shí)呢·
　　讀者需要有一些程序設(shè)計(jì)方面的經(jīng)驗(yàn)，尤其需要理解遞歸過(guò)程和簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，如數(shù)組和鏈表。
　　讀者應(yīng)該能較為熟練地利用數(shù)學(xué)歸納法進(jìn)行證明。書中有一些內(nèi)容要求讀者具備初等微積分方面的知識(shí)。除此之外，本書的第一部分和第八部分將介紹讀者需要用到的所有數(shù)學(xué)技巧。
　　我們收到讀者的反饋，他們強(qiáng)烈希望提供練習(xí)和思考題的答案，為此，我們?cè)谡旧辖o出了少數(shù)練習(xí)和思考題的答案，讀者可以根據(jù)我們的答案來(lái)檢驗(yàn)自己的解答。
　　致使用本書的專業(yè)技術(shù)人員
　　本書涉及的主題非常廣泛，因而是一本很好的算法參考手冊(cè)。因?yàn)槊恳徽露际窍鄬?duì)獨(dú)立的，所以讀者可以重點(diǎn)查閱自己感興趣的主題。
　　在我們所討論的算法中，多數(shù)都有著極大的實(shí)用價(jià)值。因此，我們?cè)跁�中涉及了算法�?shí)現(xiàn)方面的考慮和其他工程方面的問(wèn)題。對(duì)于那些為數(shù)不多的、主要具有理論研究?jī)r(jià)值的算法，通常還給出其實(shí)用的替代算法。
　　如果希望實(shí)現(xiàn)這些算法中的任何一個(gè)，你會(huì)發(fā)現(xiàn)將書中的偽代碼翻譯成你熟悉的某種程序設(shè)計(jì)語(yǔ)言是一件相當(dāng)直接的事。偽代碼被設(shè)計(jì)成能夠清晰、簡(jiǎn)明地描述每一個(gè)算法。因此，我們不考慮錯(cuò)誤處理和其他需要對(duì)讀者所用編程環(huán)境有特定假設(shè)的軟件工程問(wèn)題。我們力求簡(jiǎn)單而直接地給出每一個(gè)算法，而不會(huì)讓某種特定程序設(shè)計(jì)語(yǔ)言的特殊性掩蓋算法的本質(zhì)內(nèi)容。
　　如果你是在課堂外使用本書，那么可能無(wú)法從教師那里得到答案來(lái)驗(yàn)證自己的解答，因此，我們?cè)诰W(wǎng)站上給出了部分練習(xí)和思考題的答案，讀者可以免費(fèi)下載參考。
　　致我們的同事
　　我們?cè)诒緯�中給出了詳盡的參考文獻(xiàn)。每一章在結(jié)束時(shí)都給出了“本章注記”，介紹一些歷史性的細(xì)節(jié)和參考文獻(xiàn)。但是，各章的注記并沒(méi)有提供整個(gè)算法領(lǐng)域的全部參考文獻(xiàn)。有一點(diǎn)可能是讓人難以置信的，就是在本書這樣一本大部頭中，由于篇幅的原因，很多有趣的算法都沒(méi)能包括進(jìn)來(lái)。
　　盡管學(xué)生們發(fā)來(lái)了大量的請(qǐng)求，希望我們提供思考題和練習(xí)的解答，但我們還是決定基本上不提供思考題和練習(xí)的參考答案（少數(shù)除外），以打消學(xué)生們?cè)噲D查閱答案，而不是自己動(dòng)手得出答案的念頭。
　　第3版中所做的修改
　　在本書的第2版和第3版之間有哪些變化呢·這兩版之間的變化量和第2版與第1版之間的變化量相當(dāng)，正如在第2版的變化中所說(shuō)，這些變化可以說(shuō)不太大，也可以說(shuō)很大，具體要看讀者怎么看待這些變化了。
　　快速地瀏覽一遍目錄，你就會(huì)發(fā)現(xiàn)，第2版中的多數(shù)章節(jié)在第3版中都出現(xiàn)了。在第3版中，去掉了兩章和一節(jié)的內(nèi)容，新增加了三章以及兩節(jié)的內(nèi)容。如果單從目錄來(lái)判斷第3版中改動(dòng)的范圍，得出的結(jié)論很可能是改動(dòng)不大。
　　我們依然保持前兩版的組織結(jié)構(gòu)，既按照問(wèn)題領(lǐng)域又根據(jù)技術(shù)來(lái)組織章節(jié)內(nèi)容。書中既包含基于技術(shù)的章，如分治法、動(dòng)態(tài)規(guī)劃、貪心算法、攤還分析、NP完全性和近似算法，也包含關(guān)于排序、動(dòng)態(tài)集的數(shù)據(jù)結(jié)構(gòu)和圖問(wèn)題算法的完整部分。我們發(fā)現(xiàn)雖然讀者需要了解如何應(yīng)用這些技術(shù)來(lái)設(shè)計(jì)和分析算法，但是思考題中很少提示應(yīng)用哪個(gè)技術(shù)來(lái)解決這些問(wèn)題。
　　下面總結(jié)了第3版的主要變化：
　　新增了討論van Emde Boas樹和多線程算法的章節(jié)，并且將矩陣基礎(chǔ)移至附錄。
　　修訂了遞歸式那一章的內(nèi)容，更廣泛地覆蓋分治法，并且前兩節(jié)介紹了應(yīng)用分治法解決兩個(gè)問(wèn)題。4.2節(jié)介紹了用于矩陣乘法的Strassen算法，關(guān)于矩陣運(yùn)算的內(nèi)容已從本章移除。
　　移除兩章很少講授的內(nèi)容：二項(xiàng)堆和排序網(wǎng)絡(luò)。排序網(wǎng)絡(luò)中的關(guān)鍵思想——0-1原理，在本版的思考題8-7中作為比較交換算法的0-1排序引理進(jìn)行介紹。斐波那契堆的處理不再依賴二項(xiàng)堆。
　　修訂了動(dòng)態(tài)規(guī)劃和貪心算法相關(guān)內(nèi)容。與第2版中的裝配線調(diào)度問(wèn)題相比，本版用一個(gè)更有趣的問(wèn)題——鋼條切割來(lái)引入動(dòng)態(tài)規(guī)劃。而且，我們比在第2版中更強(qiáng)調(diào)助記性，并且引入子問(wèn)題圖這一概念來(lái)闡釋動(dòng)態(tài)規(guī)劃算法的運(yùn)行時(shí)間。在我們給出的貪心算法例子（活動(dòng)選擇問(wèn)題）中，我們以更直接的方式給出貪心算法。
　　我們從二叉搜索樹（包括紅黑樹）刪除一個(gè)結(jié)點(diǎn)的方式，現(xiàn)在保證實(shí)際所刪除的結(jié)點(diǎn)就是請(qǐng)求刪除的結(jié)點(diǎn)（在前兩版中，有些情況下某個(gè)其他結(jié)點(diǎn)可能被刪除）。用這種新的方式刪除結(jié)點(diǎn)，如果程序的其他部分保持指針指向樹中的結(jié)點(diǎn)，那么終止時(shí)就不會(huì)錯(cuò)誤地將指針指向已刪去的結(jié)點(diǎn)。
　　流網(wǎng)絡(luò)相關(guān)材料現(xiàn)在基于邊上的全部流。這種方法比前兩版中使用的凈流更直觀。
　　由于關(guān)于矩陣基礎(chǔ)和Strassen算法的材料移到了其他章，矩陣運(yùn)算這一章的內(nèi)容比第2版中所占的篇幅更小。
　　修改了對(duì)Knuth-Morris-Pratt字符串匹配算法的討論。
　　修正了上一版中的一些錯(cuò)誤。在網(wǎng)站上，這些錯(cuò)誤大多數(shù)都已在第2版的勘誤中給出，但是有些沒(méi)有給出。
　　根據(jù)許多讀者的要求，我們改變了書中偽代碼的語(yǔ)法，現(xiàn)在用“=”表示賦值，用“==”表示檢驗(yàn)相等，正如C、C++、Java和Python所用的。同樣，我們不再使用關(guān)鍵字do和then而是使用“//”作為程序行末尾的注釋符號(hào)。我們現(xiàn)在還使用點(diǎn)標(biāo)記法表明對(duì)象屬性。書中的偽代碼仍是過(guò)程化的，而不是面向?qū)ο蟮�。換句話說(shuō)，我們只是簡(jiǎn)單地調(diào)用過(guò)程，將對(duì)象作為參數(shù)傳遞，而不是關(guān)于對(duì)象的運(yùn)行方法。
　　新增100道練習(xí)和28道思考題，還更新并補(bǔ)充了參考文獻(xiàn)。
　　最后，我們對(duì)書中的語(yǔ)句、段落和小節(jié)進(jìn)行了一些調(diào)整，以使本書條理更清晰。
　　網(wǎng)站
　　讀者可以通過(guò)網(wǎng)站來(lái)獲取補(bǔ)充資料，以及與我們聯(lián)系。這個(gè)網(wǎng)站上給出了已知錯(cuò)誤的清單、部分練習(xí)和思考題的答案等。此外，網(wǎng)站上還告訴讀者如何報(bào)告錯(cuò)誤或者提出建議。
　　第3版致謝
　　我們已經(jīng)與MIT Press合作20多年，建立了很好的合作關(guān)系！感謝Ellen Faran、Bob Prior、Ada Brunstein和Mary Reilly的幫助和支持。
　　在出版第3版時(shí)，我們?cè)谶_(dá)特茅斯學(xué)院計(jì)算機(jī)科學(xué)系、MIT計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室、哥倫比亞大學(xué)工業(yè)工程與運(yùn)籌學(xué)系從事教學(xué)和科研工作。感謝這些學(xué)校和同事為我們提供的支持和實(shí)驗(yàn)環(huán)境。
　　Julie Sussman，P.P.A擔(dān)當(dāng)本書第3版的技術(shù)編輯，再次拯救了我們。每次審閱，我們都覺(jué)得已經(jīng)消除了錯(cuò)誤，但是Julie還是發(fā)現(xiàn)了許多錯(cuò)誤。她還幫我們改進(jìn)了幾處文字表述。如果有技術(shù)編輯名人堂，Julie一定第一輪就可以入選。Julie是非凡的，我們?cè)趺锤兄x都是不夠的。Priya Natarajan也發(fā)現(xiàn)了一些錯(cuò)誤，使得我們可以在將本書交給出版社前修正這些錯(cuò)誤。書中的任何錯(cuò)誤（毫無(wú)疑問(wèn)，一定存在一些錯(cuò)誤）都由作者負(fù)責(zé)（或許這些錯(cuò)誤有些是Julie審閱材料后引入的）。
　　對(duì)于van Emde Boas樹的處理出自于Erik Demaine的筆記，轉(zhuǎn)而也受到Michael Bender的影響。此外，我還將Javed Aslam、Bradley Kuszmaul和Hui Zha的思想也整合到這一版。
　　多線程算法這一章是基于與Harald Prokop一起撰寫的筆記，其他在MIT從事Cilk項(xiàng)目的同事也對(duì)本部分內(nèi)容有所貢獻(xiàn)，包括Bradley Kuszmaul和Matteo Frigo。多線程偽代碼的設(shè)計(jì)靈感來(lái)自MIT Cilk擴(kuò)展到C，以及由Cilk Arts的Cilk++擴(kuò)展到C++。
　　我們還要感謝許多第1版和第2版的讀者，他們報(bào)告了所發(fā)現(xiàn)的錯(cuò)誤，或者提出了改進(jìn)本書的建議。我們修正了全部報(bào)告來(lái)的真實(shí)錯(cuò)誤，并且盡可能多地采納了讀者的建議。我們很高興有這么多的人為本書做出貢獻(xiàn)，但是很遺憾我們無(wú)法全部列出這些貢獻(xiàn)者。
　　最后，非常感謝我們各自的妻子Nicole Cormen、Wendy Leiserson、Gail Rivest和Rebecca Ivry，還有我們的孩子Ricky、Will、Debby和Katie Leiserson，Alex和Christopher Rivest，以及Molly、Noah和Benjamin Stein。感謝他們?cè)谖覀儗懽鞅緯�過(guò)程中給予的愛(ài)和支持。正是由于有了來(lái)自家庭的耐心和鼓勵(lì)，本書的寫作工作才得以完成。謹(jǐn)將此書獻(xiàn)給他們。
　　Thomas H.Cormen，新罕布什爾州黎巴嫩市
　　Charles E.Leiserson，馬薩諸塞州劍橋市
　　Ronald L.Rivest，馬薩諸塞州劍橋市
　　Clifford Stein，紐約州紐約市
　　譯者序
　　我從1994年開始每年都為本科生講授《算法設(shè)計(jì)與分析》課程，粗略地統(tǒng)計(jì)一下發(fā)現(xiàn)至今已有5000余名各類學(xué)生聽過(guò)該課。算法的重要性不言而喻，因?yàn)椴还苄赂拍�、新方法、新理論如何引人注目，信息的表示與處理總是計(jì)算技術(shù)（含軟件、硬件、應(yīng)用、網(wǎng)絡(luò)、安全、智能等）永恒的主題。信息處理的核心是算法，在大數(shù)據(jù)時(shí)代，設(shè)計(jì)高效的算法顯得格外重要。
　　當(dāng)初，為了教好這門基礎(chǔ)必修課，提高教學(xué)質(zhì)量，我覺(jué)得應(yīng)該從教學(xué)內(nèi)容的改革入手，具體來(lái)說(shuō)，采用的教材應(yīng)該與國(guó)際一流大學(xué)接軌。1997年訪美期間，在Stanford大學(xué)了解到他們采用的教材是Thomas H. Cormen等編著的《Introduction to Algorithms》，于是從Stanford書店買了一本帶回來(lái)，從第二年開始便改用該書作教材。至今，15年過(guò)去了，我們一直追隨其變遷，從第二版到第三版。教學(xué)實(shí)踐證明它確實(shí)是一本好教材，難怪世界范圍內(nèi)包括MIT、CMU、Stanford、UCB、Cornell、UIUC等國(guó)際國(guó)內(nèi)名校在內(nèi)的1000余所大學(xué)都一直用它作為教材或教學(xué)參考書，也難怪它印數(shù)巨大且在《高引用計(jì)算機(jī)科學(xué)文獻(xiàn)》（《Most Cited Computer Science Citations》）一覽表中名列前茅。
　　這是一本有1200多頁(yè)的厚書，教學(xué)內(nèi)容非常豐富，不但涵蓋了典型算法、算法分析、算法設(shè)計(jì)方法和NP完全等內(nèi)容，而且還包括數(shù)據(jù)結(jié)構(gòu)，甚至高級(jí)數(shù)據(jù)結(jié)構(gòu)的介紹。后者可作為國(guó)內(nèi)《數(shù)據(jù)結(jié)構(gòu)》課程的教材或教學(xué)參考資料。在學(xué)時(shí)有限的情況下，要在本科階段教完前者的所有內(nèi)容也是困難的，故要做取舍。好在該書的各個(gè)章節(jié)相對(duì)獨(dú)立且難度由淺入深，我們的做法是將相對(duì)容易的一般的入門性內(nèi)容留在本科階段，而將相對(duì)難的專門的較深入的內(nèi)容并入研究生課程《算法及復(fù)雜性》或《計(jì)算復(fù)雜性》。除本校外，本人就曾多次應(yīng)邀在蘭州大學(xué)、湖南大學(xué)和浙江師范大學(xué)等院校為研究生講授過(guò)這些內(nèi)容。其實(shí)該書也適合希望增強(qiáng)自身程序設(shè)計(jì)能力和程序評(píng)判能力的廣大應(yīng)用計(jì)算技術(shù)的社會(huì)公眾，特別是參加信息學(xué)奧林匹克競(jìng)賽和ACM程序設(shè)計(jì)競(jìng)賽的選手及其教練員。
　　教學(xué)過(guò)程中我們發(fā)現(xiàn)該書具有以下特點(diǎn)：（1）選材與時(shí)俱進(jìn)，具有實(shí)用性且能引起讀者的興趣。該書中研究的許多問(wèn)題都是當(dāng)前現(xiàn)實(shí)應(yīng)用中的關(guān)鍵技術(shù)問(wèn)題。（2）采用偽碼描述算法，既簡(jiǎn)潔易懂又便于抓住本質(zhì)，再配上豐富的插圖來(lái)描述和解釋算法的執(zhí)行過(guò)程使得教學(xué)內(nèi)容更加通俗，便于自學(xué)。（3）對(duì)算法正確性和復(fù)雜性的分析比較全面，既有嚴(yán)密的論證，又有直觀的解釋。（4）既有結(jié)論性知識(shí)的介紹，也有逐步導(dǎo)出結(jié)論的研究過(guò)程的展示。（5）豐富的練習(xí)題和思考題使得及時(shí)檢驗(yàn)所學(xué)知識(shí)掌握情況和進(jìn)一步拓展學(xué)習(xí)內(nèi)容成為可能。
　　同時(shí)，我們也注意到：學(xué)生們總是反映看英文版教材速度太慢，所以他們總是想方設(shè)法再找一本中譯版來(lái)閱讀。正是這樣的背景，在第三版的《Introduction to Algorithms》出版后，我們應(yīng)機(jī)械工業(yè)出版社編輯的邀請(qǐng)，啟動(dòng)了長(zhǎng)久的翻譯工程，先后參加翻譯工作的老師有：國(guó)防科學(xué)技術(shù)大學(xué)的殷建平教授（翻譯第1~3章）、中國(guó)科學(xué)技術(shù)大學(xué)的徐云教授（翻譯第10~14章、第18~21章和第27章）、南開大學(xué)的王剛教授（翻譯第4章和第15~17章）、南開大學(xué)的劉曉光教授（翻譯第6~9章）、南開大學(xué)的蘇明副研究員（翻譯第5章和第28~30章）、上海交通大學(xué)的鄒恒明教授（翻譯第22~26章）、哈爾濱工業(yè)大學(xué)的王宏志副教授（翻譯第31~35章和附錄部分）。由于水平有限且工作量巨大，譯文中一定存在許多不足，在此敬請(qǐng)各位同行專家學(xué)者和廣大讀者批評(píng)指正，歡迎大家將發(fā)現(xiàn)的錯(cuò)誤或提出的意見與建議發(fā)送到郵箱。在整個(gè)工程即將完成之際，我們特別要感謝機(jī)械工業(yè)出版社的溫莉芳老師和王春華老師，沒(méi)有你們的信任、耐心和支持整個(gè)翻譯工作不可能完成。
　　殷建平
　　2012年11月于長(zhǎng)沙