本書通過算法所解決的現(xiàn)實世界的實例來介紹各種算法的思想和技術(shù)細節(jié)。算法用偽代碼給出,使得后續(xù)可以很容易地用一種計算機語言來實現(xiàn)。
前言
第1章股票跨度1
1.1算法2
1.2運行時間和復(fù)雜度5
1.3使用棧求解股票跨度9
注釋13
習(xí)題14
第2章探索迷宮15
2.1圖16
2.2圖表示20
2.3深度優(yōu)先圖遍歷25
2.4寬度優(yōu)先搜索32
注釋35
習(xí)題36
第3章壓縮算法38
3.1壓縮40
3.2樹和優(yōu)先隊列42
3.3赫夫曼編碼44
3.4倫佩爾-齊夫-韋爾奇壓縮算法50
注釋58
習(xí)題58
第4章秘密60
4.1一個解密挑戰(zhàn)61
4.2一次性密碼本64
4.3AES加密67
4.4迪菲-赫爾曼密鑰交換72
4.5快速模冪運算76
注釋79
習(xí)題80
第5章秘密分割81
5.1公鑰密碼學(xué)81
5.2RSA密碼系統(tǒng)83
5.3消息哈希90
5.4互聯(lián)網(wǎng)通信匿名化91
注釋95
習(xí)題96
第6章排序問題97
6.1拓撲排序98
6.2加權(quán)圖102
6.3關(guān)鍵路徑103
注釋108
習(xí)題109
第7章行、段落和路徑110
7.1最短路徑112
7.2迪杰斯特拉算法114
注釋118
習(xí)題119
第8章路由和套利120
8.1互聯(lián)網(wǎng)路由122
8.2Bellman-Ford(-Moore)算法125
8.3負權(quán)重和環(huán)130
8.4套利133
注釋135
第9章什么最重要136
9.1PageRank思想136
9.2超鏈接矩陣137
9.3冪方法139
9.4Google矩陣142
注釋145
第10章投票力147
10.1投票系統(tǒng)148
10.2Schulze方法150
10.3Floyd-Warshall算法158
注釋159
第11章蠻力、秘書和二分法160
11.1順序搜索160
11.2匹配、比較、記錄和關(guān)鍵字162
11.3馬太效應(yīng)和冪律163
11.4自組織搜索167
11.5秘書問題170
11.6二分搜索172
11.7在計算機中表示整數(shù)175
11.8再探二分搜索179
11.9比較樹180
注釋183
第12章各種各樣的排序算法185
12.1選擇排序185
12.2插入排序188
12.3堆排序191
12.4歸并排序197
12.5快速排序205
12.6多不勝選210
注釋212
習(xí)題212
第13章寄存室、鴿巢和桶213
13.1將關(guān)鍵字映射到值213
13.2哈希216
13.3哈希函數(shù)218
13.4浮點數(shù)表示和哈希223
13.5碰撞225
13.6數(shù)字指紋231
13.7Bloom過濾器235
注釋242
習(xí)題243
第14章比特和樹244
14.1將占卜看作通信問題244
14.2信息和熵246
14.3分類249
14.4決策樹250
14.5屬性選擇253
14.6ID3算法256
14.7內(nèi)在機制261
14.8奧卡姆剃刀法則266
14.9代價、問題和改進266
注釋268
習(xí)題269
第15章字符串算法271
15.1蠻力字符串匹配273
15.2Knuth-Morris-Pratt算法275
15.3Boyer-Moore-Horspool算法283
注釋288
習(xí)題288
第16章聽從命運的安排290
16.1隨機數(shù)291
16.2隨機抽樣296
16.3權(quán)力游戲300
16.4搜索素數(shù)307
注釋313
習(xí)題314
參考文獻315
索引326