齣版者的話
譯者序
前言
第1章算法分析
1.1分析算法
1.1.1僞代碼
1.1.2隨機存取機模型
1.1.3基本操作數目的計算
1.1.4遞歸算法的分析
1.1.5漸近錶示法
1.1.6漸近錶示法的重要性
1.2相關數學知識復習
1.2.1求和
1.2.2對數和冪
1.2.3簡單的證明技術
1.2.4概率基礎
1.3算法分析案例
1.3.1最大子數組問題的第一個解
1.3.2一種改進的求最大子數組算法
1.3.3綫性時間的最大子數組算法
1.4平攤分析
1.4.1平攤技術
1.4.2對一個可擴展數組實現的分析
1.5練習
本章注記
第一部分數據結構
第2章基本數據結構
2.1棧和隊列
2.1.1棧
2.1.2隊列
2.2列錶
2.2.1基於索引的列錶
2.2.2鏈錶
2.3樹
2.3.1樹的定義
2.3.2樹的遍曆
2.3.3二叉樹
2.3.4錶示樹的數據結構
2.4練習
本章注記
第3章二叉搜索樹
3.1搜索和更新
3.1.1二叉搜索樹的定義
3.1.2二叉搜索樹中的搜索
3.1.3二叉搜索樹中的插入
3.1.4二叉搜索樹中的刪除
3.1.5二叉搜索樹的性能
3.2範圍查詢
3.3基於索引的搜索
3.4隨機構造二叉搜索樹
3.5練習
本章注記
第4章平衡二叉搜索樹
4.1秩和鏇轉
4.2AVL樹
4.3紅黑樹
4.4弱AVL樹
4.5伸展樹
4.6練習
本章注記
第5章優先隊列和堆
5.1優先隊列
5.2PQ排序、選擇排序和插入排序
5.2.1選擇排序
5.2.2插入排序
5.3堆
5.3.1基於數組結構的二叉樹
5.3.2堆中的插入
5.3.3堆中的刪除
5.4堆排序
5.5擴展優先隊列
5.6練習
本章注記
第6章散列錶
6.1映射
6.1.1映射的定義
6.1.2查找錶
6.2散列函數
6.2.1分量求和
6.2.2多項式求值函數
6.2.3基於錶格的散列
6.2.4取模
6.2.5隨機綫性和多項式函數
6.3碰撞處理與再散列
6.3.1拉鏈法
6.3.2開放尋址法
6.3.3綫性探測
6.3.4平方探測
6.3.5雙重散列
6.3.6再散列
6.4布榖鳥散列
6.5通用散列
6.6練習
本章注記
第7章並查集結構
7.1並查集及其應用
7.1.1連通分支
7.1.2迷宮建築和滲透理論
7.2基於列錶的實現
7.3基於樹的實現
7.4練習
本章注記
第二部分排序和選擇
第8章歸並排序和快速排序
8.1歸並排序
8.1.1分而治之
8.1.2歸並排序和遞推方程
8.2快速排序
8.2.1隨機快速排序
8.2.2原地快速排序
8.3基於比較的排序的下界
8.4練習
本章注記
第9章快速排序和選擇
9.1桶排序和基數排序
9.1.1桶排序
9.1.2基數排序
9.2選擇
9.2.1隨機快速選擇
9.2.2確定性選擇
9.3加權中位數
9.4練習
本章注記
第三部分基本技術
第10章貪心法
10.1分份背包問題
10.2任務調度
10.3文本壓縮和哈夫曼編碼
10.4練習
本章注記
第11章分治法
11.1遞推與主定理
11.2整數乘法
11.3矩陣乘法
11.4極大點集問題
11.5練習
本章注記
第12章動態規劃
12.1矩陣連乘
12.2通用技術
12.3望遠鏡調度
12.4博弈策略
12.4.1硬幣行
12.4.2概率博弈策略與逆嚮歸納法
12.5最長公共子序列問題
12.5.1問題定義
12.5.2應用動態規劃解LCS問題
12.60-1背包問題
12.7練習
本章注記
第13章圖及遍曆
13.1圖的術語和錶示方法
13.1.1圖的一些術語
13.1.2圖的操作
13.1.3錶示圖的數據結構
13.2深度優先搜索
13.3廣度優先搜索
13.4有嚮圖
13.4.1遍曆有嚮圖
13.4.2傳遞閉包
13.4.3有嚮DFS和垃圾迴收
13.4.4有嚮無環圖
13.5雙連通分量
13.6練習
本章注記
第四部分圖算法
第14章最短路徑
14.1單源最短路徑
14.2Dijkstra算法
14.3BellmanFord 算法
14.4有嚮無環圖中的最短路徑
14.5所有頂點對之間的最短路徑
14.5.1動態規劃最短路徑算法
14.5.2通過矩陣乘法計算最短路徑
14.6練習
本章注記
第15章最小生成樹
15.1最小生成樹的性質
15.2Kruskal算法
15.3PrimJarník算法
15.4Baruvka算法
15.5練習
本章注記
第16章網絡流和匹配
16.1流與割
16.1.1割
16.1.2剩餘容量和增流路徑
16.2最大流算法
16.2.1FordFulkerson算法
16.2.2EdmondsKarp算法
16.3最大二分圖匹配
16.4棒球賽的淘汰
16.5最低成本流
16.6練習
本章注記
第五部分計算睏難問題
第17章NP完全性
17.1P和NP
17.1.1定義復雜類P和NP
17.1.2一些有趣的NP問題
17.2NP完全性
17.2.1多項式時間歸約和NP難度
17.2.2CookLevin 定理
17.2.3如何證明一個問題是NP完全問題
17.3閤取範式可滿足問題和3可滿足問題
17.4頂點覆蓋、團和集閤覆蓋
17.5子集和與背包問題
17.6哈密頓迴路和TSP
17.7練習
本章注記
第18章近似算法
18.1幾何旅行商問題
18.1.1MetricTSP的一個2近似算法
18.1.2Christofides近似算法
18.2覆蓋問題的近似
18.2.1頂點覆蓋的2近似算法
18.2.2集閤覆蓋的對數近似
18.3多項式時間近似方法
18.4迴溯和分支定界
18.4.1迴溯法
18.4.2分支定界法
18.5練習
本章注記
第六部分高級主題
第19章隨機算法
19.1隨機排列的生成
19.2穩定婚姻和優惠券收集
19.2.1優惠券收集問題分析
19.2.2穩定婚姻問題
19.3最小割
19.3.1收縮邊
19.3.2計算最小割
19.3.3更快的算法
19.4尋找素數
19.5切爾諾夫界
19.5.1馬爾可夫不等式
19.5.2示性隨機變量之和
19.5.3幾何型隨機變量之和
19.6跳躍錶
19.6.1搜索
19.6.2更新操作
19.6.3跳躍錶的概率分析
19.7練習
本章注記
第20章B樹和外部存儲器
20.1外部存儲器
20.2(2,4)樹和B樹
20.2.1多叉搜索樹
20.2.2(2,4)樹
20.2.3(a,b)樹和B樹
20.3外部存儲器排序
20.4在綫緩存算法
20.5練習
本章注記
第21章多維搜索
21.1範圍樹
21.2優先搜索樹
21.2.1構造優先搜索樹
21.2.2在優先搜索樹中搜索
21.2.3優先範圍樹
21.3四叉樹和kd樹
21.3.1四叉樹
21.3.2kd樹
21.4練習
本章注記
第22章計算幾何
22.1幾何對象上的操作
22.2凸殼
22.2.1禮品包裝算法
22.2.2Graham掃描算法
22.3綫段相交
22.4求最近點對
22.5練習
本章注記
第23章字符串算法
23.1字符串操作
23.2BoyerMoore 算法
23.3KnuthMorrisPratt算法
23.4基於散列的詞典匹配
23.5字典樹
23.5.1標準字典樹
23.5.2壓縮字典樹
23.5.3後綴字典樹
23.5.4搜索引擎
23.6練習
本章注記
第24章密碼學
24.1最大公約數
24.1.1一些初等數論知識
24.1.2歐幾裏得GCD算法
24.2模運算
24.2.1模冪運算
24.2.2模乘法逆
24.3加密操作
24.4RSA密碼係統
24.5El Gamal密碼係統
24.6練習
本章注記
第25章快速傅裏葉變換
25.1捲積
25.2原始單位根
25.3離散傅裏葉變換
25.4快速傅裏葉變換算法
25.5練習
本章注記
第26章綫性規劃
26.1定義問題
26.2單純形法
26.2.1鬆弛型
26.2.2擴展的例子
26.2.3單純形算法
26.3對偶
26.4綫性規劃的應用
26.5練習
本章注記
附錄A一些有用的數學知識
參考文獻
· · · · · · (收起)