《算法分析與設計技巧》是西安電子科技大學出版社出版的一本圖書。
基本介紹
- 中文名：算法分析與設計技巧
- 作者：司存瑞、司棟、蘇秋萍、艾慶興
- 出版社：西安電子科技大學出版社
- 出版時間：2016年01月
- ISBN：9787560639000
內容簡介,圖書目錄,
內容簡介
全書共分5章, 第1章介紹了算法的概念與評價, 第2章介紹了遞歸法、分治法、貪心法、搜尋法和回溯法等常用算法的概念、基本思想及其套用, 第3章對動態規划算法的基本思想與概念、解題方法與步驟及其簡單套用與最佳化等進行了全面深入的研究, 第4章著重討論了搜尋算法中的最佳化技巧, 第5章對圖上的算法: 並查集、生成樹、最短路、強連通分量、2-SAT、差分約束、二分圖以及網路流進行了全面梳理與分析。
圖書目錄
第1章 算法的概念 1
1.1 算法的概念和描述 1
1.1.1 算法的概念 1
1.1.2 算法的描述 3
1.2 算法的時間複雜度和空間複雜度 4
1.2.1 算法的評價 4
1.2.2 算法的時間複雜度 5
1.2.3 算法的空間複雜度 11
習題1 12
第2章 常用算法 18
2.1 遞歸法 18
2.1.1 遞歸的概念與基本思想 18
2.1.2 遞歸法的套用 19
2.2 分治法 23
2.2.1 分治的概念與基本思想 23
2.2.2 分治法的套用 27
2.3 貪心法 34
2.3.1 貪心的概念與基本思想 34
2.3.2 貪心法的套用 34
2.4 搜尋法與回溯法 42
2.4.1 搜尋與回溯的概念與基本思想 42
2.4.2 搜尋法與回溯法的套用 43
習題2 48
第3章 動態規劃 53
3.1 動態規劃的基本思想與概念 53
3.1.1 動態規劃的基本思想 53
3.1.2 動態規劃的概念 55
3.1.3 動態規劃的常用名詞 56
3.1.4 動態規划算法的基本步驟 56
3.2 動態規劃的簡單套用 58
3.2.1 線性動態規劃 58
3.2.2 背包動態規劃 69
3.2.3 區間動態規劃 79
3.2.4 格線動態規劃 82
3.3 動態規劃的深入研究 88
3.3.1 樹形動態規劃 88
3.3.2 狀態壓縮動態規劃 95
3.3.3 基於連通性的狀態壓縮動態規劃 104
3.3.4 數位計數類動態規劃 112
3.4 動態規劃的最佳化方法 115
3.4.1 減少狀態總數 115
3.4.2 利用數據結構加速狀態轉移過程 120
3.4.3 四邊形不等式最佳化 124
3.4.4 斜率最佳化 126
習題3 129
第4章 搜尋算法中的最佳化技巧 138
4.1 搜尋中的剪枝技巧 138
4.2 選擇合適的搜尋方向 158
4.3 A*算法 171
4.4 跳舞鏈 181
4.5 搜尋還是動態規劃 194
習題4 205
第5章 圖上的算法 209
5.1 並查集 209
5.2 生成樹 220
5.3 最短路 230
5.4 強連通分量 239
5.5 2SAT 250
5.6 差分約束 261
5.7 二分圖 266
5.8 網路流 279
5.8.1 網路流的概念 279
5.8.2 最大流的求解方法 280
習題5 299
參考文獻 306
