算法設計與分析

本書涵蓋了常見計算機算法設計和分析的思路和方法，內容包括算法概論、遞推與遞歸、分治法、動態規劃法、搜索方法、近似算法、隨機算法等，最後提供一些高級數據結構的介紹，以幫助實現效率更高的算法。本書重視算法思路的總結以及方法的正確性證明，以深入淺出的方式引導學生學習教材內容，既具有嚴謹性，又具有簡明性。全書為絕大多數算法提供了可以直接驗證的C/C++代碼。本書適合作為高等院校計算機相關專業的教材，也可作為編程競賽的輔導用書。 ^[3] 

1.1算法的概念1

1.2算法的表達1

1.2.1自然語言1

1.2.2結構化圖形工具2

1.2.3計算機高級語言3

1.3算法的評價3

1.3.1算法的正確性4

1.3.2算法的空間複雜性5

1.3.3算法的時間複雜性5

1.4最差時間複雜性和平均時間複雜性6

1.5函數的階與漸進性分析7

1.5.1複雜性函數的階7

1.5.2函數的漸進性階的比較8

1.5.3函數的漸進性階的運算8

1.5.4函數的漸進性表示與函數集合9

1.6本章習題9

第2章遞推與遞歸/10

2.1遞推關係與遞推算法10

2.2遞歸函數21

2.3遞歸函數的執行過程22

2.4遞歸函數的時間複雜性與遞歸樹24

2.5估計遞歸函數的複雜度的主方法26

2.6本章習題27

第3章分治法/29

3.1二分搜索算法29

3.1.1問題分析與算法設計29

3.1.2時間複雜性分析30

〖1〗算法設計與分析目錄[3]〖3〗3.2合併排序算法30

3.2.1問題分析與算法設計31

3.2.2Merge函數31

3.2.3時間複雜性分析32

3.3快速排序算法32

3.3.1固定主元的快速排序32

3.3.2隨機選主元的快速排序34

3.4搜索第k元35

3.4.1平均時間為線性36

3.4.2最差時間為線性37

3.5最近點對39

3.5.1一維空間中的最近點對39

3.5.2二維空間中的最近點對40

3.6本章習題44

第4章動態規劃/45

4.1遞歸方法中的重複計算45

4.2最長公共子序列47

4.2.1問題描述47

4.2.2遞推關係分析47

4.2.3算法實現48

4.3最大子段和49

4.3.1問題描述49

4.3.2遞推分析49

4.3.3算法實現50

4.4矩陣連乘問題51

4.4.1問題描述51

4.4.2遞推分析52

4.4.3算法實現52

4.5數據壓縮問題53

4.5.1問題描述53

4.5.2遞推分析54

4.5.3算法實現55

4.601揹包問題56

4.6.1問題描述56

4.6.2遞推分析56

4.6.3算法描述56

4.7消費和儲蓄問題57

4.7.1問題描述57

4.7.2遞推分析58

4.7.3算法實現58

4.8最優二叉搜索樹問題59

4.8.1問題描述59

4.8.2遞推分析60

4.8.3算法實現60

4.9本章習題61

第5章貪心算法/63

5.1活動安排問題64

5.1.1問題描述64

5.1.2問題分析64

5.1.3算法實現64

5.2服務調度問題65

5.2.1問題描述65

5.2.2問題分析66

5.2.3算法實現66

5.3最遲時間限制服務調度問題67

5.3.1問題描述67

5.3.2問題分析67

5.3.3算法實現69

5.4ε揹包問題70

5.4.1問題描述70

5.4.2問題分析70

5.4.3算法實現70

5.5最小生成樹問題72

5.5.1問題描述72

5.5.2Prim算法原理72

5.5.3Prim算法實現72

5.5.4Kruskal算法原理74

5.5.5Kruskal算法實現75

5.6單源最短路徑問題77

5.6.1問題描述77

5.6.2Dijkstra算法原理77

5.6.3Dijkstra算法實現78

5.7本章習題80

第6章深度優先搜索/81

6.1樹的搜索81

6.1.1解空間、子集樹與排列樹81

6.1.2深度優先搜索82

6.1.3揹包問題的回溯算法84

6.1.4n皇后問題86

6.1.5旅行推銷員問題88

6.1.6最大團問題90

6.1.7圖着色問題91

6.1.8連續郵資問題92

6.2圖的搜索94

6.2.1狼羊過河問題95

6.2.2分油問題98

6.3本章習題100

第7章寬度優先搜索/102

7.1寬度優先搜索一般形式102

7.1.1基本算法102

7.1.2算法性能103

7.1.3算法設計要素104

7.2樹的分支定界法104

7.2.1揹包問題104

7.2.2旅行推銷員問題107

7.3圖的分支定界法109

7.3.1狼羊過河問題109

7.3.2分油問題112

7.4本章習題115

第8章近似算法/116

8.1近似算法的概念116

8.2揹包問題的0.5近似算法117

8.2.1貪心算法117

8.2.20.5近似算法118

8.3揹包問題的(1ε)近似算法118

8.3.1一種動態規劃算法118

8.3.2(1ε)近似算法120

8.4旅行推銷員問題的2近似算法121

8.5本章習題124

第9章隨機算法/126

9.1數值型隨機算法126

9.1.1數值積分隨機算法126

9.1.2隨機計數器127

9.2蒙特卡洛算法128

9.2.1矩陣乘法驗證128

9.2.2質數檢測129

9.3Las Vegas算法132

9.3.1n皇后問題132

9.3.2通用散列算法134

9.4本章習題135

第10章高級數據結構（一）/136

10.1線段樹136

10.1.1線段樹的應用背景136

10.1.2線段樹的結構136

10.1.3線段樹的性質137

10.1.4線段樹的基本存儲結構138

10.1.5線段樹的基本操作138

10.1.6線段樹的應用舉例140

10.2樹狀數組142

10.2.1樹狀數組的應用背景142

10.2.2樹狀數組的定義142

10.2.3樹狀數組的實現143

10.2.4樹狀數組的應用143

10.3伸展樹144

10.3.1伸展樹的應用背景144

10.3.2伸展樹的定義及特點144

10.3.3伸展樹的主要操作145

10.4Treap151

10.4.1概述151

10.4.2Treap基本操作151

10.4.3Treap的其他操作153

10.4.4總結155

10.5本章習題156

第11章高級數據結構（二）/157

11.1塊狀鏈表157

11.1.1塊狀鏈表基本思想157

11.1.2塊狀鏈表基本操作157

11.1.3塊狀鏈表的應用162

11.2後綴樹163

11.2.1模式匹配問題163

11.2.2後綴樹簡介163

11.2.3後綴樹定義163

11.2.4後綴樹的構建164

11.2.5後綴樹的應用166

11.3樹鏈剖分168

11.3.1樹鏈剖分的思想和性質168

11.3.2樹鏈剖分的實現及應用169

11.4本章習題177

參考文獻/178 ^[3]