本書的撰寫有機(jī)結(jié)合了理論與實(shí)現(xiàn)，在講授算法理論的同時也通過C#實(shí)例講授了算法的實(shí)現(xiàn)。通過描述并分析一些重要的傳統(tǒng)算法，從而理解它們并且了解每一個算法在什么時候使用較為適合，通俗易懂地教授讀者創(chuàng)造自己的算法的技巧。這些技巧讓讀者能從不同的角度看問題，建立有用的方法工具，從而解決實(shí)際問題，抑或從容面對面試難題。本書適合當(dāng)作“算法設(shè)計(jì)與分析”和“數(shù)據(jù)結(jié)構(gòu)與算法”兩門課程的教材或參考書使用。特別是本書還融入和面試相關(guān)的內(nèi)容，因此適合作為算法相關(guān)工作面試的參考資料。
EssentialAlgorithms:APracticalApproachtoComputerAlgorithms算法是使高效的程序成為可能的方法。它們解釋了如何排列記錄、搜索項(xiàng)、計(jì)算數(shù)值（比如質(zhì)因子分解）、查找一個街道網(wǎng)絡(luò)中的最短路徑、確定可能通過通信網(wǎng)絡(luò)的最大流。算法好壞的差別可能意味著是在一秒、一個小時內(nèi)解決問題，還是永遠(yuǎn)也不能解決問題。
學(xué)習(xí)算法使你能建立有用的方法工具來解決具體的問題。它能幫助你理解在不同的情況下，哪個算法是最有效的，所以對于一個特定的問題，你就能選擇最適合的算法。對某些數(shù)據(jù)而言性能優(yōu)異的算法可能對其他的數(shù)據(jù)而言表現(xiàn)糟糕。所以知道如何選擇一個最適合當(dāng)前情況的算法是很重要的。
更重要的是，通過學(xué)習(xí)算法，你可以學(xué)習(xí)常規(guī)的問題解決技巧。即使你已知的任何算法都不能很好地適合當(dāng)前的狀況，你也可以把這些技巧應(yīng)用到其他問題上。這些技巧讓你從不同的角度看問題，使你能創(chuàng)造和分析自己的算法，從而解決你的問題，并且滿足沒有預(yù)料到的需求。
除了幫助你解決工作上的問題，這些技巧甚至?xí)䦷椭惬@得需要使用這些技巧的工作。許多大的科技公司，比如微軟、谷歌、雅虎、IBM等公司都想要讓他們的程序員理解算法和相關(guān)問題的解決技巧。其中，有些公司因?yàn)樽屆嬖囌咴诿嬖囍薪鉀Q算法編程和邏輯難題而“臭名昭著”。
好的面試官不一定期待你解決每一個難題。事實(shí)上，當(dāng)你沒有解決某個難題時，他們可能會了解更多。最好的面試官想看到你如何處理一個不熟悉的問題，而不是想要看到答案。他們想看到你是舉起雙手說這個問題在面試中是不合理的，還是你分析了這個問題，并提出了一條有希望的推理來用算法解決這個問題�！疤炷�，我不知道�；蛟S我要上網(wǎng)搜一下”將會是一個壞的答案�！翱雌饋硪粋�遞歸的分治法可能有用”將會是一個好得多的答案。
這是一本易讀的計(jì)算機(jī)算法導(dǎo)論書。它描述了一些重要的傳統(tǒng)算法，并且說明了每一個算法在什么時候是適合的。它解釋了如何分析算法從而理解它們的行為。最重要的，它教會了你創(chuàng)造自己新算法的技巧。
這里是本書中描述的一些有用的算法：
數(shù)值算法，比如隨機(jī)化、分解因式、處理質(zhì)數(shù)、數(shù)值積分熟練操作常見數(shù)據(jù)結(jié)構(gòu)的方法，比如堆、樹、平衡樹、B樹排序和搜索網(wǎng)絡(luò)算法，比如最短路徑、生成樹、拓?fù)渑判蚝土饔?jì)算這里是本書中解釋的一些常規(guī)的問題解決技巧：
暴力或者窮舉搜索分治法回溯法遞歸分支界限貪心算法和爬山法最小花費(fèi)算法縮小范圍啟發(fā)式算法為了幫助讀者掌握這些算法，本書提供了一些練習(xí)，讀者可以利用它們來探索自己的方法，以便修改書中的算法并把它們應(yīng)用到新的情況中。這些練習(xí)也會幫助你鞏固算法中的主要技巧。
最后，本書包含了解決面試中可能遇到的算法問題的技巧。算法技巧會讓你解決許多面試中的難題。即使你不能用算法技巧解決每一個難題，至少表明你熟悉這些方法并且能用它們解決其他的問題。
算法選擇本書中的每一個算法都是因?yàn)橐粋�或多個下列原因而被選擇的：
這個算法是有用的，并且有經(jīng)驗(yàn)的程序員應(yīng)該能理解它如何工作以及如何在程序中使用它。
這個算法展示了你可以應(yīng)用到其他問題中的重要算法編程技巧。
計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生普遍學(xué)習(xí)這個算法，所以這個算法或者它使用的技巧可能出現(xiàn)在一個技術(shù)性面試中。
當(dāng)讀者讀完本書并做完練習(xí)后，將會有一個好的算法基礎(chǔ)并掌握解決自己編程問題的技巧。
本書的目標(biāo)人群本書主要針對三種讀者：專業(yè)程序員、準(zhǔn)備面試的程序員和學(xué)習(xí)編程的學(xué)生。
專業(yè)程序員將會發(fā)現(xiàn)本書中所描述的算法和技巧對于解決他們工作中遇到的難題是很有用的。即使遇到無法直接用書中的算法解決的問題，閱讀本書中的算法也會讓你從新的角度觀察問題，從而發(fā)現(xiàn)新的解決辦法。
準(zhǔn)備工作面試的程序員可以使用本書來磨煉他們的算法技巧。你的面試可能不會包括書中描述的任何問題，但是可能包含一些足夠相似的問題。你可以用從本書中學(xué)到的技巧解決它們。
學(xué)習(xí)編程的學(xué)生應(yīng)該學(xué)習(xí)這些算法。本書中描述的許多方法是簡單、富有魅力而且有效的。但是它們并不都是十分顯而易見的，所以你不一定會在偶然間自己發(fā)現(xiàn)它們。遞歸、分治、分支界限等技巧，還有使用眾所周知的數(shù)據(jù)結(jié)構(gòu)，這些對任何有興趣編程的人都是十分需要掌握的。
注就我個人而言，算法只是一種樂趣，它們就像填字游戲或者數(shù)獨(dú)一樣。我喜歡組成一個復(fù)雜的算法，倒一些數(shù)據(jù)進(jìn)去，然后看到一個美麗的三維圖形、一條匹配一系列點(diǎn)的曲線，或者一些其他的優(yōu)雅的答案出現(xiàn)。我喜歡這種感覺。
充分運(yùn)用本書僅僅是閱讀本書，就能學(xué)到一些新的算法和技巧。但是要真正掌握這些算法體現(xiàn)出的方法，就需要用它們工作，需要用某種編程語言實(shí)現(xiàn)它們。你還需要實(shí)驗(yàn)、修改這些算法，嘗試舊問題的新變型。本書中的練習(xí)和面試問題能讓你想到使用這些算法中技巧的新方法。
為了從本書中得到最大的收獲，我強(qiáng)烈推薦用一種你最喜歡的語言實(shí)現(xiàn)盡可能多的算法。甚至用
Rod Stephens初是一名數(shù)學(xué)家，但是在麻省理工學(xué)院進(jìn)修時，他喜歡上了算法和編程，并且從此以后走上了專業(yè)編程的道路。作為一位獲獎導(dǎo)師，他經(jīng)常在各種技術(shù)大會上講演，并已寫了26本技術(shù)圖書，被翻譯為多國語言出版。
目 錄
Essential Algorithms: A Practical Approach to Computer Algorithms
出版者的話
譯者序
前言
第1章 算法基礎(chǔ)知識1
1.1 方法1
1.2 算法和數(shù)據(jù)結(jié)構(gòu)2
1.3 偽代碼2
1.4 算法的特點(diǎn)4
1.4.1 大O符號5
1.4.2 常見的運(yùn)行時間函數(shù)7
1.4.3 可視化函數(shù)12
1.5實(shí)際因素12
1.6 總結(jié)13
練習(xí)13
第2章 數(shù)值算法16
2.1 隨機(jī)化數(shù)據(jù)16
2.1.1 隨機(jī)數(shù)生成16
2.1.2 隨機(jī)化數(shù)組20
2.1.3 生成不均勻分布21
2.2 尋找最大公約數(shù)21
2.3 求冪運(yùn)算23
2.4 有關(guān)素?cái)?shù)的運(yùn)算24
2.4.1 尋找素?cái)?shù)因子24
2.4.2 尋找素?cái)?shù)26
2.4.3素性測試27
2.5 進(jìn)行數(shù)值積分28
2.5.1 矩形規(guī)則28
2.5.2梯形規(guī)則29
2.5.3 自適應(yīng)求積30
2.5.4 蒙特卡羅積分32
2.6 查找零32
2.7 總結(jié)34
練習(xí)34
第3章 鏈表36
3.1 基本概念36
3.2 單鏈表37
3.2.1 遍歷鏈表37
3.2.2 查找單元格37
3.2.3 使用哨兵38
3.2.4 在開頭添加單元格39
3.2.5 在結(jié)尾添加單元格40
3.2.6 在某個單元格后插入單元格40
3.2.7 刪除單元格41
3.3 雙向鏈表42
3.4 有序鏈表43
3.5 鏈表算法44
3.5.1 復(fù)制鏈表44
3.5.2 鏈表的插入排序45
3.6 鏈表的選擇排序46
3.7 多線程鏈表47
3.8 循環(huán)鏈表48
3.8.1 標(biāo)記單元格49
3.8.2 使用散列表50
3.8.3 鏈表回溯51
3.8.4 反轉(zhuǎn)鏈表51
3.8.5 烏龜和兔子53
3.8.6 雙向鏈表中的循環(huán)問題55
3.9 總結(jié)55
練習(xí)55
第4章 數(shù)組57
4.1 基本概念57
4.2 一維數(shù)組58
4.2.1 查找元素58
4.2.2 查找最大值、最小值、平均值59
4.2.3 插入元素60
4.2.4 移除元素61
4.3 非零下界61
4.3.1 二維數(shù)組61
4.3.2 多維數(shù)組62
4.4 三角形數(shù)組64
4.5 稀疏數(shù)組66
4.5.1 找到行或列67
4.5.2 獲取值68
4.5.3 設(shè)置值69
4.5.4 刪除值71
4.6 矩陣72
4.7 總結(jié)74
練習(xí)74
第5章 棧和隊(duì)列76
5.1 棧76
5.1.1 棧的鏈表實(shí)現(xiàn)76
5.1.2 棧的數(shù)組實(shí)現(xiàn)77
5.1.3 雙向棧78
5.1.4 棧的算法79
5.2 隊(duì)列84
5.2.1 隊(duì)列的鏈表實(shí)現(xiàn)84
5.2.2 隊(duì)列的數(shù)組實(shí)現(xiàn)85
5.2.3 專用隊(duì)列86
5.3 總結(jié)87
練習(xí)87
第6章 排序89
6.1 時間復(fù)雜度為O(N2)的算法89
6.1.1 數(shù)組中的插入排序89
6.1.2 數(shù)組中的選擇排序90
6.1.3 冒泡排序91
6.2 時間復(fù)雜度為O(N log N)的算法93
6.2.1 堆排序93
6.2.2 快速排序98
6.2.3 歸并排序103
6.3 時間復(fù)雜度為亞O(N log N)的算法105
6.3.1 計(jì)數(shù)排序106
6.3.2 桶排序107
6.4 總結(jié)108
練習(xí)108
第7章 搜索110
7.1 線性搜索110
7.2 二分搜索111
7.3 插值搜索112
7.4 總結(jié)113
練習(xí)113
第8章 散列表114
8.1 散列表的基礎(chǔ)知識114
8.2 鏈115
8.3 開放尋址116
8.3.1 刪除記錄117
8.3.2 線性探測118
8.3.3 二次探測119
8.3.4 偽隨機(jī)探測120
8.3.5 雙散列120
8.3.6 有序散列121
8.4 總結(jié)122
練習(xí)123
第9章 遞歸125
9.1 基礎(chǔ)算法125
9.1.1 階乘125
9.1.2 斐波那契數(shù)127
9.1.3 漢諾塔128
9.2 圖算法130
9.2.1 科赫曲線130
9.2.2 希爾伯特曲線131
9.2.3 謝爾賓斯基曲線132
9.2.4 墊片134
9.3 回溯算法134
9.3.1 八皇后問題136
9.3.2 騎士巡游138
9.4 選擇與排列140
9.4.1 循環(huán)選擇140
9.4.2 重復(fù)選擇141
9.4.3 不重復(fù)選擇142
9.4.4 元素可重復(fù)的排列143
9.4.5 元素不重復(fù)的排列144
9.5 消去遞歸145
9.5.1 尾遞歸的消除145
9.5.2 存儲中間值146
9.5.3 一般遞歸的消除148
9.6 總結(jié)150
練習(xí)151
第10章 樹153
10.1 樹的術(shù)語153
10.2 二叉樹屬性155
10.3 樹的表示157
10.3.1 建立樹的通用方法157
10.3.2 構(gòu)造完全樹159
10.4 樹的遍歷160
10.4.1 前序遍歷160
10.4.2 中序遍歷162
10.4.3 后序遍歷163
10.4.4 深度優(yōu)先遍歷164
10.4.5 遍歷的運(yùn)行時間164
10.5 排序樹 165
10.5.1 添加結(jié)點(diǎn)165
10.5.2 查找結(jié)點(diǎn)166
10.5.3 刪除結(jié)點(diǎn)167
10.6 線索樹168
10.6.1 建立線索樹169
10.6.2 使用線索樹171
10.7 特化樹算法172
10.7.1 動物游戲172
10.7.2 表達(dá)式求值173
10.7.3 四叉樹175
10.7.4 Trie樹179
10.8 總結(jié)182
練習(xí)182
第11章 平衡樹185
11.1 AVL樹185
11.1.1 添加值185
11.1.2 刪除值187
11.2 2-3樹187
11.2.1 添加值188
11.2.2 刪除值189
11.3 B樹191
11.3.1 添加值191
11.3.2 刪除值192
11.4 平衡樹變體193
11.4.1 自上而下的B樹193
11.4.2 B+樹193
11.5 總結(jié)194
練習(xí)195
第12章 決策樹196
12.1 游戲搜索樹196
12.1.1 極小化極大值算法197
12.1.2 初始步驟和反應(yīng)199
12.1.3 啟發(fā)式游戲樹200
12.2 搜索通用決策樹201
12.2.1 優(yōu)化問題202
12.2.2 窮舉搜索202
12.2.3 分支界限203
12.2.4 決策樹的啟發(fā)式搜索205
12.2.5 其他決策樹問題209
12.3 總結(jié)212
練習(xí)195
第13章 基本網(wǎng)絡(luò)算法214
13.1 網(wǎng)絡(luò)術(shù)語214
13.2
書單推薦
