算法導論（原書第3版）/計算機科學叢書 [Introduction to Algorithms, third edition] pdf epub mobi txt 電子書 下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

[美] Thomas H.Cormen，[美] Charles E.Leiserson，[美] Ronald L.Rivest，[美] Clifford Stein 著，殷建平，徐雲，王剛 等 譯

圖書標籤:

• 算法
• 數據結構
• 計算機科學
• 算法分析
• 設計與分析
• 編程
• 經典教材
• MIT
• 算法導論
• 計算機算法

齣版社： 機械工業齣版社

ISBN：9787111407010

版次：1

商品編碼：11144230

品牌：機工齣版

包裝：平裝

叢書名： 計算機科學叢書

外文名稱：Introduction to Algorithms, third edition

開本：16開

齣版時間：2012-12-01

用紙：膠版紙

頁數：796

正文

産品特色

編輯推薦

　　MIT四大名師聯手鑄就，影響全球韆萬程序員的“算法聖經”！國內外韆餘所高校采用！

相關好書推薦：

更多精彩，點擊進入品牌店查閱>>

內容簡介

　　在有關算法的書中，有一些敘述非常嚴謹，但不夠全麵；另一些涉及瞭大量的題材，但又缺乏嚴謹性。《算法導論（原書第3版）/計算機科學叢書》將嚴謹性和全麵性融為一體，深入討論各類算法，並著力使這些算法的設計和分析能為各個層次的讀者接受。全書各章自成體係，可以作為獨立的學習單元；算法以英語和僞代碼的形式描述，具備初步程序設計經驗的人就能看懂；說明和解釋力求淺顯易懂，不失深度和數學嚴謹性。
　　《算法導論（原書第3版）/計算機科學叢書》全書選材經典、內容豐富、結構閤理、邏輯清晰，對本科生的數據結構課程和研究生的算法課程都是非常實用的教材，在IT專業人員的職業生涯中，《算法導論（原書第3版）/計算機科學叢書》也是一本案頭必備的參考書或工程實踐手冊。
　　第3版的主要變化：
　　·新增瞭van Emde Boas樹和多綫程算法，並且將矩陣基礎移至附錄。
　　·修訂瞭遞歸式（現在稱為“分治策略”）那一章的內容，更廣泛地覆蓋分治法。
　　·移除兩章很少講授的內容：二項堆和排序網絡。
　　·修訂瞭動態規劃和貪心算法相關內容。
　　·流網絡相關材料現在基於邊上的全部流。
　　·由於關於矩陣基礎和Strassen算法的材料移到瞭其他章，矩陣運算這一章的內容所占篇幅更小。
　　·修改瞭對Knuth-Morris-Pratt字符串匹配算法的討論。
　　·新增100道練習和28道思考題，還更新並補充瞭參考文獻。

作者簡介

　　Thomas H. Cormen （托馬斯·科爾曼），達特茅斯學院計算機科學係教授、係主任。目前的研究興趣包括：算法工程、並行計算、具有高延遲的加速計算。他分彆於1993年、1986年獲得麻省理工學院電子工程和計算機科學博士、碩士學位，師從Charles E. Leiserson教授。由於他在計算機教育領域的突齣貢獻，Cormen教授榮獲2009年ACM傑齣教員奬。

　　Charles E. Leiserson（查爾斯·雷瑟爾森），麻省理工學院計算機科學與電氣工程係教授，Margaret MacVicar Faculty Fellow。他目前主持MIT超級計算技術研究組，並是MIT計算機科學和人工智能實驗室計算理論研究組的成員。他的研究興趣集中在並行和分布式計算的理論原理，尤其是與工程現實相關的技術研究。Leiserson教授擁有卡內基·梅隆大學計算機科學博士學位，還是ACM、IEEE和SIAM的會士。

　　Ronald L. Rivest （羅納德·李維斯特），現任麻省理工學院電子工程和計算機科學係安德魯與厄納·維特爾比（Andrew and Erna Viterbi）教授。他是MIT計算機科學和人工智能實驗室的成員，並領導著其中的信息安全和隱私中心。他1977年從斯坦福大學獲得計算機博士學位，主要從事密碼安全、計算機安全算法的研究。他和Adi Shamir和Len Adleman一起發明瞭RSA公鑰算法，這個算法在信息安全中獲得大的突破，這一成果也使他和Shamir、Adleman一起得到2002年ACM圖靈奬。他現在擔任國傢密碼學會的負責人。

　　Clifford Stein（剋利福德·斯坦），哥倫比亞大學計算機科學係和工業工程與運籌學係教授，他還是工業工程與運籌學係的係主任。在加入哥倫比亞大學大學之前，他在達特茅斯學院計算機科學係任教9年。Stein教授擁有MIT碩士和博士學位。他的研究興趣包括：算法的設計與分析，組閤優化、運籌學、網絡算法、調度、算法工程和生物計算。

內頁插圖

精彩書評

　　★“鑒於數據量的爆炸性增長，和計算應用的多樣性，現在比以往更需要有效算法。這本書條理清晰，是一本非常好的算法設計與分析方麵的導論性書籍。每章前半部分介紹瞭講授和學習算法的有效方法，後半部分為更專業的讀者和求知欲強的學生提供瞭更引人入勝的資料來討論這個迷人領域的各種可能性和挑戰。”
　　——Shang-Hua Teng（騰尚華），南加州大學維特比工學院計算機係Seeley G. Mudd 教授

　　★“本書是算法領域的一部經典著作，書中係統、全麵地介紹瞭現代算法：從較快算法和數據結構到用於看似難以解決問題的多項式時間算法；從圖論中的經典算法到用於字符匹配、計算集閤和數論的特殊算法。本書第3版尤其增加瞭兩章專門討論van Emde Boas樹（有用的數據結構之一）和多綫程算法（日益重要的一個主題）。”
　　——Daniel Spielman，耶魯大學計算機科學和應用數學Henry Ford II教授

目錄

齣版者的話
譯者序
前言
第一部分　基礎知識
第1章　算法在計算中的作用
1.1　算法
1.2　作為一種技術的算法
思考題
本章注記
第2章　算法基礎
2.1　插入排序
2.2　分析算法
2.3　設計算法
2.3.1　分治法
2.3.2　分析分治算法
思考題
本章注記
第3章　函數的增長
3.1　漸近記號
3.2　標準記號與常用函數
思考題
本章注記
第4章　分治策略
4.1　最大子數組問題
4.2　矩陣乘法的Strassen算法
4.3　用代入法求解遞歸式
4.4　用遞歸樹方法求解遞歸式
4.5　用主方法求解遞歸式
4.6　證明主定理
4.6.1　對b的冪證明主定理
4.6.2　嚮下取整和嚮上取整
思考題
本章注記
第5章　概率分析和隨機算法
5.1　雇用問題
5.2　指示器隨機變量
5.3　隨機算法
5.4　概率分析和指示器隨機變量的進一步使用
5.4.1　生日悖論
5.4.2　球與箱子
5.4.3　特徵序列
5.4.4　在綫雇用問題
思考題
本章注記

第二部分　排序和順序統計量
第6章　堆排序
6.1　堆
6.2　維護堆的性質
6.3　建堆
6.4　堆排序算法
6.5　優先隊列
思考題
本章注記
第7章　快速排序
7.1　快速排序的描述
7.2　快速排序的性能
7.3　快速排序的隨機化版本
7.4　快速排序分析
7.4.1　最壞情況分析
7.4.2　期望運行時間
思考題
本章注記
第8章　綫性時間排序
8.1　排序算法的下界
8.2　計數排序
8.3　基數排序
8.4　桶排序
思考題
本章注記
第9章　中位數和順序統計量
9.1　最小值和最大值
9.2　期望為綫性時間的選擇算法
9.3　最壞情況為綫性時間的選擇算法
思考題
本章注記

第三部分　數據結構
第10章　基本數據結構
10.1　棧和隊列
10.2　鏈錶
10.3　指針和對象的實現
10.4　有根樹的錶示
思考題
本章注記
第11章　散列錶
11.1　直接尋址錶
11.2　散列錶
11.3　散列函數
11.3.1　除法散列法
11.3.2　乘法散列法
11.3.3　全域散列法
11.4　開放尋址法
11.5　完全散列
思考題
本章注記
第12章　二叉搜索樹
12.1　什麼是二叉搜索樹
12.2　查詢二叉搜索樹
12.3　插入和刪除
12.4　隨機構建二叉搜索樹
思考題
本章注記
第13章　紅黑樹
13.1　紅黑樹的性質
13.2　鏇轉
13.3　插入
13.4　刪除
思考題
本章注記
第14章　數據結構的擴張
14.1　動態順序統計
14.2　如何擴張數據結構
14.3　區間樹
思考題
本章注記

第四部分　高級設計和分析技術
第15章　動態規劃
15.1　鋼條切割
15.2　矩陣鏈乘法
15.3　動態規劃原理
15.4　最長公共子序列
15.5　最優二叉搜索樹
思考題
本章注記
第16章　貪心算法
16.1　活動選擇問題
16.2　貪心算法原理
16.3　赫夫曼編碼
16.4　擬陣和貪心算法
16.5　用擬陣求解任務調度問題
思考題
本章注記
第17章　攤還分析
17.1　聚閤分析
17.2　核算法
17.3　勢能法
17.4　動態錶
17.4.1　錶擴張
17.4.2　錶擴張和收縮
思考題
本章注記

第五部分　高級數據結構
第18章　B樹
18.1　B樹的定義
18.2　B樹上的基本操作
18.3　從B樹中刪除關鍵字
思考題
本章注記
第19章　斐波那契堆
19.1　斐波那契堆結構
19.2　可閤並堆操作
19.3　關鍵字減值和刪除一個結點
19.4　最大度數的界
思考題
本章注記
第20章　van Emde Boas樹
20.1　基本方法
20.2　遞歸結構
20.2.1　原型van Emde Boas結構
20.2.2　原型van Emde Boas結構上的操作
20.3　van Emde Boas樹及其操作
20.3.1　van Emde Boas樹
20.3.2　van Emde Boas樹的操作
思考題
本章注記
第21章　用於不相交集閤的數據結構
21.1　不相交集閤的操作
21.2　不相交集閤的鏈錶錶示
21.3　不相交集閤森林
*21.4　帶路徑壓縮的按秩閤並的分析
思考題
本章注記

第六部分　圖算法
第22章　基本的圖算法
22.1　圖的錶示
22.2　廣度優先搜索
22.3　深度優先搜索
22.4　拓撲排序
22.5　強連通分量
思考題
本章注記
第23章　最小生成樹
23.1　最小生成樹的形成
23.2　Kruskal算法和Prim算法
思考題
本章注記
第24章　單源最短路徑
24.1　Bellman-Ford算法
24.2　有嚮無環圖中的單源最短路徑問題
24.3　Dijkstra算法
24.4　差分約束和最短路徑
24.5　最短路徑性質的證明
思考題
本章注記
第25章　所有結點對的最短路徑問題
25.1　最短路徑和矩陣乘法
25.2　Floyd�瞁arshall算法
25.3　用於稀疏圖的Johnson算法
思考題
本章注記
第26章　最大流
26.1　流網絡
26.2　FordFulkerson方法
26.3　最大二分匹配
26.4　推送重貼標簽算法
26.5　前置重貼標簽算法
思考題
本章注記

第七部分　算法問題選編
第27章　多綫程算法
27.1　動態多綫程基礎
27.2　多綫程矩陣乘法
27.3　多綫程歸並排序
思考題
本章注記
第28章　矩陣運算
28.1　求解綫性方程組
28.2　矩陣求逆
28.3　對稱正定矩陣和最小二乘逼近
思考題
本章注記
第29章　綫性規劃
29.1　標準型和鬆弛型
29.2　將問題錶達為綫性規劃
29.3　單純形算法
29.4　對偶性
29.5　初始基本可行解
思考題
本章注記
第30章　多項式與快速傅裏葉變換
30.1　多項式的錶示
30.2　DFT與FFT
30.3　高效FFT實現
思考題
本章注記
第31章　數論算法
31.1　基礎數論概念
31.2　最大公約數
31.3　模運算
31.4　求解模綫性方程
31.5　中國餘數定理
31.6　元素的冪
31.7　RSA公鑰加密係統
31.8　素數的測試
31.9　整數的因子分解
思考題
本章注記
第32章　字符串匹配
32.1　樸素字符串匹配算法
32.2　RabinKarp算法
32.3　利用有限自動機進行字符串匹配
32.4　Knuth-Morris-Pratt算法
思考題
本章注記
第33章　計算幾何學
33.1　綫段的性質
33.2　確定任意一對綫段是否相交
33.3　尋找凸包
33.4　尋找最近點對
思考題
本章注記
第34章　NP完全性
34.1　多項式時間
34.2　多項式時間的驗證
34.3　NP完全性與可歸約性
34.4　NP完全性的證明
34.5　NP完全問題
34.5.1　團問題
34.5.2　頂點覆蓋問題
34.5.3　哈密頓迴路問題
34.5.4　旅行商問題
34.5.5　子集和問題
思考題
本章注記
第35章　近似算法
35.1　頂點覆蓋問題
35.2　旅行商問題
35.2.1　滿足三角不等式的旅行商問題
35.2.2　一般旅行商問題
35.3　集閤覆蓋問題
35.4　隨機化和綫性規劃
35.5　子集和問題
思考題
本章注記
第八部分　附錄：數學基礎知識
附錄A　求和
A.1　求和公式及其性質
A.2　確定求和時間的界
思考題
附錄注記
附錄B　集閤等離散數學內容
B.1　集閤
B.2　關係
B.3　函數
B.4　圖
B.5　樹
B.5.1　自由樹
B.5.2　有根樹和有序樹
B.5.3　二叉樹和位置樹
思考題
附錄注記
附錄C　計數與概率
C.1　計數
C.2　概率
C.3　離散隨機變量
C.4　幾何分布與二項分布
*C.5　二項分布的尾部
思考題
附錄注記
附錄D　矩陣
D.1　矩陣與矩陣運算
D.2　矩陣基本性質
思考題
附錄注記
參考文獻
索引

精彩書摘

　　證明 每個結點的秩從0開始，並且隻有執行瞭LINK操作，它纔會增加。因為最多有n—1個UNION操作，所以同樣最多有n—1個LINK操作。因為每個LINK操作或者不改變任何的秩，或者將某結點的秩加1，所以所有的秩最大為n—1。
　　引理21.6提供瞭一個關於結點秩的較弱的界。事實上，每個結點的秩最大為（lgn）（見練習21.4—2）。然而，引理21.6的這個較鬆的界已足夠滿足我們的要求。
　　時間界的證明 我們將利用攤還分析中的勢方法（見17.3節）來證明O（ma（n））的時間界。在進行攤還分析時，為瞭方便起見，我們假設不調用UNION操作，而是調用LINK操作。也就是說，因為LINK過程的參數是指嚮兩個根的指針，故我們獨立使用相應的FIND—SET操作。下麵的引理說明即使因調用UNION而導緻額外的FIND—SET操作，其漸近運行時間仍然保持不變。

　　……

前言/序言

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

信息時代基石：算法的探索與實踐 在信息爆炸、技術飛速迭代的當下，我們身處一個由數據和算法驅動的時代。從智能手機的推薦係統到復雜的金融模型，從自動駕駛的導航到基因測序的分析，算法無處不在，默默地塑造著我們的生活，定義著未來的可能性。它們是解決問題、優化流程、洞察模式的強大工具，更是計算機科學領域的核心基石。本書旨在為讀者揭示算法世界的奧秘，帶領大傢走進這個邏輯嚴謹、充滿創造力的學科殿堂，理解其深層原理，掌握其實用技巧，並培養解決復雜計算問題的能力。 算法是什麼？——從問題到解決方案的橋梁 簡單來說，算法就是解決特定問題的一係列清晰、明確、有限的步驟。它不是一個具體的程序代碼，而是一種抽象的思維方式和解決問題的藍圖。一個好的算法，如同精密的齒輪，能夠高效、準確地將輸入轉化為期望的輸齣。想象一下，我們需要找到一係列數字中的最大值。一個直觀的算法可能是：首先，將第一個數字視為當前最大值；然後，逐個遍曆剩餘的數字，如果遇到一個比當前最大值更大的數字，就更新當前最大值；最後，當遍曆完所有數字後，當前最大值就是整個列錶中的最大值。這雖然簡單，卻是一個完整的算法。 本書將從最基礎的概念入手，係統地闡述算法的定義、特性以及設計的基本原則。我們將探討如何準確地描述一個算法，如何分析其效率，以及如何選擇最適閤特定問題的算法。這不僅僅是理論上的探討，更是為日後解決實際計算挑戰打下堅實基礎的關鍵一步。理解算法的本質，就如同掌握瞭一把解鎖無數信息挑戰的鑰匙。 算法的分析：效率與可行性的衡量標準 在算法的世界裏，效率至關重要。麵對海量的數據和日益增長的計算需求，一個低效的算法可能會導緻程序運行緩慢，甚至無法在閤理的時間內得齣結果。因此，學會分析算法的效率是必不可少的技能。本書將深入講解算法分析的核心概念，包括時間復雜度和空間復雜度。 時間復雜度衡量的是算法運行所需的時間隨輸入規模增長的變化趨勢，通常用大O符號（O notation）來錶示。例如，O(n)錶示算法的運行時間與輸入規模n成綫性關係；O(n^2)則錶示運行時間與n的平方成正比。不同的時間復雜度，意味著算法在處理大規模數據時效率的巨大差異。我們將通過各種實例，學習如何計算和比較不同算法的時間復雜度，從而選擇最優解決方案。 空間復雜度則衡量算法運行時所需的內存空間。在某些場景下，內存資源也是寶貴的，因此優化空間復雜度同樣具有重要意義。本書將引導讀者理解如何評估算法的空間消耗，並在時間和空間之間做齣明智的權衡。掌握瞭這些分析工具，我們就能以一種科學、量化的方式來評估算法的優劣，確保我們設計的解決方案既正確又高效。 經典算法的寶庫：解決各領域問題的利器 算法的世界廣闊而精彩，其中湧現齣無數經典的算法，它們如同曆經時間考驗的瑰寶，能夠解決計算機科學中一係列核心問題。本書將帶領讀者係統地學習這些經典算法，並深入理解它們背後的數學原理和設計思想。 排序算法是計算機科學中最基礎也最重要的算法之一。它們的目標是將一組無序的元素按照特定的順序排列。我們將學習諸如冒泡排序、選擇排序、插入排序等簡單但直觀的算法，理解它們的原理和局限性。更進一步，我們將探索更高效的算法，如快速排序、歸並排序、堆排序等，它們在處理大規模數據集時展現齣卓越的性能。理解這些排序算法的差異和適用場景，將為我們處理數據的整理和分析打下堅實基礎。 查找算法是數據檢索的核心。當我們需要在大量數據中快速找到特定信息時，查找算法就顯得尤為重要。我們將學習簡單的綫性查找，以及更高效的二分查找，後者在有序數據集上能夠以極快的速度定位目標。此外，我們還會接觸到散列錶（Hash Table）等更高級的數據結構和查找技術，它們能夠實現近乎常數的平均查找時間。 圖算法是處理網絡、路徑、連接等問題的強大工具。圖是由節點（頂點）和邊構成的數學結構，廣泛應用於社交網絡分析、交通導航、資源分配等領域。本書將深入探討圖的錶示方法，以及一係列核心的圖算法，包括： 深度優先搜索（DFS）和廣度優先搜索（BFS）：這兩種遍曆圖的搜索策略是許多更復雜圖算法的基礎。DFS如同探險傢，深入探索圖的每個分支；BFS則如同水波擴散，一層一層地嚮外擴展。 最短路徑算法：如Dijkstra算法和Floyd-Warshall算法，它們能夠找到圖中任意兩個節點之間的最短路徑，這在導航係統、網絡路由等方麵至關重要。 最小生成樹算法：如Prim算法和Kruskal算法，它們能夠找到連接圖中所有頂點的成本最低的邊的集閤，這在網絡設計、電力綫路鋪設等問題中有廣泛應用。 動態規劃是一種強大且通用的算法設計技術，適用於解決具有重疊子問題和最優子結構的問題。它通過將大問題分解成小問題，並存儲和重用子問題的解，從而避免重復計算，達到高效求解的目的。我們將通過經典的例子，如斐波那契數列、背包問題、最長公共子序列等，來理解動態規劃的思維方式和實現方法。 貪心算法是一種直觀的算法設計策略，它在每一步選擇局部最優解，希望最終能得到全局最優解。雖然貪心算法並非總是有效，但在許多問題中，它能夠提供簡單且高效的解決方案。我們將學習如何識彆適閤貪心算法的問題，並理解其局限性。 計算幾何是算法領域中一個重要的分支，它研究如何利用算法來解決幾何問題。我們將接觸到計算幾何的基本概念，如點、綫段、多邊形，以及相關的算法，如凸包的計算、綫段相交的判斷等，這些在計算機圖形學、機器人學等領域有著廣泛的應用。 其他重要的算法領域還包括字符串匹配、數論算法、概率算法等，本書也將對這些領域進行適當的介紹，為讀者打開更廣闊的視野。 算法設計與實現：理論與實踐的結閤 理解算法的原理固然重要，但將算法轉化為實際可運行的代碼，並解決真實世界的問題，則是理論轉化為生産力的關鍵。本書不僅注重算法的理論講解，更強調算法的設計與實現。我們將探討如何將抽象的算法邏輯轉化為結構清晰、易於理解和維護的程序代碼。 在學習過程中，讀者將有機會接觸到各種編程語言的實現示例，理解如何根據算法的特性選擇閤適的數據結構，以及如何優化代碼以獲得更好的性能。我們將鼓勵讀者動手實踐，通過解決一係列練習題和編程挑戰，將所學知識融會貫通，真正掌握算法的設計和實現技巧。 算法的應用：賦能現代科技 算法早已不再是僅限於學術研究的抽象概念，而是驅動現代科技發展的核心動力。本書將通過豐富的實例，展示算法在各個領域的廣泛應用，幫助讀者深刻理解算法的價值和影響力。 人工智能與機器學習：推薦係統、圖像識彆、自然語言處理、自動駕駛等領域，都離不開復雜的算法支持。我們將探討機器學習中的核心算法，如決策樹、支持嚮量機、神經網絡等，以及它們如何使機器具備學習和決策能力。 大數據分析：在海量數據中挖掘有價值的信息，需要高效的算法來處理和分析。我們將瞭解如何利用算法進行數據挖掘、模式識彆、預測分析等，從而從數據中獲得洞察。 網絡與通信：互聯網的暢通、數據的傳輸、信息的安全，都依賴於各種精密的算法。路由算法、加密算法、壓縮算法等，共同構建瞭現代通信的基礎。 科學計算與工程：從天氣預報到藥物研發，從金融建模到航空航天，科學計算和工程領域都離不開對復雜問題的算法求解。 通過這些應用案例，讀者將能夠更直觀地感受到算法的力量，理解算法如何解決現實世界中的挑戰，並激發他們在未來創新和發展的靈感。 為未來而準備：持續學習與探索 信息技術的發展日新月異，新的算法和技術層齣不窮。本書所介紹的內容，是理解和掌握這些新知識的堅實基礎。我們鼓勵讀者在掌握本書內容之後，繼續保持對算法領域的好奇心和探索精神，不斷學習新的算法和技術，緊跟時代發展的步伐。 算法不僅僅是計算機科學的工具，更是一種解決問題、進行邏輯推理的思維方式。掌握算法，就是掌握瞭一門通往更廣闊知識領域和無限創新可能性的語言。希望本書能成為您探索算法世界的精彩起點，並為您的學術和職業生涯提供強大的支撐。

評分☆☆☆☆☆

這本書的厚度足以說明其內容的深度和廣度。作為一名正在努力提升自己技術實力的開發者，我深知算法是計算機科學的基石，是解決一切問題的根本。我一直渴望能夠有一本權威的著作，係統地梳理算法的知識脈絡，讓我能夠從根源上理解計算機的運行機製。這本書恰恰滿足瞭我的需求。我非常期待書中對各種算法的時間和空間復雜度進行詳盡的分析，這對我來說是至關重要的，能夠幫助我更好地評估和優化代碼的性能。同時，我也對書中介紹的一些高級算法技巧，比如近似算法、隨機化算法等，充滿瞭濃厚的興趣，相信它們能為我打開新的思路，解決一些目前看來棘手的難題。我希望通過精讀這本書，能夠真正掌握算法的設計思想和分析方法，從而在麵對實際問題時，能夠信手拈來，給齣最優的解決方案，成為一名更優秀的工程師。

評分☆☆☆☆☆

我之前接觸過一些關於數據結構和算法的書籍，但總覺得它們要麼過於碎片化，要麼就是過於理論化，脫離實際應用。而這本《算法導論》給我的感覺截然不同。它的結構非常清晰，從最基礎的概念講起，循序漸進，難度逐漸提升。我特彆喜歡書中對每個算法都給齣瞭詳細的僞代碼和圖示，這對於我這種視覺型學習者來說，簡直是福音。很多抽象的概念，通過圖示和僞代碼的結閤，立刻變得直觀易懂。我尤其期待書中關於圖算法的部分，比如最短路徑、最小生成樹等，在實際的導航係統、網絡規劃等方麵都有廣泛應用。能夠深入理解這些經典算法，對我來說是職業生涯的一個重要裏程碑。這本書就像一個經驗豐富的老師，耐心細緻地指導我學習算法的精髓，讓我感覺不再是孤軍奮戰，而是有瞭一個強大的後盾。希望讀完這本書，我能夠自信地解決各種復雜的算法問題，並在實際工作中遊刃有餘。

評分☆☆☆☆☆

說實話，一開始拿起這本書，我感覺自己就像一個初次踏入迷宮的探險者，麵對著密密麻麻的符號和公式，有點不知所措。我並不是計算機科學專業的科班齣身，工作中的大部分時間都聚焦在實際的項目開發上，所以很多理論性的東西對我來說都有些陌生。但即便如此，我還是被這本書的嚴謹和係統所吸引。它不像某些網絡教程那樣淺嘗輒止，而是深入淺齣地講解每一個算法的原理、推導過程以及應用場景。我尤其欣賞書中對不同算法進行詳細的比較分析，比如在解決同一個問題時，為什麼有的算法性能更好，背後的數學原理是什麼。雖然有些章節確實需要花費不少時間和精力去消化，反復閱讀纔能有所領悟，但我相信，這種紮實的理論基礎，對於提升我的編程思維和解決復雜問題的能力是至關重要的。我希望通過這本書，能真正理解“為什麼”要這麼做，而不是僅僅停留在“怎麼做”的層麵，從而在未來的職業生涯中，能夠應對更多挑戰，設計齣更具創新性的解決方案。

評分☆☆☆☆☆

這本書剛拿到手的時候，就被它厚重的體積和封麵上的“算法導論”幾個字鎮住瞭。我一直對計算機科學的底層原理非常感興趣，尤其是在學習各種編程語言和框架的時候，總感覺缺少一些核心的理論支撐。很多時候，我們隻是調用現成的庫函數，或者照搬網上找到的代碼片段，但對於這些“魔法”是如何實現的，卻一知半解。這本書就像一本武功秘籍，我期待它能揭示那些隱藏在代碼之下的深刻邏輯。我特彆希望能通過它理解諸如排序、搜索、圖算法等基礎但至關重要的概念，並且能夠掌握分析算法效率的方法，比如時間復雜度和空間復雜度，這樣我纔能更有效地優化自己的代碼，寫齣更高效、更健壯的程序。另外，我對書中關於動態規劃和貪心算法的章節也充滿期待，這些聽起來就很“高大上”的算法，希望能在這本書的指導下，變得觸手可及，不再是隻能仰望的學術名詞。讀完這本書，我希望能擁有“內功心法”，而不是僅僅停留在“招式”的學習上，真正做到知其然，也知其所以然。

評分☆☆☆☆☆

坦白講，我對這本書的期望很高，因為身邊很多資深的程序員都推薦過。我之前在工作中遇到過不少性能瓶頸，往往是因為對算法的理解不夠深入，導緻選擇瞭效率不高的解決方案。所以，我希望通過這本《算法導論》，能夠係統地學習各種經典算法，理解它們的優缺點，以及在什麼場景下應用最閤適。我尤其對書中的“計算理論”和“高級算法”部分感到好奇，這些章節聽起來就充滿瞭挑戰，但也蘊藏著解決更復雜問題的鑰匙。我希望能夠通過這本書，建立起一個完善的算法知識體係，能夠更科學地分析和設計算法，從而在未來的工作中，能夠寫齣性能更優、更具擴展性的代碼。這本書不僅是一本技術手冊，更像是一本思想的啓迪者，我期待它能幫助我跳齣思維定勢，用更宏觀、更本質的視角來看待編程問題。

評分☆☆☆☆☆

書本講得很好，很詳細，透徹，你值得擁有，碼農的標配

評分☆☆☆☆☆

搞活動買的，以前本來有一本，但是被蟑螂咬瞭，搞得很髒，丟瞭重新買一本，紙張質量看起來還不錯。

評分☆☆☆☆☆

有一次手賤買瞭不少書，希望自己能看，要是這些書看不完，以後再便宜我也不買瞭

評分☆☆☆☆☆

書很厚，質量和內容都很不錯，值得推薦，經常在京東買書，活動很劃算

評分☆☆☆☆☆

還在看，比第一版加瞭不少新內容。

評分☆☆☆☆☆

好書，慢慢看，紙張也好

評分☆☆☆☆☆

剛拿到 還沒開始看 不過會加油的(? •?_•?)?

評分☆☆☆☆☆

我為什麼喜歡在京東買東西，因為今天買明天就可以送到。我為什麼每個商品的評價都一樣，因為在京東買的東西太多太多瞭，導緻積纍瞭很多未評價的訂單，所以我統一用段話作為評價內容。京東購物這麼久，有買到很好的産品

評分☆☆☆☆☆

不愧為程序員的聖經，看著厚度，估計要吃灰！！