算法設計與分析(第3版) 算法设计与分析(第3版)

第1篇算法設計與分析的基本概念

第1章算法的基本概念2 
1.1引言2 
1.1.1算法的定義和特徵2 
1.1.2算法設計的例子——窮舉法4 
1.1.3算法的複雜性分析7 
1.2算法的時間複雜性8 
1.2.1算法的輸入規模和運行時間的階8 
1.2.2運行時間的上界——O記號11 
1.2.3運行時間的下界——Ω記號12 
1.2. 4運行時間的準確界——Θ記號13 
1.2.5 O記號、Ω記號、Θ記號的性質17 
1.2.6複雜性類型和o記號18 
習題19 
參考文獻20 

第2章算法的複雜性分析21 
2.1常用的函數和公式21 
2.1.1整數函數21 
2.1.2對數函數22 
2.1.3排列、組合和二項式係數23 
2.1.4級數求和24 
2.2算法的時間複雜性分析25 
2.2.1循環次數的統計26 
2.2.2基本操作頻率的統計29 
2.2.3計算步的統計32 
2.3很好情況、最壞情況和平均情況分析33 
2.3.1很好情況、最壞情況和平均情況33
2.3.2很好情況和最壞情況分析34 
2.3.3平均情況分析37 

2.4用生成函數求解遞歸方程40 
2.4.1生成函數及其性質40 
2.4.2用生成函數求解遞歸方程43 
2.5用特徵方程求解遞歸方程46 
2.5.1 k階常係數線性齊次遞歸方程47 
2.5.2 k階常係數線性非齊次遞歸方程49 
2.6用遞推方法求解遞歸方程51 
2.6.1遞推52 
2.6.2用遞推法求解變係數遞歸方程52 
2.6.3換名54 
2.7算法的空間複雜性56 
2.8最優算法57 
習題58 
參考文獻60 

第2篇算法設計的基本技術

第3章排序問題和離散集合的操作62 
3.1合併排序62 
3.1.1合併排序算法的實現62 
3.1.2合併排序算法的分析64 
3.2基於堆的排序65 
3.2.1堆66 
3.2.2堆的操作67 
3.2.3堆的建立70 
3.2. 4堆的排序73 
3.3基數排序74 
3.3.1基數排序算法的思想方法74 
3.3.2基數排序算法的實現76 
3.3.3基數排序算法的分析78
3.4離散集合的Union_Find操作79 
3.4.1用於Union_Find操作的數據結構79 
3.4.2 union、find操作及路徑壓縮81 
習題84 
參考文獻85 

第4章遞歸和分治86 
4.1基於歸納的遞歸算法86 
4.1 .1基於歸納的遞歸算法的思想方法86 
4.1.2遞歸算法的例子87 
4.1.3排列問題的遞歸算法91 
4.1.4求數組主元素的遞歸算法95 
4.1.5整數劃分問題的遞歸算法98 
4.2分治法100 
4.2.1分治法的例子100 
4.2.2分治法的設計原理104 
4.2.3快速排序111 
4.2.4多項式乘積和大整數乘法116 
4.2.5平麵點集最接近點對問題123 
4.2.6選擇問題130 
4.2.7殘缺棋盤問題136 
習題141 
參考文獻143 

第5章貪婪法145 
5.1貪婪法概述146 
5.1.1貪婪法的設計思想146 
5.1.2貪婪法的例子——貨郎擔問題147 
5.2背包問題148 
5.2.1背包問題貪婪算法的實現148 
5.2.2背包問題貪婪算法的分析150
5.3單源最短路徑問題151 
5.3.1解最短路徑的狄斯奎諾算法151 
5.3.2狄斯奎諾算法的實現153 
5.3.3狄斯奎諾算法的分析155 
5.4最小花費生成樹問題156 
5.4 .1最小花費生成樹概述156 
5.4.2克魯斯卡爾算法157 
5.4.3普里姆算法161 
5.5霍夫曼編碼問題165 
5.5.1前綴碼和最優二叉樹165 
5.5.2霍夫曼編碼的實現169 
習題171 
參考文獻173 

第6章動態規劃174 
6.1動態規劃的思想方法174 
6.1.1動態規劃的最優決策原理174 
6.1.2動態規劃實例——貨郎擔問題175 
6.2多段圖的最短路徑問題177 
6.2.1多段圖的決策過程178 
6.2.2多段圖動態規划算法的實現180 
6.3資源分配問題181 
6.3.1資源分配的決策過程182 
6.3.2資源分配算法的實現184 
6.4設備更新問題187 
6.4 .1設備更新問題的決策過程187 
6.4.2設備更新算法的實現190 
6.5最長公共子序列問題192 
6.5.1最長公共子序列的搜索過程192
6.5.2最長公共子序列算法的實現195 
6.6 0/1背包問題196 
6.6.1 0/1背包問題的求解過程196 
6.6.2 0/1背包問題的實現198 
6.7 RNA很大鹼基對匹配問題199 
6.7.1 RNA很大鹼基對匹配的搜索過程200 
6.7.2 RNA很大鹼基對匹配算法的實現203 
習題205 
參考文獻207 

第7章回溯208 
7.1回溯法的思想方法208 
7.1.1問題的解空間和狀態空間樹208 
7.1.2狀態空間樹的動態搜索209 
7.1.3回溯法的一般性描述211 
7.2 n皇后問題213 
7.2.1 n皇后問題的求解過程213 
7.2.2 n皇后問題算法的實現215 
7.3圖的著色問題217 
7.3.1圖著色問題的求解過程218 
7.3.2圖的m著色問題算法的實現220 
7.4哈密爾頓迴路問題222 
7.4.1哈密爾頓迴路的求解過程222 
7.4.2哈密爾頓迴路算法的實現224 
7.5 0/1背包問題225 
7.5.1回溯法解0/1背包問題的求解過程226 
7.5.2回溯法解0/1背包問題算法的實現229 
7.6回溯法的效率分析231
習題234 
參考文獻235 

第8章分支與限界236 
8.1分支與限界法的基本思想236 
8.2作業分配問題238 
8.2.1分支限界法解作業分配問題的思想方法238 
8.2.2分支限界法解作業分配問題算法的實現241 
8.3單源最短路徑問題244 
8.3.1分支限界法解單源最短路徑問題的思想方法244 
8.3.2分支限界法解單源最短路徑問題算法的實現246 
8.4 0/1背包問題248 
8.4.1分支限界法解0/1背包問題的思想方法和求解過程249 
8.4.2 0/1背包問題分支限界算法的實現251 
8.5貨郎擔問題254 
8.5.1費用矩陣的特性及歸約254 
8.5 .2界限的確定和分支的選擇256 
8.5.3貨郎擔問題的求解過程259 
8.5.4幾個輔助函數的實現262 
8.5.5貨郎擔問題分支限界算法的實現268 
習題271 
參考文獻272 

第9章隨機算法273 
9.1隨機算法概述273 
9.1.1隨機算法的類型273 
9.1.2隨機數發生器274 
9.2舍伍德算法275 
9.2.1隨機快速排序算法275
9.2.2隨機選擇算法277 
9.3拉斯維加斯算法280 
9.3.1字符串匹配280 
9.3.2整數因子284 
9.4蒙特卡羅算法285 
9.4.1數組的主元素問題285 
9.4.2素數測試287 
習題290 
參考文獻291 

第3篇計算機應用領域的一些基法

第10章圖和網絡問題294 
10.1圖的遍歷294 
10.1.1圖的深度優先搜索遍歷294 
10.1.2圖的廣度優先搜索遍歷299 
10.1.3無向圖的接合點301 
10.1.4有向圖的強連通分支305 
10.2網絡流308 
10.2.1網絡流的概念308 
10.2.2 Ford_Fulkerson方法和很大容量增廣312 
10.2.3最短路徑增廣315 
10.3二分圖的很大匹配問題320 
10.3.1預備知識321 
10.3.2二分圖很大匹配的匈牙利樹方法323 
習題329 
參考文獻331 

第11章計算幾何問題332 
11.1引言332 
11.2平麵線段的交點問題334 
11.2.1尋找平麵線段交點的思想方法335
11.2.2尋找平麵線段交點的實現337 
11.3凸殼問題342 
11.3.1凸殼問題的格雷厄姆掃描法343 
11.3.2格雷厄姆掃描法的實現344 
11.4平麵點集的直徑問題346 
11.4.1求取平麵點集直徑的思想方法346 
11.4.2平麵點集直徑的求取348 
習題350 
參考文獻351 

第4篇算法設計與分析的一些理論問題

第12章NP完全問題354 
12.1 P類和NP類問題355 
12.1.1 P類問題355 
12.1.2 NP類問題356 
12.2 NP完全問題358 
12.2.1 NP完全問題的定義358 
12.2.2幾個典型的NP完全問題360 
12.2.3其他NP完全問題366 
12.3 co_NP類和NPI類問題366 
習題369 
參考文獻370 

第13章計算複雜性371 
13.1計算模型371 
13.1.1圖靈機的基本模型371 
13.1.2 k帶圖靈機和時間複雜性374 
13.1.3離線圖靈機和空間複雜性376 
13.1.4可滿足性問題和Cook定理379 
13.2複雜性類型之間的關係381
13.2.1時間複雜性和空間複雜性的關係382 
13.2.2時間譜系定理和空間譜系定理384 
13.2.3填充變元389 
13.3歸約性關係391 
13.4完備性394 
13.4.1 NLOGSPACE完全問題394 
13.4. 2 PSPACE完全問題和P完全問題396 
習題397 
參考文獻398 

第14章下界399 
14.1平凡下界399 
14.2判定樹模型399 
14.2.1檢索問題400 
14.2.2排序問題401 
14.3代數判定樹模型402 
14.3.1代數判定樹模型及下界定理402 
14.3.2極點問題404 
14.4線性時間歸約405 
14.4.1凸殼問題406 
14.4.2多項式插值問題406 
習題408 
參考文獻408 

第15章近似算法409 
15.1近似算法的性能409 
15.2裝箱問題410 
15.2.1首次適宜算法411 
15.2.2最適宜算法及其他算法412 
15.3頂點覆蓋問題414 
15.4貨郎擔問題416 
15.4.1歐幾里得貨郎擔問題417
15.4.2一般的貨郎擔問題419 
15.5多項式近似方案419 
15.5.1 0/1背包問題的多項式近似方案420 
15.5.2子集求和問題的完全多項式近似方案423 
習題425 
參考文獻426 

參考文獻427