算法圖解

Grokking Algorithms

作者Aditya Bhargava，美國人。

?

這本書的定位正如封面副標(biāo)題所言–像小說一樣有趣的算法入門書，作為一本入門級的算法書，這本書無疑是成功的，書中穿插著大量的圖解（作者自述自己為一個視覺性學(xué)習(xí)者），內(nèi)容簡單，將一些經(jīng)典的算法結(jié)合圖解以生動有趣的方式向讀者講解，使非程序員的讀者也能輕松理解（除了動態(tài)規(guī)劃部分本身就是一個難點）。同時，以小說為定位也很真實，本書共181頁，豐富的圖解、形象的表述、生動的表達使讀者很容易被吸引，短短一天內(nèi)即可吸收完這本書的內(nèi)容精華。

內(nèi)容提要

本書示例豐富，圖文并茂，以簡明易懂的方式闡釋了算法，旨在幫助程序員在日常項目中更好地利用算法為軟件開發(fā)助力。前三章介紹算法基礎(chǔ)，包括二分查找、大 O 表示法、兩種基本的數(shù)據(jù)結(jié)構(gòu)以及遞歸等。余下的篇幅將主要介紹應(yīng)用廣泛的算法，具體內(nèi)容包括 :面對具體問題時的解決技巧，比如何時采用 貪婪算法或動態(tài)規(guī)劃 ;散列表的應(yīng)用 ;圖算法
;K 最近鄰算法。

本書適合所有程序員、計算機專業(yè)相關(guān)師生以及對算法感興趣的讀者。

第一章 算法簡介

主要內(nèi)容

講解了二分查找算法，介紹了大O表示法。

O(log n)，也叫對數(shù)時間，這樣的算法包括二分查找。
O(n)，也叫線性時間，這樣的算法包括簡單查找。
O(n * log n)，這樣的算法包括第4章將介紹的快速排序——一種速度較快的排序算法。 ? O(n2)，這樣的算法包括第2章將介紹的選擇排序——一種速度較慢的排序算法。
O(n!)，這樣的算法包括接下來將介紹的旅行商問題的解決方案——一種非常慢的算法。
O(1)，常數(shù)時間。

小結(jié)

二分查找的速度比簡單查找快得多。
O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
算法運行時間并不以秒為單位。
算法運行時間是從其增速的角度度量的。
算法運行時間用大O表示法表示。

第二章 選擇排序

主要內(nèi)容

介紹數(shù)組和鏈表，分析了兩者查找、插入、刪除的時間復(fù)雜度，說明了兩者的適用范圍。
講解了選擇排序算法的原理和實現(xiàn)。

需要檢查的元素數(shù)越來越少
隨著排序的進行，每次需要檢查的元素數(shù)在逐漸減少，最后一次需要檢查的元素都只有一 個。既然如此，運行時間怎么還是O(n2)呢?這個問題問得好，這與大O表示法中的常數(shù)相關(guān)。 第4章將詳細(xì)解釋，這里只簡單地說一說。
你說得沒錯，并非每次都需要檢查n個元素。第一次需要檢查n個元素，但隨后檢查的元素 數(shù)依次為n - 1, n – 2, …, 2和1。平均每次檢查的元素數(shù)為1/2 × n，因此運行時間為O(n × 1/2 × n)。 但大O表示法省略諸如1/2這樣的常數(shù)(有關(guān)這方面的完整討論，請參閱第4章)，因此簡單地寫 作O(n × n)或O(n2)。

小結(jié)

計算機內(nèi)存猶如一大堆抽屜。
需要存儲多個元素時，可使用數(shù)組或鏈表。
數(shù)組的元素都在一起。
鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址。
數(shù)組的讀取速度很快。
鏈表的插入和刪除速度很快。
在同一個數(shù)組中，所有元素的類型都必須相同(都為int、double等)。

第三章 遞歸

主要內(nèi)容

介紹了遞歸（遞歸只是讓解決方案更清晰，并沒有性能上的優(yōu)勢），注意是基線條件（base case）和遞歸條件（recursive case），重點是調(diào)用棧及遞歸調(diào)用棧。

尾遞歸

小結(jié)

遞歸指的是調(diào)用自己的函數(shù)。
每個遞歸函數(shù)都有兩個條件:基線條件和遞歸條件。
棧有兩種操作:壓入和彈出。
所有函數(shù)調(diào)用都進入調(diào)用棧。
調(diào)用棧可能很長，這將占用大量的內(nèi)存。

第四章 快速排序

主要內(nèi)容

介紹了分治法，講解了D&C算法–快速排序算法的原理和實現(xiàn)（基準(zhǔn)值 pivot 和分區(qū) partitioning）。比較了快排和歸并排序的性能。
解釋了大O表示法的平均情況和最糟情況。

提示：編寫涉及數(shù)組的遞歸函數(shù)時，基線條件通常是數(shù)組為空或只包含一個元素。陷入困境時， 請檢查基線條件是不是這樣的。

小結(jié)

D&C將問題逐步分解。使用D&C處理列表時，基線條件很可能是空數(shù)組或只包含一個元 素的數(shù)組。
實現(xiàn)快速排序時，請隨機地選擇用作基準(zhǔn)值的元素。快速排序的平均運行時間為O(n log n)。
大O表示法中的常量有時候事關(guān)重大，這就是快速排序比合并排序快的原因所在。
比較簡單查找和二分查找時，常量幾乎無關(guān)緊要，因為列表很長時，O(log n)的速度比O(n) 快得多。

第五章 散列表

主要內(nèi)容

本章介紹了散列表和散列函數(shù)及其實現(xiàn)原理，解釋了填充因子定義及作用。介紹了Python的散列表的應(yīng)用–字典 dict()。
介紹了散列表的應(yīng)用范圍：查找、防止重復(fù)、緩存。

你可能根本不需要自己去實現(xiàn)散列表，任一優(yōu)秀的語言都提供了散列表實現(xiàn)。Python提供的 散列表實現(xiàn)為字典，你可使用函數(shù)dict來創(chuàng)建散列表。

經(jīng)驗規(guī)則： 一旦填裝因子大于0.7，就調(diào)整散列表的長度。

小結(jié)

你幾乎根本不用自己去實現(xiàn)散列表，因為你使用的編程語言提供了散列表實現(xiàn)。你可使用
Python提供的散列表，并假定能夠獲得平均情況下的性能:常量時間。 散列表是一種功能強大的數(shù)據(jù)結(jié)構(gòu)，其操作速度快，還能讓你以不同的方式建立數(shù)據(jù)模型。
你可能很快會發(fā)現(xiàn)自己經(jīng)常在使用它。
你可以結(jié)合散列函數(shù)和數(shù)組來創(chuàng)建散列表。
沖突很糟糕，你應(yīng)使用可以最大限度減少沖突的散列函數(shù)。
散列表的查找、插入和刪除速度都非常快。
散列表適合用于模擬映射關(guān)系。
一旦填裝因子超過0.7，就該調(diào)整散列表的長度。
散列表可用于緩存數(shù)據(jù)(例如，在Web服務(wù)器上)。
散列表非常適合用于防止重復(fù)。

第六章 廣度優(yōu)先搜索

主要內(nèi)容

簡介了圖（有向圖、無向圖），講解了BFS實現(xiàn)算法（運行時間O(V+E)）。介紹了拓?fù)渑判颉?/p>

廣度優(yōu)先搜索是一種用于圖的查找算法，可幫助回答兩類問題。
第一類問題:從節(jié)點A出發(fā)，有前往節(jié)點B的路徑嗎?
第二類問題:從節(jié)點A出發(fā)，前往節(jié)點B的哪條路徑最短?

小結(jié)

廣度優(yōu)先搜索指出是否有從A到B的路徑。
如果有，廣度優(yōu)先搜索將找出最短路徑。
面臨類似于尋找最短路徑的問題時，可嘗試使用圖來建立模型，再使用廣度優(yōu)先搜索來 解決問題。
有向圖中的邊為箭頭，箭頭的方向指定了關(guān)系的方向，例如，rama→adit表示rama欠adit錢。
無向圖中的邊不帶箭頭，其中的關(guān)系是雙向的，例如，ross - rachel表示“ross與rachel約會，而rachel也與ross約會”。
隊列是先進先出(FIFO)的。
棧是后進先出(LIFO)的。
你需要按加入順序檢查搜索列表中的人，否則找到的就不是最短路徑，因此搜索列表必 須是隊列。
對于檢查過的人，務(wù)必不要再去檢查，否則可能導(dǎo)致無限循環(huán)。

第七章 狄克斯特拉算法

主要內(nèi)容

講解了狄克斯特拉算法的實現(xiàn)，適用范圍為有向無環(huán)圖DAG且沒有負(fù)權(quán)邊。

狄克斯特拉算法包含4個步驟。
(1) 找出“最便宜”的節(jié)點，即可在最短時間內(nèi)到達的節(jié)點。
(2) 更新該節(jié)點的鄰居的開銷，其含義將稍后介紹。
(3) 重復(fù)這個過程，直到對圖中的每個節(jié)點都這樣做了。
(4) 計算最終路徑。

貝爾曼-福德算法(Bellman-Ford algorithm)

小結(jié)

廣度優(yōu)先搜索用于在非加權(quán)圖中查找最短路徑。
狄克斯特拉算法用于在加權(quán)圖中查找最短路徑。
僅當(dāng)權(quán)重為正時狄克斯特拉算法才管用。
如果圖中包含負(fù)權(quán)邊，請使用貝爾曼-福德算法。

第八章 貪婪算法

主要內(nèi)容

講解了如何用貪婪算法解決教室調(diào)度問題、背包問題、集合覆蓋問題。介紹了NP完全問題，詳解了旅行商問題。給出了識別NP完全問題的方法。

貪婪算法很簡單：每步都采取最有的做法。用專業(yè)術(shù)語說，就是你每步都選擇局部最優(yōu)解，最終得到的就是全局最優(yōu)解。

NP完全問題的簡單定義是，以難解著稱的問題.
沒辦法判斷問題是不是NP完全問題，但還是有一些蛛絲馬跡可循的。

• 元素較少時算法的運行速度非常快，但隨著元素數(shù)量的增加，速度會變得非常慢。
• 涉及“所有組合”的問題通常是NP完全問題。
• 不能將問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。
• 如果問題涉及序列(如旅行商問題中的城市序列)且難以解決，它可能就是NP完全問題。
• 如果問題涉及集合(如廣播臺集合)且難以解決，它可能就是NP完全問題。
• 如果問題可轉(zhuǎn)換為集合覆蓋問題或旅行商問題，那它肯定是NP完全問題。

小結(jié)

貪婪算法尋找局部最優(yōu)解，企圖以這種方式獲得全局最優(yōu)解。
對于NP完全問題，還沒有找到快速解決方案。
面臨NP完全問題時，最佳的做法是使用近似算法。
貪婪算法易于實現(xiàn)、運行速度快，是不錯的近似算法。

第九章 動態(tài)規(guī)劃

主要內(nèi)容

通過講解了如何用動態(tài)規(guī)劃方法解決背包問題說明動態(tài)規(guī)劃問題的基本方法–網(wǎng)格，又講解了動態(tài)規(guī)劃問題–最長公共子串。

費曼算法(Feynman algorithm)
步驟如下：
(1) 將問題寫下來。
(2) 好好思考。
(3) 將答案寫下來。

小結(jié)

需要在給定約束條件下優(yōu)化某種指標(biāo)時，動態(tài)規(guī)劃很有用。
問題可分解為離散子問題時，可使用動態(tài)規(guī)劃來解決。
每種動態(tài)規(guī)劃解決方案都涉及網(wǎng)格。
單元格中的值通常就是你要優(yōu)化的值。
每個單元格都是一個子問題，因此你需要考慮如何將問題分解為子問題。
沒有放之四海皆準(zhǔn)的計算動態(tài)規(guī)劃解決方案的公式。

第十章 K最近鄰算法

主要內(nèi)容

講解了KNN算法的原理，引出了機器學(xué)習(xí)的概念，簡單介紹了OCR、創(chuàng)建垃圾郵件過濾器。

畢達哥拉斯公式（歐式距離）
余弦相似度（cosine similarity）
樸素貝葉斯分類器(Naive Bayes classifier)

小結(jié)

KNN用于分類和回歸，需要考慮最近的鄰居。
分類就是編組。
回歸就是預(yù)測結(jié)果(如數(shù)字)。
特征抽取意味著將物品(如水果或用戶)轉(zhuǎn)換為一系列可比較的數(shù)字。
能否挑選合適的特征事關(guān)KNN算法的成敗。

第十一章 接下來如何做

主要內(nèi)容

簡單提及了10個作者認(rèn)為打算深入學(xué)習(xí)者進一步可以選擇的學(xué)習(xí)內(nèi)容和方向。

樹（B樹、紅黑樹、堆、伸展樹）；

反向索引（inverted index）；

傅立葉變換（非常適合用于處理信號）；

并行算法；

MapReduce（映射和歸并，映射是將一個數(shù)組轉(zhuǎn)換為另一個數(shù)組，歸并是將一個數(shù)組轉(zhuǎn)換為一個元素）；

布隆過濾器（概率型數(shù)據(jù)結(jié)構(gòu)，使用散 列表時，答案絕對可靠，而使用布隆過濾器時，答案卻是很可能是正確的）和HyperLogLog（一種類似于布隆過濾器的算法）；

SHA算法（安全散列算法(secure hash algorithm，SHA)函數(shù)，一個散列函數(shù)，它生成一個散列值——一個較短的字符串）；

局部敏感的散列算法（相反的為Simhash）；

Diffie-Hellman密匙交換（如果你對加密感興趣，先著手研究 Diffie-Hellman算法是不錯的選擇:它既優(yōu)雅又不難理解）（Diffie-Hellman算法解決了如下兩個問題： 1. 雙方無需知道加密算法。他們不必會面協(xié)商要使用的加密算法。2. 要破解加密的消息比登天還難。）

線性規(guī)劃（作者覺得最好的算法）（Simplex算法）（如果你對最優(yōu)化感興趣， 就研究研究線性規(guī)劃吧!）。

pdf下載

總結(jié)

以上是生活随笔為你收集整理的算法图解 -- 书评的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。