算法設計與分析（高等學校計算機專業(yè)規(guī)劃教材）
定 價：29 元
- 作者：徐義春、萬書振、解德祥
- 出版時間：2016/7/14
- ISBN：9787302437895
- 出 版 社：清華大學出版社
- 中圖法分類：TP301.6
- 頁碼：150
- 紙張：膠版紙
- 版次：1
- 開本：16K
本書涵蓋了常見計算機算法設計和分析的思路和方法，內(nèi)容包括算法概論、遞推與遞歸、分治法、動態(tài)規(guī)劃法、搜索方法、近似算法、隨機算法等，最后提供一些高級數(shù)據(jù)結構的介紹，以幫助實現(xiàn)效率更高的算法。本書重視算法思路的總結以及方法的正確性證明，以深入淺出的方式引導學生學習教材內(nèi)容，既具有嚴謹性，又具有簡明性。全書為絕大多數(shù)算法提供了可以直接驗證的C/C++代碼。本書適合作為高等院校計算機相關專業(yè)的教材，也可作為編程競賽的輔導用書。
（1）涵蓋了常見計算機算法設計和分析的思路和方法，內(nèi)容包括算法概論、遞推與遞歸、分治法、動態(tài)規(guī)劃法、搜索方法、近似算法、隨機算法等
�。�2）重視算法思路的總結以及方法的正確性證明，以深入淺出的方式引導學生學習教材內(nèi)容，既具有嚴謹性，又具有簡明性。
（3）為絕大多數(shù)算法提供了C/C++代碼實現(xiàn)。
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函數(shù)的階與漸進性分析7
1.5.1復雜性函數(shù)的階7
1.5.2函數(shù)的漸進性階的比較8
1.5.3函數(shù)的漸進性階的運算8
1.5.4函數(shù)的漸進性表示與函數(shù)集合9
1.6本章習題9
第2章遞推與遞歸/10
2.1遞推關系與遞推算法10
2.2遞歸函數(shù)21
2.3遞歸函數(shù)的執(zhí)行過程22
2.4遞歸函數(shù)的時間復雜性與遞歸樹24
2.5估計遞歸函數(shù)的復雜度的主方法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函數(shù)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章動態(tài)規(guī)劃/45
4.1遞歸方法中的重復計算45
4.2最長公共子序列47
4.2.1問題描述47
4.2.2遞推關系分析47
4.2.3算法實現(xiàn)48
4.3最大子段和49
4.3.1問題描述49
4.3.2遞推分析49
4.3.3算法實現(xiàn)50
4.4矩陣連乘問題51
4.4.1問題描述51
4.4.2遞推分析52
4.4.3算法實現(xiàn)52
4.5數(shù)據(jù)壓縮問題53
4.5.1問題描述53
4.5.2遞推分析54
4.5.3算法實現(xiàn)55
4.601背包問題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算法實現(xiàn)58
4.8最優(yōu)二叉搜索樹問題59
4.8.1問題描述59
4.8.2遞推分析60
4.8.3算法實現(xiàn)60
4.9本章習題61
第5章貪心算法/63
5.1活動安排問題64
5.1.1問題描述64
5.1.2問題分析64
5.1.3算法實現(xiàn)64
5.2服務調(diào)度問題65
5.2.1問題描述65
5.2.2問題分析66
5.2.3算法實現(xiàn)66
5.3最遲時間限制服務調(diào)度問題67
5.3.1問題描述67
5.3.2問題分析67
5.3.3算法實現(xiàn)69
5.4ε背包問題70
5.4.1問題描述70
5.4.2問題分析70
5.4.3算法實現(xiàn)70
5.5最小生成樹問題72
5.5.1問題描述72
5.5.2Prim算法原理72
5.5.3Prim算法實現(xiàn)72
5.5.4Kruskal算法原理74
5.5.5Kruskal算法實現(xiàn)75
5.6單源最短路徑問題77
5.6.1問題描述77
5.6.2Dijkstra算法原理77
5.6.3Dijkstra算法實現(xiàn)78
5.7本章習題80
第6章深度優(yōu)先搜索/81
6.1樹的搜索81
6.1.1解空間、子集樹與排列樹81
6.1.2深度優(yōu)先搜索82
6.1.301背包問題的回溯算法84
6.1.4n皇后問題86
6.1.5旅行推銷員問題88
6.1.6最大團問題90
6.1.7圖著色問題91
6.1.8連續(xù)郵資問題92
6.2圖的搜索94
6.2.1狼羊過河問題95
6.2.2分油問題98
6.3本章習題100
第7章寬度優(yōu)先搜索/102
7.1寬度優(yōu)先搜索一般形式102
7.1.1基本算法102
7.1.2算法性能103
7.1.3算法設計要素104
7.2樹的分支定界法104
7.2.101背包問題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.201背包問題的0.5近似算法117
8.2.1貪心算法117
8.2.20.5近似算法118
8.301背包問題的(1ε)近似算法118
8.3.1一種動態(tài)規(guī)劃算法118
8.3.2(1ε)近似算法120
8.4旅行推銷員問題的2近似算法121
8.5本章習題124
第9章隨機算法/126
9.1數(shù)值型隨機算法126
9.1.1數(shù)值積分隨機算法126
9.1.2隨機計數(shù)器127
9.2蒙特卡洛算法128
9.2.1矩陣乘法驗證128
9.2.2質(zhì)數(shù)檢測129
9.3Las Vegas算法132
9.3.1n皇后問題132
9.3.2通用散列算法134
9.4本章習題135
第10章高級數(shù)據(jù)結構（一）/136
10.1線段樹136
10.1.1線段樹的應用背景136
10.1.2線段樹的結構136
10.1.3線段樹的性質(zhì)137
10.1.4線段樹的基本存儲結構138
10.1.5線段樹的基本操作138
10.1.6線段樹的應用舉例140
10.2樹狀數(shù)組142
10.2.1樹狀數(shù)組的應用背景142
10.2.2樹狀數(shù)組的定義142
10.2.3樹狀數(shù)組的實現(xiàn)143
10.2.4樹狀數(shù)組的應用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章高級數(shù)據(jù)結構（二）/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樹鏈剖分的思想和性質(zhì)168
11.3.2樹鏈剖分的實現(xiàn)及應用169
11.4本章習題177
參考文獻/178
書單推薦
