目 錄

第一部分 基本概念和算法導(dǎo)引第1章 算法分析基本概念

1.1 引言

1.2 歷史背景

1.3 二分搜索

1.4 合并兩個(gè)已排序的表

1.5 選擇排序

1.6 插入排序

1.7 自底向上合并排序

1.8 時(shí)間復(fù)雜性

1.9 空間復(fù)雜性

1.10 最優(yōu)算法

1.11 如何估計(jì)算法的運(yùn)行時(shí)間

1.12 最壞情況和平均情況的分析

1.13 平攤分析

1.14 輸入大小和問(wèn)題實(shí)例

1.15 分治遞推式

1.16 練習(xí)

1.17 參考注釋第2章 數(shù)據(jù)結(jié)構(gòu)

2.1 引言

2.2 鏈表

2.3 圖

2.4 樹(shù)

2.5 根樹(shù)

2.6 二叉樹(shù)

2.7 練習(xí)

2.8 參考注釋第3章 堆和不相交集數(shù)據(jù)結(jié)構(gòu)

3.1 引言

3.2 堆

3.3 不相交集數(shù)據(jù)結(jié)構(gòu)

3.4 練習(xí)

3.5 參考注釋

第二部分 基于遞歸的技術(shù)第4章 歸納法

4.1 引言

4.2 尋找多數(shù)元素

4.3 整數(shù)冪

4.4 多項(xiàng)式求值（Horner規(guī)則）

4.5 基數(shù)排序

4.6 生成排列

4.7 練習(xí)

4.8 參考注釋第5章 分治

5.1 引言

5.2 二分搜索

5.3 合并排序

5.4 分治范式

5.5 選擇： 尋找中項(xiàng)和第k小的元素

5.6 快速排序

5.7 多選

5.8 大整數(shù)乘法

5.9 矩陣乘法

5.10 最近點(diǎn)對(duì)問(wèn)題

5.11 練習(xí)

5.12 參考注釋第6章 動(dòng)態(tài)規(guī)劃

6.1 引言

6.2 最長(zhǎng)公共子序列問(wèn)題

6.3 矩陣鏈相乘

6.4 動(dòng)態(tài)規(guī)劃范式

6.5 所有點(diǎn)對(duì)的最短路徑問(wèn)題

6.6 背包問(wèn)題

6.7 練習(xí)

6.8 參考注釋

第三部分 最先割技術(shù)第7章 貪心算法

7.1 引言

7.2 最短路徑問(wèn)題

7.3 最小耗費(fèi)生成樹(shù)（Kruskal算法）

7.4 最小耗費(fèi)生成樹(shù)(Prim算法)

7.5 文件壓縮

7.6 練習(xí)

7.7 參考注釋第8章 圖的遍歷

8.1 引言

8.2 深度優(yōu)先搜索

8.3 深度優(yōu)先搜索的應(yīng)用

8.4 廣度優(yōu)先搜索

8.5 廣度優(yōu)先搜索的應(yīng)用

8.6 練習(xí)

8.7 參考注釋

第四部分 問(wèn)題的復(fù)雜性第9章 NP完全問(wèn)題

9.1 引言

9.2 P類(lèi)

9.3 NP類(lèi)

9.4 NP完全問(wèn)題的分析

9.5 co�睳P類(lèi)

9.6 三種復(fù)雜性類(lèi)之間的關(guān)系

9.7 練習(xí)

9.8 參考注釋第10章 計(jì)算復(fù)雜性引論

10.1 引言

10.2 計(jì)算模型：圖靈機(jī)

10.3 k帶圖靈機(jī)和時(shí)間復(fù)雜性

10.4 離線圖靈機(jī)和空間復(fù)雜性

10.5 帶壓縮和線性加速

10.6 復(fù)雜性類(lèi)之間的關(guān)系

10.7 歸約

10.8 完全性

10.9 多項(xiàng)式時(shí)間層次

10.10 練習(xí)

10.11 參考注釋第11章 下界

11.1 引言

11.2 平凡下界

11.3 決策樹(shù)模型

11.4 代數(shù)決策樹(shù)模型

11.5 線性時(shí)間歸約

11.6 練習(xí)

11.7 參考注釋

第五部分 克服困難性第12章 回溯法

12.1 引言

12.2 3著色問(wèn)題

12.3 8皇后問(wèn)題

12.4 一般回溯法

12.5 分支限界法

12.6 練習(xí)

12.7 參考注釋第13章 隨機(jī)算法

13.1 引言

13.2 Las Vegas和Monte Carlo算法

13.3 兩個(gè)簡(jiǎn)單的例子

13.4 隨機(jī)快速排序

13.5 隨機(jī)選擇

13.6 占有問(wèn)題

13.7 尾部界

13.8 Chernoff界的應(yīng)用：多選

13.9 隨機(jī)取樣

13.10 最小割問(wèn)題

13.11 測(cè)試串的相等性

13.12 模式匹配

13.13 素?cái)?shù)測(cè)試

13.14 練習(xí)

13.15 參考注釋第14章 近似算法

14.1 引言

14.2 基本定義

14.3 差界

14.4 相對(duì)性能界

14.5 多項(xiàng)式近似方案

14.6 完全多項(xiàng)式近似方案

14.7 練習(xí)

14.8 參考注釋

第六部分 域指定問(wèn)題的迭代改進(jìn)第15章 網(wǎng)絡(luò)流

15.1 引言

15.2 預(yù)備知識(shí)

15.3 Ford�睩ulkerson方法

15.4 最大容量增值

15.5 最短路徑增值

15.6 Dinic算法

15.7 MPM算法

15.8 練習(xí)

15.9 參考注釋第16章 匹配

16.1 引言

16.2 預(yù)備知識(shí)

16.3 二分圖上的網(wǎng)絡(luò)流方法

16.4 二分圖的匈牙利樹(shù)方法

16.5 一般圖中的最大匹配

16.6 二分圖的On2.5算法

16.7 練習(xí)

16.8 參考注釋

第七部分 計(jì)算幾何技術(shù)第17章 幾何掃描

17.1 引言

17.2 一個(gè)簡(jiǎn)單的例子：計(jì)算點(diǎn)集中的極大點(diǎn)

17.3 幾何預(yù)備知識(shí)

17.4 計(jì)算線段的交點(diǎn)

17.5 凸包問(wèn)題

17.6 計(jì)算點(diǎn)集的直徑

17.7 練習(xí)

17.8 參考注釋第18章 Voronoi圖解

18.1 引言

18.2 最近點(diǎn)Voronoi圖解

18.3 Voronoi圖解的應(yīng)用

18.4 最遠(yuǎn)點(diǎn)Voronoi圖解

18.5 最遠(yuǎn)點(diǎn)Voronoi圖解的應(yīng)用

18.6 練習(xí)

18.7 參考注釋附錄A 數(shù)學(xué)預(yù)備知識(shí)

附錄B 離散概率簡(jiǎn)介

參考文獻(xiàn)