算法設計技巧與分析

第一部分 基本概念和算法導引
第1章 算法分析基本概念
1.1 引言
1.2 歷史背景
1.3 二分搜索
1.4 合並兩個已排序的表
1.5 選擇排序
1.6 插入排序
1.7 自底向上合並排序
1.8 時間復雜性
1.9 空間復雜性
1.10 最優算法
1.11 如何估計算法運行時間
1.12 最壞情況和平均情況的分析
1.13 平攤分析
1.14 輸入大小和問題實例
1.15 練習
1.16 參考注釋
第2章 數學預備知識
2.1 集合、關系和函數
2.2 證明方法
2.3 對數
2.4 底函數和頂函數
2.5 階乘和二項式系數
2.6 鴿巢原理
2.7 和式
2.8 遞推關系
2.9 練習
第3章 數據結構
3.1 引言
3.2 鏈表
3.3 圖
3.4 樹
3.5 根樹
3.6 二叉樹
3.7 練習
3.8 參考注釋
第4章 堆和不相交集數據結構
4.1 引言
4.2 堆
4.3 不相交集數據結構
4.4 練習
4.5 參考注釋
第二部分 基于遞歸的技術
第5章 歸納法
5.1 引言
5.2 兩個簡單的例子
5.3 基數排序
5.4 整數冪
5.5 多項式求值（Horner規則）
5.6 生成排列
5.7 尋找多數元素
5.8 練習
5.9 參考注釋
第6章 分治
6.1 引言
6.2 二分搜索
6.3 合並排序
6.4 分治範式
6.5 尋找中項和第k小元素
6.6 快速排序
6.7 大整數乘法
6.8 矩陣乘法
6.9 最近點對問題
6.10 練習
6.11 參考注釋
第7章 動態規劃
7.1 引言
7.2 最長公共子序列問題
7.3 矩陣鏈相乘
7.4 動態規劃範式
7.5 所有點對的最短路徑問題
7.6 背包問題
7.7 練習
7.8 參考注釋
第三部分 最先割技術
第8章 貪心算法
8.1 引言
8.2 最短路徑問題
8.3 最小耗費生成樹（Kruskal算法）
8.4 最小耗費生成樹（Prim算法）
8.5 文件壓縮
8.6 練習
8.7 參考注釋
第9章 圖的遍歷
9.1 引言
9.2 深度優先搜索
9.3 深度優先搜索的應用
9.4 廣度優先搜索
9.5 廣度優先搜索的應用
9.6 練習
9.7 參考注釋
第四部分 問題的復雜性
第10章 NP完全問題
10.1 引言
10.2 P類
10.3 NP類
10.4 NP完全問題
10.5 co-NP類
10.6 NPI類
10.7 四種類之間的關系
10.8 練習
10.9 參考注釋
第11章 計算復雜性引論
11.1 引言
11.2 計算模型︰圖靈機
11.3 k帶圖靈機和時間復雜性
11.4 離線圖靈機和空間復雜性
11.5 帶壓縮和線性增速
11.6 復雜性類之間的關系
11.7 歸約
11.8 完全性
11.9 多項式時間層次
11.10 練習
11.11 參考注釋
第12章 下界
12.1 引言
12.2 平凡下界
12.3 決策樹模型
12.4 代數決策樹模型
12.5 線性時間歸約
12.6 練習
12.7 參考注釋第五部分克服困難性
第五部分 克服困難性
第13章 回溯法
13.1 引言
13.2 3著色問題
13.3 8皇後問題
13.4 一般回溯方法
13.5 分支限界法
13.6 練習
13.7 參考注釋
第14章 隨機算法
14.1 引言
14.2 Las Vegas和Monte Carlo算法
14.3 隨機化快速排序
14.4 隨機化的選擇算法
14.5 測試串的相等性
14.6 模式匹配
14.7 隨機取樣
14.8 素數性測試
14.9 練習
14.10 參考注釋
第15章 近似算法
15.1 引言
15.2 基本定義
15.3 差界
15.4 相對性能界
15.5 多項式近似方案
15.6 完全多項式近似方案
15.7 練習
15.8 參考注釋第六部分域指定問題的迭代改進
第六部分 域指定問題的迭代改進
第16章 網絡流
16.1 引言
16.2 預備知識
16.3 Ford-Fulkerson方法
16.4 最大容量增值
16.5 最短路徑增值
16.6 Dinic算法
16.7 MPM算法
16.8 練習
16.9 參考注釋
第17章 匹配
17.1 引言
17.2 預備知識
17.3 網絡流方法
17.4 二分圖的匈牙利樹方法
17.5 一般圖中的最大匹配
17.6 二分圖的On2.5算法
17.7 練習
17.8 參考注釋
第七部分 計算幾何技術
第18章 幾何掃描
18.1 引言
18.2 幾何預備知識
18.3 計算線段的交點
18.4 凸包問題
18.5 計算點集的直徑
18.6 練習
18.7 參考注釋
第19章 Voronoi圖解
19.1 引言
19.2 最近點Voronoi圖解
19.3 Voronoi圖解的應用
19.4 最遠點Voronoi圖解
19.5 最遠點Voronoi圖解的應用
19.6 練習
19.7 參考注釋
參考文獻

多年來，我一直在尋找一本適合國內計算機專業學生用的有關算法方面的國外教材。盡管在國內引進了一些不錯的國外教材，但總有篇幅過多，內容不夠新穎或數據結構內容夾雜其中等等這樣那樣的不甚滿意之處。

不久前我有幸看到世界科學圖書出版社出版的由M．H．Alsuwaiyel撰寫的“Algorithms Design Techniques and Analysis”，它是以國際著名算法專家，我國台灣出身的李德財教授所主編的系列叢書“Lecture Notes Series on Computing”中的一本。雖然此書不是美國的大學教材，而是沙特阿拉伯的大學計算機系教材，但是我很快就被該書的組織簡明、概括，且包含當前市面上算法較少涉及的概率算法和近似算法的基本內容所吸引。它是一本適合本科生學習算法的好書。

該書涉及數據結構的部分較少，即使有一些，描述上也很快與算法中比較復雜的集合查找和合並運算等相結合，讓讀者不會感到和已經學過的數據結構重復。這比較適合國內大學計算機系中數據結構和算法分成兩門課開設的實際狀況。

對于想了解NP完全問題基本概念的讀者，本書的篇幅給了他們基本但又清楚的描述。本書還包括計算幾何一章，其取材也是適中的。

概率算法和近似算法是近20年來算法研究迅猛發展的領域，本書給予了足夠的重視，這是本書特色之一，是我向國內學生特別推薦的主要原因。

本書的另一特色是以算法的設計技術為綱，講述一個又一個的算法技術，然後分析其算法復雜性。

我希望該書（簡體中文版）的出版能彌補短期內暫時無合適中文算法教材的空白。誠摯地向國內的廣大算法老師推薦采用本書作為教材。

本書由上海應用技術學院的吳偉昶老師在算法界的老前輩方世昌教授的協助下翻譯。吳偉昶多年來對算法很專研，在翻譯過程中對原著的少量錯誤進行了糾正。方世昌教授是算法名著“The Design and Analysis of Compnter Algorithms by Aho，Hopcroft and Ullman（1974）”我國最早譯本之一的譯者，雖然該書至今還沒有理想的譯本正式出版，但是方的譯本在20世紀80年代的我國高校計算機系師生中廣泛流傳，對算法在我國的普及做出了不可磨滅的貢獻。我堅信本譯本的出版將對我國高校計算機系的算法教學起到很大的推動作用。

朱洪
年7月6日
復旦大學