算法設計與分析(2016年清華大學出版社出版的圖書)

算法設計與分析(2016年清華大學出版社出版的圖書)

本詞條是多義詞,共14個義項
更多義項 ▼ 收起列表 ▲

《算法設計與分析》是2016年清華大學出版社出版的圖書,作者是徐義春、萬書振、解德祥。

基本介紹

  • 中文名:算法設計與分析
  • 作者:徐義春、萬書振、解德祥
  • 出版時間:2016年7月
  • 出版社: 清華大學出版社
  • 頁數:150 頁 
  • ISBN: 9787302437895
  • 定價:29.00 元
  • 開本:16 開
  • 裝幀:平裝
  • 叢書系列:高等學校計算機專業規劃教材 
內容簡介,圖書目錄,

內容簡介

本書涵蓋了常見計算機算法設計和分析的思路和方法,內容包括算法概論、遞推與遞歸、分治法、動態規劃法、搜尋方法、近似算法、隨機算法等,最後提供一些高級數據結構的介紹,以幫助實現效率更高的算法。本書重視算法思路的總結以及方法的正確性證明,以深入淺出的方式引導學生學習教材內容,既具有嚴謹性,又具有簡明性。全書為絕大多數算法提供了可以直接驗證的C/C++代碼。本書適合作為高等院校計算機相關專業的教材,也可作為編程競賽的輔導用書。

圖書目錄

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函式的階與漸進性分析7
1.5.1複雜性函式的階7
1.5.2函式的漸進性階的比較8
1.5.3函式的漸進性階的運算8
1.5.4函式的漸進性表示與函式集合9
1.6本章習題9
第2章遞推與遞歸/10
2.1遞推關係與遞推算法10
2.2遞歸函式21
2.3遞歸函式的執行過程22
2.4遞歸函式的時間複雜性與遞歸樹24
2.5估計遞歸函式的複雜度的主方法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函式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章動態規劃/45
4.1遞歸方法中的重複計算45
4.2最長公共子序列47
4.2.1問題描述47
4.2.2遞推關係分析47
4.2.3算法實現48
4.3最大子段和49
4.3.1問題描述49
4.3.2遞推分析49
4.3.3算法實現50
4.4矩陣連乘問題51
4.4.1問題描述51
4.4.2遞推分析52
4.4.3算法實現52
4.5數據壓縮問題53
4.5.1問題描述53
4.5.2遞推分析54
4.5.3算法實現55
4.601背包問題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算法實現58
4.8最優二叉搜尋樹問題59
4.8.1問題描述59
4.8.2遞推分析60
4.8.3算法實現60
4.9本章習題61
第5章貪心算法/63
5.1活動安排問題64
5.1.1問題描述64
5.1.2問題分析64
5.1.3算法實現64
5.2服務調度問題65
5.2.1問題描述65
5.2.2問題分析66
5.2.3算法實現66
5.3最遲時間限制服務調度問題67
5.3.1問題描述67
5.3.2問題分析67
5.3.3算法實現69
5.4ε背包問題70
5.4.1問題描述70
5.4.2問題分析70
5.4.3算法實現70
5.5最小生成樹問題72
5.5.1問題描述72
5.5.2Prim算法原理72
5.5.3Prim算法實現72
5.5.4Kruskal算法原理74
5.5.5Kruskal算法實現75
5.6單源最短路徑問題77
5.6.1問題描述77
5.6.2Dijkstra算法原理77
5.6.3Dijkstra算法實現78
5.7本章習題80
第6章深度優先搜尋/81
6.1樹的搜尋81
6.1.1解空間、子集樹與排列樹81
6.1.2深度優先搜尋82
6.1.3背包問題的回溯算法84
6.1.4n皇后問題86
6.1.5旅行推銷員問題88
6.1.6最大團問題90
6.1.7圖著色問題91
6.1.8連續郵資問題92
6.2圖的搜尋94
6.2.1狼羊過河問題95
6.2.2分油問題98
6.3本章習題100
第7章寬度優先搜尋/102
7.1寬度優先搜尋一般形式102
7.1.1基本算法102
7.1.2算法性能103
7.1.3算法設計要素104
7.2樹的分支定界法104
7.2.1背包問題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.2背包問題的0.5近似算法117
8.2.1貪心算法117
8.2.20.5近似算法118
8.3背包問題的(1ε)近似算法118
8.3.1一種動態規划算法118
8.3.2(1ε)近似算法120
8.4旅行推銷員問題的2近似算法121
8.5本章習題124
第9章隨機算法/126
9.1數值型隨機算法126
9.1.1數值積分隨機算法126
9.1.2隨機計數器127
9.2蒙特卡洛算法128
9.2.1矩陣乘法驗證128
9.2.2質數檢測129
9.3Las Vegas算法132
9.3.1n皇后問題132
9.3.2通用散列算法134
9.4本章習題135
第10章高級數據結構(一)/136
10.1線段樹136
10.1.1線段樹的套用背景136
10.1.2線段樹的結構136
10.1.3線段樹的性質137
10.1.4線段樹的基本存儲結構138
10.1.5線段樹的基本操作138
10.1.6線段樹的套用舉例140
10.2樹狀數組142
10.2.1樹狀數組的套用背景142
10.2.2樹狀數組的定義142
10.2.3樹狀數組的實現143
10.2.4樹狀數組的套用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章高級數據結構(二)/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樹鏈剖分的思想和性質168
11.3.2樹鏈剖分的實現及套用169
11.4本章習題177
參考文獻/178

相關詞條

熱門詞條

聯絡我們