算法設計基礎

汪江樺

中國科學院大學博士、副教授，主要研究方向為信息分析與數據挖掘，
發表核心期刊級以上級別學術論文10餘篇，主持省部級項目3項，
作為主研人員參與國家自然科學基金項目2項。

湯建國

電子科技大學博士、副教授，主要研究方向為粒計算與機器學習，
發表論文20餘篇，其中SCI檢索論文4篇，EI檢索論文10餘篇，中文核心期刊論文數篇；
主持國家自然科學基金項目2項，各類省部級項目5項。
 

目錄：
第1章概論1
1.1算法的基本概念2
1.1.1算法的含義2
1.1.2算法的作用3
1.1.3算法的特性4
1.1.4算法的描述6
1.1.5算法設計的步驟8
1.2算法分析9
1.2.1算法的時間複雜度與大O表示法9
1.2.2算法的時間複雜度分析12
1.2.3算法的空間複雜度分析15
1.3算法設計示例16
1.4本章小結20
習題1 20
實訓1 22

第2章蠻力法25
2.1蠻力法概述26
2.1.1蠻力法的基本思想26
2.1.2蠻力法解題格式28
2.2蠻力法的應用31
2.2.1順序查找31
2.2.2冒泡排序32
2.2.3直接選擇排序34
2.2.4直接插入排序36
2.3蠻力法的分析與設計37
2.3.1百錢百雞問題38
2.3.2解數字謎39
2.3.3獄吏問題41
2.4蠻力法示例43
2.5本章小結49
習題2 49
實訓２ 50

第3章分治法53
3.1遞歸技術54
3.1.1遞歸的定義54
3.1.2遞歸的執行過程55
3.1.3遞歸的設計方法56
3.1.4遞歸技術效率分析59
3.1.5遞歸過程60
3.2遞歸設計實例63
3.3分治法概述66
3.3.1分治法的基本思想67
3.3.2快速排序69
3.3.3二路歸併排序71
3.3.4二分查找73
3.4分治法示例74
3.5本章小結77
習題3 78
實訓3 79

第4章貪心法81
4.1貪心法概述82
4.1.1貪心法的基本思想82
4.1.2活動安排問題83
4.1.3幣種統計問題86
4.2貪心法的應用87
4.2.1哈夫曼樹87
4.2. 2哈夫曼編碼88
4.2.3 *小生成樹90
4.2.4單源*短路徑92
4.3貪心法的分析與設計94
4.3.1背包問題94
4.3.2田忌賽馬問題96
4.3.3多機調度問題98
4.4貪心法示例99
4.5本章小結102
習題4 102
實訓4 104

第5章動態規劃法105
5.1動態規劃法概述106
5.1.1動態規劃法的基本思想106
5.1.2 *優決策表106
5.2動態規劃法的應用112
5.2.1斐波那契數列112
5.2.2數字塔問題114
5.2.3湊硬幣問題115
5.2.4 0-1背包問題117
5.3動態規劃法的分析與設計120
5.4動態規劃法示例124
5.5本章小結126
習題5 126
實訓5 128

第6章回溯法131
6.1回溯法概述132
6.1.1問題的解空間132
6.1.2回溯法的基本思想133
6.1.3 0-1背包問題134
6.2回溯法示例137
6.3本章小結147
習題6 147
實訓6 149

第7章分支限界法151
7.1分支限界法概述152
7.1.1分支限界法的基本思想152
7.1.2 0-1背包問題153
7.2分支限界法示例158
7.3本章小結163
習題7 163
實訓7 164