算法設計與分析(第2版)（簡體書）

本書是作者在多年從事算法設計與分析課程教學和研究的基礎上編寫而成，系統地介紹了算法設計與分析的理論、方法和技術。內容圍繞兩條主線來組織。一條主線是介紹典範性的算法問題，如排序、選擇、圖遍歷等。 另一條主線是介紹典範性的算法設計分析策略，如分治、貪心、動態規劃等算法設計策略和對手分析、平攤分析等算法分析策略。本書中兩條主線交替進行，每條主線又各自分為基本和進階兩部分。

講解抽象的算法設計與分析知識，幫助讀者脫離具體的機器與編程語言的細節，瞭解算法設計背後的核心原理。

前言
教學建議
第一部分計算模型
第1 章抽象的算法設計與分析........... 2

1.1 RAM 模型的引入................... 2

1.1.1 計算的基本概念................... 2

1.1.2計算模型的基本概念. . . . . . . .. .. . . . . 3
1.1.3RAM 模型........................ 3

1.1.4計算模型的選擇：易用性與精確性........................... 5
1.2 抽象算法設計...................... 6

1.2.1 算法問題規約..................... 6

1.2.2 算法正確性證明：數學歸納法....... 7

1.3 抽象算法分析...................... 8

1.3.1 抽象算法的性能指標. . . . . . . .. .. . . . . 8
1.3.2 最壞情況時間複雜度分析.......... 9

1.3.3 平均情況時間複雜度分析......... 10

1.4 習題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 11
第2 章從算法的視角重新審視數學的概念. . . . . . . . . . .. .. .. .. . . . . 14
2.1 數學運算背後的算法操作......... 14

2.1.1 取整. x . 和. x . . . . . . . . . . .. .. .. .. . 14
2.1.2 對數log n . . . . .. .. .. . . . . . . . . . .. .. . 14
2.1.3 階乘n!. . . . .. .. .. .. . . . . . . . . . .. .. . 15
2.1.4 常用級數求和.f (i). . . . . . .. .. .. .. 16
2.1.5 期望E[X] ....................... 18

2.2 函數的漸近增長率................ 19

2.3 “分治遞歸”求解................. 21

2.3.1 替換法. .. .. . . . . . . . . . .. .. .. .. . . . . 21
2.3.2 分治遞歸與遞歸樹.. . . . . . . . . . .. .. .21
2.3.3 Master 定理. .. .. .. . . . . . . . . . .. .. .. 22
2.4 習題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 23
第二部分從蠻力到分治
第3 章蠻力算法設計................... 31

3.1 蠻力選擇與查找. . . . . . .. .. .. . . . . . . . 31
3.2 蠻力排序.. . . . . . .. .. .. .. . . . . . . . . . .. 32
3.2.1選擇排序. . . .. .. .. .. . . . . . . . . . .. .. 32
3.2.2插入排序. . . .. .. .. .. . . . . . . . . . .. .. 33
3.3 習題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 35
第4 章分治排序.. .. .. .. . . . . . .. .. .. .. . . . 37
4.1 快速排序. . . . . . . .. .. .. .. . . . . . . . . . .. 37
4.1.1插入排序的不足. .. .. . . . . . . . . . .. .. 37
4.1.2快速排序的改進. .. .. . . . . . . . . . .. .. 38
4.1.3最壞情況時間複雜度分析......... 39

4.1.4基於遞歸方程的平均情況時間複雜度分析. . . . . . .. .. .. . . . . . . . . . . 40
4.1.5基於指標隨機變量的平均情況時間複雜度分析. . . . . . .. .. .. . . . . . . . . . . 41
4.2 合併排序.. . . . . . .. .. .. .. . . . . . . . . . .. 43
4.3 基於比較的排序的下界. .. .. .. . . . . . 44
4.3.1決策樹的引入. . . . . . .. .. .. . . . . . . . . 45
4.3.2比較排序的最壞情況時間複雜度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 45
4.3.3比較排序的平均情況時間複雜度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 46
4.4 習題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 48
第5 章線性時間選擇................... 50
5.1 期望線性時間選擇................ 50

5.1.1選擇算法設計. . . . . . .. .. .. . . . . . . . . 50
5.1.2選擇算法分析. . . . . . .. .. .. . . . . . . . . 51
5.2 最壞情況線性時間選擇. .. .. .. . . . . . 52
5.2.1選擇算法設計. . . . . . .. .. .. . . . . . . . . 52
5.2.2選擇算法分析. .. . . . . . . . . . .. .. . . . . 53
5.3 習題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 54
第6 章對數時間查找................... 57
6.1 折半查找.. .. . . . . . . . .. .. .. .. . . . . . . . 57
6.1.1經典折半查找. .. . . . . . . . .. .. .. . . . . 57
6.1.2查找峰值. . . . . . . .. .. .. . . . . . . . . . .. 58
6.1.3計算√N ........................ 59

6.2 平衡二叉搜索樹. . . . . . . . .. .. .. . . . . . 59
6.2.1二叉搜索樹及其平衡性........... 59

6.2.2紅黑樹的定義. .. . . . . . . . . . .. .. . . . . 60
6.2.3紅黑樹的平衡性. .. .. .. .. . . . . . . . . . 62
6.3 習題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 62
第7 章分治算法設計要素. . . . . . . . . . .. .. .65
7.1 分治算法的關鍵特徵. . . . . . . .. .. .. . 65
7.2 計算逆序對的個數................ 66

7.2.1依託於合併排序的逆序對計數.. .. . 66
7.2.2原地的逆序對計數.. .. . . . . . . . . . .. .67
7.3 整數乘法.. .. . . . . . . . .. .. .. .. . . . . . . . 68
7.3.1簡單分治. . . . . . . .. .. .. . . . . . . . . . .. 69
7.3.2更精細的分治.