出版者的話
譯者序
前言
第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.3BellmanFord 算法
14.4有向無環圖中的最短路徑
14.5所有頂點對之間的最短路徑
14.5.1動態規劃最短路徑算法
14.5.2通過矩陣乘法計算最短路徑
14.6練習
本章注記
第15章最小生成樹
15.1最小生成樹的性質
15.2Kruskal算法
15.3PrimJarník算法
15.4Baruvka算法
15.5練習
本章注記
第16章網絡流和匹配
16.1流與割
16.1.1割
16.1.2剩余容量和增流路徑
16.2最大流算法
16.2.1FordFulkerson算法
16.2.2EdmondsKarp算法
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.2CookLevin 定理
17.2.3如何證明一個問題是NP完全問題
17.3合取范式可滿足問題和3可滿足問題
17.4頂點覆蓋、團和集合覆蓋
17.5子集和與背包問題
17.6哈密頓回路和TSP
17.7練習
本章注記
第18章近似算法
18.1幾何旅行商問題
18.1.1MetricTSP的一個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.
新書資訊