算法詳解 卷2 圖算法和數(shù)據(jù)結(jié)構(gòu)
定 價(jià)：49 元
- 作者：[美]蒂姆·拉夫加登（Tim Roughgarden）
- 出版時(shí)間：2020/6/1
- ISBN：9787115526038
- 出 版 社：人民郵電出版社
- 中圖法分類：TP301.6
- 頁碼：188
- 紙張：
- 版次：01
- 開本：小16開
算法詳解系列圖書共有4卷，本書是第2卷—圖算法和數(shù)據(jù)結(jié)構(gòu)。本書共有6章，主要介紹了3個(gè)主題，分別是圖的搜索和應(yīng)用、最短路徑以及數(shù)據(jù)結(jié)構(gòu)。附錄簡(jiǎn)單回顧了漸進(jìn)性表示法。本書的每一章均有小測(cè)驗(yàn)、章末習(xí)題，這為讀者的自我檢查以及進(jìn)一步學(xué)習(xí)提供了方便。
本書提供了豐富而實(shí)用的資料，能夠幫助讀者提升算法思維能力。本書適合計(jì)算機(jī)專業(yè)的高校教師和學(xué)生，想要培養(yǎng)和訓(xùn)練算法思維和計(jì)算思維的IT專業(yè)人士，以及正在準(zhǔn)備面試的應(yīng)聘者和面試官閱讀參考。
算法是計(jì)算機(jī)科學(xué)的核心與靈魂。算法的應(yīng)用范圍極廣，網(wǎng)絡(luò)路由、計(jì)算基因組學(xué)、公鑰加密學(xué)和數(shù)據(jù)庫系統(tǒng)等的實(shí)現(xiàn)都需要算法。研究算法可以幫助我們成為更優(yōu)秀的程序員，可以讓我們具有更縝密的思維，并成功應(yīng)對(duì)各種場(chǎng)合的技術(shù)面試。
這是一本非常容易上手的算法入門圖書，它可作為程序員的學(xué)習(xí)用書，也適合想要學(xué)習(xí)算法和想提升算法思維能力的讀者閱讀。
本書主要包括以下內(nèi)容：
圖的搜索和應(yīng)用；
散列表；
最短路徑算法；
布隆過濾器；
隨機(jī)化算法；
堆；
搜索樹。
蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大學(xué)計(jì)算機(jī)科學(xué)系的教授,也是該校管理科學(xué)和工程系的客座教授，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第一卷，基于他從2012年開始定期舉行的在線算法課程編寫。
第1章 圖的基礎(chǔ)知識(shí) 1
1.1 基本術(shù)語 1
1.2 圖的一些應(yīng)用 2
1.3 圖形的度量 3
1.3.1 圖的邊數(shù)量 3
1.3.2 稀疏圖和稠密圖 4
1.3.3 小測(cè)驗(yàn)1.1的答案 5
1.4 圖的表示方法 7
1.4.1 鄰接列表 7
1.4.2 鄰接矩陣 8
1.4.3 圖的表示形式之間的比較 9
1.4.4 小測(cè)驗(yàn)1.2和小測(cè)驗(yàn)1.3的答案 10
1.5 本章要點(diǎn) 11
1.6 章末習(xí)題 12
第2章 圖的搜索及其應(yīng)用 14
2.1 概述 14
2.1.1 一些應(yīng)用 15
2.1.2 零代價(jià)的基本算法 16
2.1.3 通用的圖搜索算法 17
2.1.4 寬度優(yōu)先的搜索和深度優(yōu)先的搜索 20
2.1.5 GenericSearch算法的正確性 22
2.2 寬度優(yōu)先的搜索和最短路徑 23
2.2.1 高層思路 23
2.2.2 BFS的偽碼 24
2.2.3 BFS的一個(gè)例子 25
2.2.4 正確性和運(yùn)行時(shí)間 27
2.2.5 最短路徑 28
2.2.6 小測(cè)驗(yàn)2.1的答案 31
2.3 計(jì)算連通分量 32
2.3.1 連通分量 32
2.3.2 連通分量的應(yīng)用 33
2.3.3 UCC（無向圖連通分量）算法 34
2.3.4 UCC算法的一個(gè)例子 35
2.3.5 UCC算法的正確性和運(yùn)行時(shí)間 36
2.3.6 小測(cè)驗(yàn)2.2的答案 37
2.4 深度優(yōu)先的搜索 37
2.4.1 DFS的一個(gè)例子 37
2.4.2 DFS的偽碼 39
2.4.3 正確性和運(yùn)行時(shí)間 41
2.5 拓?fù)渑判颉?1
2.5.1 拓?fù)漤樞颉?1
2.5.2 什么時(shí)候存在拓?fù)漤樞颉?3
2.5.3 計(jì)算拓?fù)漤樞颉?5
2.5.4 通過DFS的拓?fù)渑判颉?6
2.5.5 拓?fù)渑判虻囊粋�(gè)例子 47
2.5.6 正確性和運(yùn)行時(shí)間 48
2.5.7 小測(cè)驗(yàn)2.3和小測(cè)驗(yàn)2.4的答案 49
*2.6 計(jì)算強(qiáng)連通分量 50
2.6.1 強(qiáng)連通分量的定義 50
2.6.2 為什么要使用深度優(yōu)先的搜索 52
2.6.3 為什么要使用反轉(zhuǎn)的圖 53
2.6.4 Kosaraju的偽碼 57
2.6.5 一個(gè)例子 59
2.6.6 正確性和運(yùn)行時(shí)間 60
2.6.7 小測(cè)驗(yàn)2.5和小測(cè)驗(yàn)2.6的答案 60
2.7 Web的結(jié)構(gòu) 61
2.7.1 Web圖 62
2.7.2 蝴蝶結(jié) 63
2.7.3 主要發(fā)現(xiàn) 64
2.8 本章要點(diǎn) 65
2.9 章末習(xí)題 65
第3章 Dijkstra最短路徑算法 70
3.1 單源最短路徑問題 70
3.1.1 問題定義 70
3.1.2 一些前提條件 72
3.1.3 為什么不使用寬度優(yōu)先的搜索 72
3.1.4 小測(cè)驗(yàn)3.1的答案 73
3.2 Dijkstra算法 74
3.2.1 偽碼 74
3.2.2 一個(gè)例子 76
*3.3 為什么Dijkstra算法是正確的 77
3.3.1 一種虛假的簡(jiǎn)化 77
3.3.2 Dijkstra算法的一個(gè)糟糕例子 78
3.3.3 非負(fù)邊長時(shí)的正確性 78
3.4 算法的實(shí)現(xiàn)及其運(yùn)行時(shí)間 82
3.5 本章要點(diǎn) 84
3.6 章末習(xí)題 84
第4章 堆數(shù)據(jù)結(jié)構(gòu) 88
4.1 數(shù)據(jù)結(jié)構(gòu)概述 88
4.1.1 選擇正確的數(shù)據(jù)結(jié)構(gòu) 88
4.1.2 進(jìn)入更高層次 89
4.2 堆所支持的操作 90
4.2.1 Insert和ExtractMin 91
4.2.2 其他操作 92
4.3 堆的應(yīng)用 93
4.3.1 應(yīng)用：排序 93
4.3.2 應(yīng)用：事件管理器 96
4.3.3 應(yīng)用：中位值維護(hù) 96
4.4 Dijkstra算法的提速 98
4.4.1 為什么要使用堆 98
4.4.2 計(jì)劃 99
4.4.3 維持不變性 101
4.4.4 運(yùn)行時(shí)間 103
*4.5 實(shí)現(xiàn)細(xì)節(jié) 104
4.5.1 樹形式的堆 104
4.5.2 數(shù)組形式的堆 106
4.5.3 在O (log n)時(shí)間內(nèi)實(shí)現(xiàn)Insert操作 107
4.5.4 在O (log n)時(shí)間內(nèi)實(shí)現(xiàn)ExtractMin操作 111
4.6 本章要點(diǎn) 114
4.7 章末習(xí)題 114
第5章 搜索樹 117
5.1 有序數(shù)組 117
5.1.1 有序數(shù)組支持的操作 117
5.1.2 有序數(shù)組不支持的操作 119
5.2 搜索樹支持的操作 120
*5.3 實(shí)現(xiàn)細(xì)節(jié) 122
5.3.1 搜索樹的屬性 122
5.3.2 搜索樹的高度 123
5.3.3 在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Search 124
5.3.4 在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Min和Max 125
5.3.5 在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Predecessor 126
5.3.6 在O(n)時(shí)間內(nèi)實(shí)現(xiàn)OutputSorted操作 127
5.3.7 在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Insert操作 128
5.3.8 在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Delete操作 129
5.3.9 強(qiáng)化的搜索樹支持Select操作 132
5.3.10 小測(cè)驗(yàn)5.1的答案 134
*5.4 平衡搜索樹 134
5.4.1 努力實(shí)現(xiàn)更好的平衡 134
5.4.2 旋轉(zhuǎn) 135
5.5 本章要點(diǎn) 137
5.6 章末習(xí)題 138
第6章 散列表和布隆過濾器 140
6.1 支持的操作 140
6.2 散列表的應(yīng)用 143
6.2.1 應(yīng)用：消除重復(fù) 144
6.2.2 應(yīng)用：兩數(shù)之和問題 145
6.2.3 應(yīng)用：搜索巨大的狀態(tài)空間 147
6.2.4 小測(cè)驗(yàn)6.2的答案 148
*6.3 實(shí)現(xiàn)的高層思路 148
6.3.1 兩個(gè)簡(jiǎn)單的解決方案 148
6.3.2 散列函數(shù) 149
6.3.3 沖突是不可避免的 150
6.3.4 解決沖突的方法：鏈地址法 152
6.3.5 解決沖突的方法：開放地址法 153
6.3.6 良好的散列函數(shù)是怎么樣的 156
6.3.7 小測(cè)驗(yàn)6.3至小測(cè)驗(yàn)6.5的答案 160
*6.4 更多的實(shí)現(xiàn)細(xì)節(jié) 162
6.4.1 負(fù)載和性能 162
6.4.2 管理散列表的負(fù)載 164
6.4.3 選擇散列函數(shù) 165
6.4.4 選擇沖突解決策略 166
6.4.5 小測(cè)驗(yàn)6.6的答案 166
6.5 布隆過濾器的基礎(chǔ)知識(shí) 166
6.5.1 布隆過濾器支持的操作 167
6.5.2 布隆過濾器的應(yīng)用 169
6.5.3 布隆過濾器的實(shí)現(xiàn) 169
*6.6 布隆過濾器的啟發(fā)式分析 172
6.6.1 啟發(fā)式假設(shè) 172
6.6.2 部分位被設(shè)置為1 174
6.6.3 假陽性率 175
6.6.4 結(jié)束語 176
6.6.5 小測(cè)驗(yàn)6.7的答案 177
6.7 本章要點(diǎn) 178
6.8 章末習(xí)題 179
附錄 快速回顧漸進(jìn)性表示法 181
部分習(xí)題答案 187
書單推薦
