算法設計與分析基礎

第1章 緒論
1.1 什麼是算法
1.2 算法問題求解基礎
1.3 重要的問題類型
1.4 基本數據結構
小結
第2章 算法效率分析基礎
2.1 分析框架
2.2 漸進符號和基本效率類型
2.3 非遞歸算法的數學分析
2.4 遞歸算法的數學分析
2.5 例題:斐波那
2.6 算法的經驗分析
2.7 算法可視法
小結
第3章 蠻力法
3.1 選擇排序和冒泡排序
3.2 順序查找和蠻力字符串匹配
3.3 最近對和凸包問題的蠻力算法
3.4 窮舉查找
小結
第4章 分治法
4.1 合並排序
4.2 快速排序
4.3 折半查找
4.4 二叉樹遍歷及其相關特性
4.5 大整數乘法和Strassen矩陣乘法
4.6 用分治法解最近對問題和凸包問題
小結
第5章 減治法
5.1 插入排序
5.2 深度優先查找和廣度優先查找
……
第6章 變治法
第7章 時空權衡
第8章 動態規劃
第9章 貪婪技術
第10章 迭代改進
第11章 算法能力的極限
第12章 超越算法能力的極限
跋
附錄
習題提示
參考文獻

三年前的夏天，本書第l版剛剛脫稿，現在，它的第2版又即將付梓了。

三年中，本書第1版伴隨著眾多喜愛算法並用心學習算法的各位讀者走過了一千多個日日夜夜。想到大家正在通過我的文字來理解Levitin教授的原著，又想到自己水平有限，失誤實在無法完全避免，因此背上常常會生出汗來。但我沒有想到的是，讀者給了我很多鼓勵和幫助。

首先，讀者們給我寫來大量的電子郵件，有探討問題的，有表揚的，有建議的，還有打算為本書成立一個論壇的，真的非常感謝大家。其次，讀者們聚集在某一知名網上書店的論壇里討論本書，大多數讀者都沒有吝惜溢美之詞，讓我受寵若驚。而且，先後有20位大學教師確定將此書作為相關課程的教材，我非常感謝大家的信任。更有益鋒、csoapy、馬帥、lrc531、dreamhead等網友，提出了不少勘誤建議，尤其令人高興的是，這些建議100％都是正確的。

欣喜之余，不禁讓人感嘆互聯網的巨大威力。如果沒有電子郵件、網上論壇這樣的互聯網工具，讀者和譯者的交流不可能這樣自由和迅捷，最新的勘誤也不能以最快的速度送達讀者手中，就連書中許多互聯網相關的習題也無法完成。更有意思的是，如果沒有互聯網，我也不可能為大家翻譯本書，因為對本書譯者的甄選，譯者和編者的日常交流也完全是在網上進行的。

互聯網就是以這樣的方式在改變著我們的生活，改變著整個世界，可以說，它是近20年來最偉大的發明。但大家有沒有想到，正是各種算法在支撐著整個互聯網的正常運行。互聯網的信息傳輸需要路由選擇算法，互聯網的信息安全需要加密算法，互聯網的信息檢索需要模式匹配算法，互聯網的信息存儲需要排序算法，這樣的例子不勝枚舉。應該承認，沒有算法就沒有互聯網。

本書第l章“緒論”引用了David Berlinski的名言︰ “微積分以及在微積分基礎上建立起來的數學分析體系成就了現代科學，而算法則成就了現代世界。”這句話絕不是隨便說說而已的，算法的確是一種改造世界的有力工具。因此，我衷心希望讀者們能夠學好算法、用好算法，甚至能在算法上有所創新，真正掌握算法的強大威力。

最後，我還是要感謝家人，尤其是妻子李靚對本書翻譯過程的大力支持，你們的贊賞是我堅持下去的動力。