●第1章算法的概念
1.1算法的概念和描述
1.1.1算法的概念
1.1.2算法的描述
1.2算法的時間復雜度和空間復雜度
1.2.1算法的評價
1.2.2算法的時間復雜度
1.2.3算法的空間復雜度
習題1
第2章常用算法
2.1遞歸法
2.1.1遞歸的概念與基本思想
2.1.2遞歸法的應用
2.2分治法
2.2.1分治的概念與基本思想
2.2.2分治法的應用
2.3貪心法
2.3.1貪心的概念與基本思想
2.3.2貪心法的應用
2.4搜索法與回溯法
2.4.1搜索與回溯的概念與基本思想
2.4.2搜索法與回溯法的應用
習題2
第3章動態規劃
3.1動態規劃的基本思想與概念
3.1.1動態規劃的基本思想
3.1.2動態規劃的概念
3.1.3動態規劃的常用名詞
3.1.4動態規劃算法的基本步驟
3.2動態規劃的簡單應用
3.2.1線性動態規劃
3.2.2背包動態規劃
3.2.3區間動態規劃
3.2.4網格動態規劃
3.3動態規劃的深入研究
3.3.1樹形動態規劃
3.3.2狀態壓縮動態規劃
3.3.3基於連通性的狀態壓縮動態規劃
3.3.4數位計數類動態規劃
3.4動態規劃的優化方法
3.4.1減少狀態總數
3.4.2利用數據結構加速狀態轉移過程
3.4.3四邊形不等式優化
3.4.4斜率優化
習題3
第4章搜索算法中的優化技巧
4.1搜索中的剪枝技巧
4.2選擇合適的搜索方向
4.3A*算法
4.4跳舞鏈
4.5搜索還是動態規劃
習題4
第5章圖上的算法
5.1並查集
5.2生成樹
5.3最短路
5.4強連通分量
5.52—SAT
5.6差分約束
5.7二分圖
5.8網絡流
5.8.1網絡流的概念
5.8.2優選流的求解方法
習題5
參考文獻
《高等學校電子信息類專業"十三五"規劃教材:算法分析與設計技巧》集作者多年的教學經驗及國內外關於算法分析與設計的近期新內容於一體。全書共分5章,第1章介紹了算法的概念與評價,第2章介紹了遞歸法、分治法、貪心法、搜索法和回溯法等常用算法的概念、基本思想及其應用,第3章對動態規劃算法的基本思想與概念、解題方法與步驟及其簡單應用與優化等進行了全面深入的研究,第4章著重討論了搜索算法中的優化技巧,第5章對圖上的算法:並查集、生成樹、最短路、強連通分量、2—SAT、差分約束、二分圖以及網絡流進行了全面梳理與分析。為了使學生盡快掌握算法分析與設計技巧,除第1章外,其餘各章特意從近年來國際、國內信息學競賽試題中精選了若干試題作為例題,對這些例題從算法分析、設計技巧到代碼實現均給出了完整的解決方案。相信這些內容會給讀者帶來諸多方便。