本書的撰寫有機結合了理論與實現(xiàn)，在講授算法理論的同時也通過C#實例講授了算法的實現(xiàn)。通過描述并分析一些重要的傳統(tǒng)算法，從而理解它們并且了解每一個算法在什么時候使用較為適合，通俗易懂地教授讀者創(chuàng)造自己的算法的技巧。這些技巧讓讀者能從不同的角度看問題，建立有用的方法工具，從而解決實際問題，抑或從容面對面試難題。本書適合當作“算法設計與分析”和“數(shù)據(jù)結構與算法”兩門課程的教材或參考書使用。特別是本書還融入和面試相關的內(nèi)容，因此適合作為算法相關工作面試的參考資料。
EssentialAlgorithms:APracticalApproachtoComputerAlgorithms算法是使高效的程序成為可能的方法。它們解釋了如何排列記錄、搜索項、計算數(shù)值（比如質因子分解）、查找一個街道網(wǎng)絡中的最短路徑、確定可能通過通信網(wǎng)絡的最大流。算法好壞的差別可能意味著是在一秒、一個小時內(nèi)解決問題，還是永遠也不能解決問題。
學習算法使你能建立有用的方法工具來解決具體的問題。它能幫助你理解在不同的情況下，哪個算法是最有效的，所以對于一個特定的問題，你就能選擇最適合的算法。對某些數(shù)據(jù)而言性能優(yōu)異的算法可能對其他的數(shù)據(jù)而言表現(xiàn)糟糕。所以知道如何選擇一個最適合當前情況的算法是很重要的。
更重要的是，通過學習算法，你可以學習常規(guī)的問題解決技巧。即使你已知的任何算法都不能很好地適合當前的狀況，你也可以把這些技巧應用到其他問題上。這些技巧讓你從不同的角度看問題，使你能創(chuàng)造和分析自己的算法，從而解決你的問題，并且滿足沒有預料到的需求。
除了幫助你解決工作上的問題，這些技巧甚至會幫助你獲得需要使用這些技巧的工作。許多大的科技公司，比如微軟、谷歌、雅虎、IBM等公司都想要讓他們的程序員理解算法和相關問題的解決技巧。其中，有些公司因為讓面試者在面試中解決算法編程和邏輯難題而“臭名昭著”。
好的面試官不一定期待你解決每一個難題。事實上，當你沒有解決某個難題時，他們可能會了解更多。最好的面試官想看到你如何處理一個不熟悉的問題，而不是想要看到答案。他們想看到你是舉起雙手說這個問題在面試中是不合理的，還是你分析了這個問題，并提出了一條有希望的推理來用算法解決這個問題。“天哪，我不知道�；蛟S我要上網(wǎng)搜一下”將會是一個壞的答案。“看起來一個遞歸的分治法可能有用”將會是一個好得多的答案。
這是一本易讀的計算機算法導論書。它描述了一些重要的傳統(tǒng)算法，并且說明了每一個算法在什么時候是適合的。它解釋了如何分析算法從而理解它們的行為。最重要的，它教會了你創(chuàng)造自己新算法的技巧。
這里是本書中描述的一些有用的算法：
數(shù)值算法，比如隨機化、分解因式、處理質數(shù)、數(shù)值積分熟練操作常見數(shù)據(jù)結構的方法，比如堆、樹、平衡樹、B樹排序和搜索網(wǎng)絡算法，比如最短路徑、生成樹、拓撲排序和流計算這里是本書中解釋的一些常規(guī)的問題解決技巧：
暴力或者窮舉搜索分治法回溯法遞歸分支界限貪心算法和爬山法最小花費算法縮小范圍啟發(fā)式算法為了幫助讀者掌握這些算法，本書提供了一些練習，讀者可以利用它們來探索自己的方法，以便修改書中的算法并把它們應用到新的情況中。這些練習也會幫助你鞏固算法中的主要技巧。
最后，本書包含了解決面試中可能遇到的算法問題的技巧。算法技巧會讓你解決許多面試中的難題。即使你不能用算法技巧解決每一個難題，至少表明你熟悉這些方法并且能用它們解決其他的問題。
算法選擇本書中的每一個算法都是因為一個或多個下列原因而被選擇的：
這個算法是有用的，并且有經(jīng)驗的程序員應該能理解它如何工作以及如何在程序中使用它。
這個算法展示了你可以應用到其他問題中的重要算法編程技巧。
計算機科學專業(yè)的學生普遍學習這個算法，所以這個算法或者它使用的技巧可能出現(xiàn)在一個技術性面試中。
當讀者讀完本書并做完練習后，將會有一個好的算法基礎并掌握解決自己編程問題的技巧。
本書的目標人群本書主要針對三種讀者：專業(yè)程序員、準備面試的程序員和學習編程的學生。
專業(yè)程序員將會發(fā)現(xiàn)本書中所描述的算法和技巧對于解決他們工作中遇到的難題是很有用的。即使遇到無法直接用書中的算法解決的問題，閱讀本書中的算法也會讓你從新的角度觀察問題，從而發(fā)現(xiàn)新的解決辦法。
準備工作面試的程序員可以使用本書來磨煉他們的算法技巧。你的面試可能不會包括書中描述的任何問題，但是可能包含一些足夠相似的問題。你可以用從本書中學到的技巧解決它們。
學習編程的學生應該學習這些算法。本書中描述的許多方法是簡單、富有魅力而且有效的。但是它們并不都是十分顯而易見的，所以你不一定會在偶然間自己發(fā)現(xiàn)它們。遞歸、分治、分支界限等技巧，還有使用眾所周知的數(shù)據(jù)結構，這些對任何有興趣編程的人都是十分需要掌握的。
注就我個人而言，算法只是一種樂趣，它們就像填字游戲或者數(shù)獨一樣。我喜歡組成一個復雜的算法，倒一些數(shù)據(jù)進去，然后看到一個美麗的三維圖形、一條匹配一系列點的曲線，或者一些其他的優(yōu)雅的答案出現(xiàn)。我喜歡這種感覺。
充分運用本書僅僅是閱讀本書，就能學到一些新的算法和技巧。但是要真正掌握這些算法體現(xiàn)出的方法，就需要用它們工作，需要用某種編程語言實現(xiàn)它們。你還需要實驗、修改這些算法，嘗試舊問題的新變型。本書中的練習和面試問題能讓你想到使用這些算法中技巧的新方法。
為了從本書中得到最大的收獲，我強烈推薦用一種你最喜歡的語言實現(xiàn)盡可能多的算法。甚至用
Rod Stephens初是一名數(shù)學家，但是在麻省理工學院進修時，他喜歡上了算法和編程，并且從此以后走上了專業(yè)編程的道路。作為一位獲獎導師，他經(jīng)常在各種技術大會上講演，并已寫了26本技術圖書，被翻譯為多國語言出版。
目 錄
Essential Algorithms: A Practical Approach to Computer Algorithms
出版者的話
譯者序
前言
第1章 算法基礎知識1
1.1 方法1
1.2 算法和數(shù)據(jù)結構2
1.3 偽代碼2
1.4 算法的特點4
1.4.1 大O符號5
1.4.2 常見的運行時間函數(shù)7
1.4.3 可視化函數(shù)12
1.5實際因素12
1.6 總結13
練習13
第2章 數(shù)值算法16
2.1 隨機化數(shù)據(jù)16
2.1.1 隨機數(shù)生成16
2.1.2 隨機化數(shù)組20
2.1.3 生成不均勻分布21
2.2 尋找最大公約數(shù)21
2.3 求冪運算23
2.4 有關素數(shù)的運算24
2.4.1 尋找素數(shù)因子24
2.4.2 尋找素數(shù)26
2.4.3素性測試27
2.5 進行數(shù)值積分28
2.5.1 矩形規(guī)則28
2.5.2梯形規(guī)則29
2.5.3 自適應求積30
2.5.4 蒙特卡羅積分32
2.6 查找零32
2.7 總結34
練習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 在結尾添加單元格40
3.2.6 在某個單元格后插入單元格40
3.2.7 刪除單元格41
3.3 雙向鏈表42
3.4 有序鏈表43
3.5 鏈表算法44
3.5.1 復制鏈表44
3.5.2 鏈表的插入排序45
3.6 鏈表的選擇排序46
3.7 多線程鏈表47
3.8 循環(huán)鏈表48
3.8.1 標記單元格49
3.8.2 使用散列表50
3.8.3 鏈表回溯51
3.8.4 反轉鏈表51
3.8.5 烏龜和兔子53
3.8.6 雙向鏈表中的循環(huán)問題55
3.9 總結55
練習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 設置值69
4.5.4 刪除值71
4.6 矩陣72
4.7 總結74
練習74
第5章 棧和隊列76
5.1 棧76
5.1.1 棧的鏈表實現(xiàn)76
5.1.2 棧的數(shù)組實現(xiàn)77
5.1.3 雙向棧78
5.1.4 棧的算法79
5.2 隊列84
5.2.1 隊列的鏈表實現(xiàn)84
5.2.2 隊列的數(shù)組實現(xiàn)85
5.2.3 專用隊列86
5.3 總結87
練習87
第6章 排序89
6.1 時間復雜度為O(N2)的算法89
6.1.1 數(shù)組中的插入排序89
6.1.2 數(shù)組中的選擇排序90
6.1.3 冒泡排序91
6.2 時間復雜度為O(N log N)的算法93
6.2.1 堆排序93
6.2.2 快速排序98
6.2.3 歸并排序103
6.3 時間復雜度為亞O(N log N)的算法105
6.3.1 計數(shù)排序106
6.3.2 桶排序107
6.4 總結108
練習108
第7章 搜索110
7.1 線性搜索110
7.2 二分搜索111
7.3 插值搜索112
7.4 總結113
練習113
第8章 散列表114
8.1 散列表的基礎知識114
8.2 鏈115
8.3 開放尋址116
8.3.1 刪除記錄117
8.3.2 線性探測118
8.3.3 二次探測119
8.3.4 偽隨機探測120
8.3.5 雙散列120
8.3.6 有序散列121
8.4 總結122
練習123
第9章 遞歸125
9.1 基礎算法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 重復選擇141
9.4.3 不重復選擇142
9.4.4 元素可重復的排列143
9.4.5 元素不重復的排列144
9.5 消去遞歸145
9.5.1 尾遞歸的消除145
9.5.2 存儲中間值146
9.5.3 一般遞歸的消除148
9.6 總結150
練習151
第10章 樹153
10.1 樹的術語153
10.2 二叉樹屬性155
10.3 樹的表示157
10.3.1 建立樹的通用方法157
10.3.2 構造完全樹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 遍歷的運行時間164
10.5 排序樹 165
10.5.1 添加結點165
10.5.2 查找結點166
10.5.3 刪除結點167
10.6 線索樹168
10.6.1 建立線索樹169
10.6.2 使用線索樹171
10.7 特化樹算法172
10.7.1 動物游戲172
10.7.2 表達式求值173
10.7.3 四叉樹175
10.7.4 Trie樹179
10.8 總結182
練習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 總結194
練習195
第12章 決策樹196
12.1 游戲搜索樹196
12.1.1 極小化極大值算法197
12.1.2 初始步驟和反應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 總結212
練習195
第13章 基本網(wǎng)絡算法214
13.1 網(wǎng)絡術語214
13.2
書單推薦
