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