本書的撰寫有機(jī)結(jié)合了理論與實(shí)現(xiàn)，在講授算法理論的同時(shí)也通過(guò)C#實(shí)例講授了算法的實(shí)現(xiàn)。通過(guò)描述并分析一些重要的傳統(tǒng)算法，從而理解它們并且了解每一個(gè)算法在什么時(shí)候使用較為適合，通俗易懂地教授讀者創(chuàng)造自己的算法的技巧。這些技巧讓讀者能從不同的角度看問(wèn)題，建立有用的方法工具，從而解決實(shí)際問(wèn)題，抑或從容面對(duì)面試難題。本書適合當(dāng)作“算法設(shè)計(jì)與分析”和“數(shù)據(jù)結(jié)構(gòu)與算法”兩門課程的教材或參考書使用。特別是本書還融入和面試相關(guān)的內(nèi)容，因此適合作為算法相關(guān)工作面試的參考資料。
EssentialAlgorithms:APracticalApproachtoComputerAlgorithms算法是使高效的程序成為可能的方法。它們解釋了如何排列記錄、搜索項(xiàng)、計(jì)算數(shù)值（比如質(zhì)因子分解）、查找一個(gè)街道網(wǎng)絡(luò)中的最短路徑、確定可能通過(guò)通信網(wǎng)絡(luò)的最大流。算法好壞的差別可能意味著是在一秒、一個(gè)小時(shí)內(nèi)解決問(wèn)題，還是永遠(yuǎn)也不能解決問(wèn)題。
學(xué)習(xí)算法使你能建立有用的方法工具來(lái)解決具體的問(wèn)題。它能幫助你理解在不同的情況下，哪個(gè)算法是最有效的，所以對(duì)于一個(gè)特定的問(wèn)題，你就能選擇最適合的算法。對(duì)某些數(shù)據(jù)而言性能優(yōu)異的算法可能對(duì)其他的數(shù)據(jù)而言表現(xiàn)糟糕。所以知道如何選擇一個(gè)最適合當(dāng)前情況的算法是很重要的。
更重要的是，通過(guò)學(xué)習(xí)算法，你可以學(xué)習(xí)常規(guī)的問(wèn)題解決技巧。即使你已知的任何算法都不能很好地適合當(dāng)前的狀況，你也可以把這些技巧應(yīng)用到其他問(wèn)題上。這些技巧讓你從不同的角度看問(wèn)題，使你能創(chuàng)造和分析自己的算法，從而解決你的問(wèn)題，并且滿足沒(méi)有預(yù)料到的需求。
除了幫助你解決工作上的問(wèn)題，這些技巧甚至?xí)䦷椭惬@得需要使用這些技巧的工作。許多大的科技公司，比如微軟、谷歌、雅虎、IBM等公司都想要讓他們的程序員理解算法和相關(guān)問(wèn)題的解決技巧。其中，有些公司因?yàn)樽屆嬖囌咴诿嬖囍薪鉀Q算法編程和邏輯難題而“臭名昭著”。
好的面試官不一定期待你解決每一個(gè)難題。事實(shí)上，當(dāng)你沒(méi)有解決某個(gè)難題時(shí)，他們可能會(huì)了解更多。最好的面試官想看到你如何處理一個(gè)不熟悉的問(wèn)題，而不是想要看到答案。他們想看到你是舉起雙手說(shuō)這個(gè)問(wèn)題在面試中是不合理的，還是你分析了這個(gè)問(wèn)題，并提出了一條有希望的推理來(lái)用算法解決這個(gè)問(wèn)題。“天哪，我不知道�；蛟S我要上網(wǎng)搜一下”將會(huì)是一個(gè)壞的答案�！翱雌饋�(lái)一個(gè)遞歸的分治法可能有用”將會(huì)是一個(gè)好得多的答案。
這是一本易讀的計(jì)算機(jī)算法導(dǎo)論書。它描述了一些重要的傳統(tǒng)算法，并且說(shuō)明了每一個(gè)算法在什么時(shí)候是適合的。它解釋了如何分析算法從而理解它們的行為。最重要的，它教會(huì)了你創(chuàng)造自己新算法的技巧。
這里是本書中描述的一些有用的算法：
數(shù)值算法，比如隨機(jī)化、分解因式、處理質(zhì)數(shù)、數(shù)值積分熟練操作常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的方法，比如堆、樹、平衡樹、B樹排序和搜索網(wǎng)絡(luò)算法，比如最短路徑、生成樹、拓?fù)渑判蚝土饔?jì)算這里是本書中解釋的一些常規(guī)的問(wèn)題解決技巧：
暴力或者窮舉搜索分治法回溯法遞歸分支界限貪心算法和爬山法最小花費(fèi)算法縮小范圍啟發(fā)式算法為了幫助讀者掌握這些算法，本書提供了一些練習(xí)，讀者可以利用它們來(lái)探索自己的方法，以便修改書中的算法并把它們應(yīng)用到新的情況中。這些練習(xí)也會(huì)幫助你鞏固算法中的主要技巧。
最后，本書包含了解決面試中可能遇到的算法問(wèn)題的技巧。算法技巧會(huì)讓你解決許多面試中的難題。即使你不能用算法技巧解決每一個(gè)難題，至少表明你熟悉這些方法并且能用它們解決其他的問(wèn)題。
算法選擇本書中的每一個(gè)算法都是因?yàn)橐粋�(gè)或多個(gè)下列原因而被選擇的：
這個(gè)算法是有用的，并且有經(jīng)驗(yàn)的程序員應(yīng)該能理解它如何工作以及如何在程序中使用它。
這個(gè)算法展示了你可以應(yīng)用到其他問(wèn)題中的重要算法編程技巧。
計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生普遍學(xué)習(xí)這個(gè)算法，所以這個(gè)算法或者它使用的技巧可能出現(xiàn)在一個(gè)技術(shù)性面試中。
當(dāng)讀者讀完本書并做完練習(xí)后，將會(huì)有一個(gè)好的算法基礎(chǔ)并掌握解決自己編程問(wèn)題的技巧。
本書的目標(biāo)人群本書主要針對(duì)三種讀者：專業(yè)程序員、準(zhǔn)備面試的程序員和學(xué)習(xí)編程的學(xué)生。
專業(yè)程序員將會(huì)發(fā)現(xiàn)本書中所描述的算法和技巧對(duì)于解決他們工作中遇到的難題是很有用的。即使遇到無(wú)法直接用書中的算法解決的問(wèn)題，閱讀本書中的算法也會(huì)讓你從新的角度觀察問(wèn)題，從而發(fā)現(xiàn)新的解決辦法。
準(zhǔn)備工作面試的程序員可以使用本書來(lái)磨煉他們的算法技巧。你的面試可能不會(huì)包括書中描述的任何問(wèn)題，但是可能包含一些足夠相似的問(wèn)題。你可以用從本書中學(xué)到的技巧解決它們。
學(xué)習(xí)編程的學(xué)生應(yīng)該學(xué)習(xí)這些算法。本書中描述的許多方法是簡(jiǎn)單、富有魅力而且有效的。但是它們并不都是十分顯而易見(jiàn)的，所以你不一定會(huì)在偶然間自己發(fā)現(xiàn)它們。遞歸、分治、分支界限等技巧，還有使用眾所周知的數(shù)據(jù)結(jié)構(gòu)，這些對(duì)任何有興趣編程的人都是十分需要掌握的。
注就我個(gè)人而言，算法只是一種樂(lè)趣，它們就像填字游戲或者數(shù)獨(dú)一樣。我喜歡組成一個(gè)復(fù)雜的算法，倒一些數(shù)據(jù)進(jìn)去，然后看到一個(gè)美麗的三維圖形、一條匹配一系列點(diǎn)的曲線，或者一些其他的優(yōu)雅的答案出現(xiàn)。我喜歡這種感覺(jué)。
充分運(yùn)用本書僅僅是閱讀本書，就能學(xué)到一些新的算法和技巧。但是要真正掌握這些算法體現(xiàn)出的方法，就需要用它們工作，需要用某種編程語(yǔ)言實(shí)現(xiàn)它們。你還需要實(shí)驗(yàn)、修改這些算法，嘗試舊問(wèn)題的新變型。本書中的練習(xí)和面試問(wèn)題能讓你想到使用這些算法中技巧的新方法。
為了從本書中得到最大的收獲，我強(qiáng)烈推薦用一種你最喜歡的語(yǔ)言實(shí)現(xiàn)盡可能多的算法。甚至用
Rod Stephens初是一名數(shù)學(xué)家，但是在麻省理工學(xué)院進(jìn)修時(shí)，他喜歡上了算法和編程，并且從此以后走上了專業(yè)編程的道路。作為一位獲獎(jiǎng)導(dǎo)師，他經(jīng)常在各種技術(shù)大會(huì)上講演，并已寫了26本技術(shù)圖書，被翻譯為多國(guó)語(yǔ)言出版。
目 錄
Essential Algorithms: A Practical Approach to Computer Algorithms
出版者的話
譯者序
前言
第1章 算法基礎(chǔ)知識(shí)1
1.1 方法1
1.2 算法和數(shù)據(jù)結(jié)構(gòu)2
1.3 偽代碼2
1.4 算法的特點(diǎn)4
1.4.1 大O符號(hào)5
1.4.2 常見(jiàn)的運(yùn)行時(shí)間函數(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素性測(cè)試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 在某個(gè)單元格后插入單元格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)問(wè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 時(shí)間復(fù)雜度為O(N2)的算法89
6.1.1 數(shù)組中的插入排序89
6.1.2 數(shù)組中的選擇排序90
6.1.3 冒泡排序91
6.2 時(shí)間復(fù)雜度為O(N log N)的算法93
6.2.1 堆排序93
6.2.2 快速排序98
6.2.3 歸并排序103
6.3 時(shí)間復(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ǔ)知識(shí)114
8.2 鏈115
8.3 開放尋址116
8.3.1 刪除記錄117
8.3.2 線性探測(cè)118
8.3.3 二次探測(cè)119
8.3.4 偽隨機(jī)探測(cè)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 八皇后問(wèn)題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 存儲(chǔ)中間值146
9.5.3 一般遞歸的消除148
9.6 總結(jié)150
練習(xí)151
第10章 樹153
10.1 樹的術(shù)語(yǔ)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)行時(shí)間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 動(dòng)物游戲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)化問(wèn)題202
12.2.2 窮舉搜索202
12.2.3 分支界限203
12.2.4 決策樹的啟發(fā)式搜索205
12.2.5 其他決策樹問(wèn)題209
12.3 總結(jié)212
練習(xí)195
第13章 基本網(wǎng)絡(luò)算法214
13.1 網(wǎng)絡(luò)術(shù)語(yǔ)214
13.2
書單推薦
