圖解算法精華（算法圖解閱讀筆記）

2023-10-12 18:37:51 2

圖解算法精華?算法圖解巴爾加瓦，現在小編就來說說關於圖解算法精華?下面內容希望能幫助到你，我們來一起看看吧!

圖解算法精華

算法圖解

巴爾加瓦

207個筆記

1.1 引言

你將學習使用K最近鄰算法編寫推薦系統；

有些問題在有限的時間內是不可解的！書中討論NP完全問題的部分將告訴你，如何識別這樣的問題以及如何設計找到近似答案的算法。

1.2 二分查找

如果你的用戶名為karlmageddon, Facebook可從以A打頭的部分開始查找，但更合乎邏輯的做法是從中間開始查找。

二分查找是一種算法，其輸入是一個有序的元素列表（必須有序的原因稍後解釋）。

你可能不記得什麼是對數了，但很可能記得什麼是冪。log10100相當於問「將多少個10相乘的結果為100」。答案是兩個：10 × 10=100。因此，log10100=2。對數運算是冪運算的逆運算。

1.3 大O表示法

實際上，Bob錯了，而且錯得離譜。列表包含10億個元素時，簡單查找需要10億毫秒，相當於11天！為什麼會這樣呢？因為二分查找和簡單查找的運行時間的增速不同。

也就是說，隨著元素數量的增加，二分查找需要的額外時間並不多，而簡單查找需要的額外時間卻很多。

大O表示法指出了最糟情況下的運行時間

除最糟情況下的運行時間外，還應考慮平均情況的運行時間，這很重要。最糟情況和平均情況將在第4章討論。

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

算法的速度指的並非時間，而是操作數的增速。

談論算法的速度時，我們說的是隨著輸入的增加，其運行時間將以什麼樣的速度增加。

O(log n)比O(n)快，當需要搜索的元素越多時，前者比後者快得越多。

1.4 小結

算法運行時間並不以秒為單位。

算法運行時間是從其增速的角度度量的。

2.1 內存的工作原理

計算機就像是很多抽屜的集合體，每個抽屜都有地址。

接下來介紹數組和鍊表以及它們的優缺點。

2.2 數組和鍊表

一種解決之道是「預留座位」：即便當前只有3個待辦事項，也請計算機提供10個位置，以防需要添加待辦事項。這樣，只要待辦事項不超過10個，就無需轉移。這是一個不錯的權變措施，但你應該明白，它存在如下兩個缺點。

❑ 你額外請求的位置可能根本用不上，這將浪費內存。你沒有使用，別人也用不了。❑ 待辦事項超過10個後，你還得轉移。

對於這種問題，可使用鍊表來解決。

這猶如尋寶遊戲。

排行榜網站使用卑鄙的手段來增加頁面瀏覽量。它們不在一個頁面中顯示整個排行榜，而將排行榜的每項內容都放在一個頁面中，並讓你單擊Next來查看下一項內容。例如，顯示十大電視反派時，不在一個頁面中顯示整個排行榜，而是先顯示第十大反派（Newman）。你必須在每個頁面中單擊Next，才能看到第一大反派（Gustavo Fring）。這讓網站能夠在10個頁面中顯示廣告，但用戶需要單擊Next九次才能看到第一個，真的是很煩。

[插圖]鍊表存在類似的問題。

但如果你需要跳躍，鍊表的效率真的很低。

元素的位置稱為索引。

3.1 遞歸

這個盒子裡有盒子，而盒子裡的盒子又有盒子。鑰匙就在某個盒子中。為找到鑰匙，你將使用什麼算法？

(1) 檢查盒子中的每樣東西。(2) 如果是盒子，就回到第一步。(3) 如果是鑰匙，就大功告成！

遞歸只是讓解決方案更清晰，並沒有性能上的優勢。實際上，在有些情況下，使用循環的性能更好。我很喜歡Leigh Caldwell在StackOverflow上說的一句話：「如果使用循環，程序的性能可能更高；如果使用遞歸，程序可能更容易理解。如何選擇要看什麼對你來說更重要。」

很多算法都使用了遞歸，因此理解這種概念很重要。

3.3 棧

[插圖]本節將介紹一個重要的編程概念——調用棧（call stack）。調用棧不僅對編程來說很重要，使用遞歸時也必須理解這個概念。

遞歸函數也使用調用棧！

原來「盒子堆」存儲在了棧中！這個棧包含未完成的函數調用，每個函數調用都包含還未檢查完的盒子。使用棧很方便，因為你無需自己跟蹤盒子堆——棧替你這樣做了。

使用棧雖然很方便，但是也要付出代價：存儲詳盡的信息可能佔用大量的內存。每個函數調用都要佔用一定的內存，如果棧很高，就意味著計算機存儲了大量函數調用的信息。在這種情況下，你有兩種選擇。

❑ 重新編寫代碼，轉而使用循環。❑ 使用尾遞歸。這是一個高級遞歸主題，不在本書的討論範圍內。另外，並非所有的語言都支持尾遞歸。

3.4 小結

每個遞歸函數都有兩個條件：基線條件和遞歸條件。

所有函數調用都進入調用棧。

調用棧可能很長，這將佔用大量的內存。

4.1 分而治之

使用D&C解決問題的過程包括兩個步驟。(1) 找出基線條件，這種條件必須儘可能簡單。(2) 不斷將問題分解（或者說縮小規模），直到符合基線條件。

首先，找出基線條件。最容易處理的情況是，一條邊的長度是另一條邊的整數倍。

如果一邊長25m，另一邊長50m，那麼可使用的最大方塊為25m×25m。

現在需要找出遞歸條件，這正是D&C的用武之地。根據D&C的定義，每次遞歸調用都必須縮小問題的規模。如何縮小前述問題的規模呢？我們首先找出這塊地可容納的最大方塊。

歐幾裡得算法前面說「適用於這小塊地的最大方塊，也是適用於整塊地的最大方塊」，如果你覺得這一點不好理解，也不用擔心。這確實不好理解，但遺憾的是，要證明這一點，需要的篇幅有點長，在本書中無法這樣做，因此你只能選擇相信這種說法是正確的。如果你想搞明白其中的原因，可參閱歐幾裡得算法。

接下來，從這塊土地中劃出最大的方塊，餘下一塊更小的土地。

餘下的這塊土地滿足基線條件，因為160是80的整數倍。將這塊土地分成兩個方塊後，將不會餘下任何土地！

第一步：找出基線條件。最簡單的數組什麼樣呢？請想想這個問題，再接著往下讀。如果數組不包含任何元素或只包含一個元素，計算總和將非常容易。

第二步：每次遞歸調用都必須離空數組更近一步。

別忘了，遞歸記錄了狀態。

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

諸如Haskell等函數式程式語言沒有循環，因此你只能使用遞歸來編寫這樣的函數。如果你對遞歸有深入的認識，函數式程式語言學習起來將更容易。

符合基線條件時運行第一個定義，符合遞歸條件時運行第二個定義。

4.2 快速排序

快速排序是一種常用的排序算法，比選擇排序快得多。例如，C語言標準庫中的函數qsort實現的就是快速排序。快速排序也使用了D&C。

下面來使用快速排序對數組進行排序。對排序算法來說，最簡單的數組什麼樣呢？還記得前一節的「提示」嗎？就是根本不需要排序的數組。

接下來，找出比基準值小的元素以及比基準值大的元素。

這被稱為分區（partitioning）。現在你有：❑ 一個由所有小於基準值的數字組成的子數組；❑ 基準值；❑ 一個由所有大於基準值的數組組成的子數組。

這裡只是進行了分區，得到的兩個子數組是無序的。但如果這兩個數組是有序的，對整個數組進行排序將非常容易。

如果子數組是有序的，就可以像下面這樣合併得到一個有序的數組：左邊的數組 基準值 右邊的數組。

這個子數組都只有一個元素，而你知道如何對這些數組進行排序。

(1) 選擇基準值。(2) 將數組分成兩個子數組：小於基準值的元素和大於基準值的元素。(3) 對這兩個子數組進行快速排序。

歸納證明剛才你大致見識了歸納證明！歸納證明是一種證明算法行之有效的方式，它分兩步：基線條件和歸納條件。是不是有點似曾相識的感覺？例如，假設我要證明我能爬到梯子的最上面。遞歸條件是這樣的：如果我站在一個橫檔上，就能將腳放到上一個橫檔上。換言之，如果我站在第二個橫檔上，就能爬到第三個橫檔。這就是歸納條件。而基線條件是這樣的，即我已經站在第一個橫檔上。因此，通過每次爬一個橫檔，我就能爬到梯子最頂端。

4.3 再談大O表示法

快速排序的獨特之處在於，其速度取決於選擇的基準值。

來看看第2章介紹的選擇排序，其運行時間為O(n2)，速度非常慢。

還有一種名為合併排序（merge sort）的排序算法，其運行時間為O(n logn)，比選擇排序快得多！快速排序的情況比較棘手，在最糟情況下，其運行時間為O(n2)。

與選擇排序一樣慢！但這是最糟情況。在平均情況下，快速排序的運行時間為O(n log n)。

❑ 這裡說的最糟情況和平均情況是什麼意思呢？❑ 若快速排序在平均情況下的運行時間為O(n log n)，而合併排序的運行時間總是O(n log n)，為何不使用合併排序？它不是更快嗎？

c是算法所需的固定時間量，被稱為常量。例如，print_items所需的時間可能是10毫秒＊n，而print_items2所需的時間為1秒 ＊ n。

通常不考慮這個常量，因為如果兩種算法的大O運行時間不同，這種常量將無關緊要。

但有時候，常量的影響可能很大，對快速查找和合併查找來說就是如此。

這裡要告訴你的是，最佳情況也是平均情況。只要你每次都隨機地選擇一個數組元素作為基準值，快速排序的平均運行時間就將為O(n log n)。

5.1 散列函數

散列函數是這樣的函數，即無論你給它什麼數據，它都還你一個數字。

如果用專業術語來表達的話，我們會說，散列函數「將輸入映射到數字」。你可能認為散列函數輸出的數字沒什麼規律，但其實散列函數必須滿足一些要求。

❑ 它必須是一致的。例如，假設你輸入apple時得到的是4，那麼每次輸入apple時，得到的都必須為4。如果不是這樣，散列表將毫無用處。

❑ 它應將不同的輸入映射到不同的數字。例如，如果一個散列函數不管輸入是什麼都返回1，它就不是好的散列函數。最理想的情況是，將不同的輸入映射到不同的數字。

散列函數總是將同樣的輸入映射到相同的索引。每次你輸入avocado，得到的都是同一個數字。因此，你可首先使用它來確定將鱷梨的價格存儲在什麼地方，並在以後使用它來確定鱷梨的價格存儲在什麼地方。

散列函數知道數組有多大，只返回有效的索引。如果數組包含5個元素，散列函數就不會返回無效索引100。

你可能根本不需要自己去實現散列表，任一優秀的語言都提供了散列表實現。Python提供的散列表實現為字典，你可使用函數dict來創建散列表。

5.2 應用案例

將散列表用於查找

無論你訪問哪個網站，其網址都必須轉換為IP位址。

這不是將網址映射到IP位址嗎？好像非常適合使用散列表囉！這個過程被稱為DNS解析（DNS resolution），散列表是提供這種功能的方式之一。

首先來投票的是Tom，上述代碼列印letthem vote!。接著Mike來投票，列印的也是let them vote!。然後，Mike又來投票，於是列印的就是kick themout!。

來看最後一個應用案例：緩存。如果你在網站工作，可能聽說過進行緩存是一種不錯的做法。下面簡要地介紹其中的原理。假設你訪問網站facebook.com。

(1) 你向Facebook的伺服器發出請求。(2) 伺服器做些處理，生成一個網頁並將其發送給你。(3) 你獲得一個網頁。

現在假設她老問你月球離地球多遠，很快你就記住了月球離地球238900英裡。因此不必再去Google搜索，你就可以直接告訴她答案。這就是緩存的工作原理：網站將數據記住，而不再重新計算。

如果你登錄了Facebook，你看到的所有內容都是為你定製的。你每次訪問facebook.com，其伺服器都需考慮你感興趣的是什麼內容。但如果你沒有登錄，看到的將是登錄頁面。每個人看到的登錄頁面都相同。Facebook被反覆要求做同樣的事情：「當我註銷時，請向我顯示主頁。」有鑑於此，它不讓伺服器去生成主頁，而是將主頁存儲起來，並在需要時將其直接發送給用戶。

這就是緩存，具有如下兩個優點。❑ 用戶能夠更快地看到網頁，就像你記住了月球與地球之間的距離時一樣。下次你侄女再問你時，你就不用再使用Google搜索，立刻就可以告訴她答案。❑ Facebook需要做的工作更少。

緩存是一種常用的加速方式，所有大型網站都使用緩存，而緩存的數據則存儲在散列表中！

Facebook不僅緩存主頁，還緩存About頁面、Contact頁面、Termsand Conditions頁面等眾多其他的頁面。因此，它需要將頁面URL映射到頁面數據。

當你訪問Facebook的頁面時，它首先檢查散列表中是否存儲了該頁面。

僅當URL不在緩存中時，你才讓伺服器做些處理，並將處理生成的數據存儲到緩存中，再返回它。這樣，當下次有人請求該URL時，你就可以直接發送緩存中的數據，而不用再讓伺服器進行處理了。

5.3 衝突

處理衝突的方式很多，最簡單的辦法如下：如果兩個鍵映射到了同一個位置，就在這個位置存儲一個鍊表。

❑ 散列函數很重要。前面的散列函數將所有的鍵都映射到一個位置，而最理想的情況是，散列函數將鍵均勻地映射到散列表的不同位置。❑ 如果散列表存儲的鍊表很長，散列表的速度將急劇下降。然而，如果使用的散列函數很好，這些鍊表就不會很長！

散列函數很重要，好的散列函數很少導致衝突。那麼，如何選擇好的散列函數呢？這將在下一節介紹！

5.4 性能

一條水平線，看到了吧？這意味著無論散列表包含一個元素還是10億個元素，從其中獲取數據所需的時間都相同。

6.3 廣度優先搜索

廣度優先搜索是一種用於圖的查找算法，可幫助回答兩類問題。❑ 第一類問題：從節點A出發，有前往節點B的路徑嗎？❑ 第二類問題：從節點A出發，前往節點B的哪條路徑最短？

在你看來，一度關係勝過二度關係，二度關係勝過三度關係，以此類推。因此，你應先在一度關係中搜索，確定其中沒有芒果銷售商後，才在二度關係中搜索。廣度優先搜索就是這樣做的！

你也可以這樣看，一度關係在二度關係之前加入查找名單。

廣度優先搜索必用隊列 記住這句話

有一個可實現這種目的的數據結構，那就是隊列（queue）。

有一個可實現這種目的的數據結構，那就是隊列（queue）。

隊列的工作原理與現實生活中的隊列完全相同。假設你與朋友一起在公交車站排隊，如果你排在他前面，你將先上車。隊列的工作原理與此相同。隊列類似於棧，你不能隨機地訪問隊列中的元素。隊列只支持兩種操作：入隊和出隊。

隊列是一種先進先出（First In FirstOut, FIFO）的數據結構，而棧是一種後進先出（Last In First Out, LIFO）的數據結構。

6.4 實現圖

首先，需要使用代碼來實現圖。圖由多個節點組成。

每個節點都與鄰近節點相連，如果表示類似於「你→Bob」這樣的關係呢？好在你知道的一種結構讓你能夠表示這種關係，它就是散列表！

記住，散列表讓你能夠將鍵映射到值。在這裡，你要將節點映射到其所有鄰居。

6.5 實現算法

說明更新隊列時，我使用術語「入隊」和「出隊」，但你也可能遇到術語「壓入」和「彈出」。壓入大致相當於入隊，而彈出大致相當於出隊。

首先，創建一個隊列。在Python中，可使用函數deque來創建一個雙端隊列。

這個算法將不斷執行，直到滿足以下條件之一：❑ 找到一位芒果銷售商；❑ 隊列變成空的，這意味著你的人際關係網中沒有芒果銷售商。

檢查一個人之前，要確認之前沒檢查過他，這很重要。為此，你可使用一個列表來記錄檢查過的人。

7.4 負權邊

如果有負權邊，就不能使用狄克斯特拉算法。因為負權邊會導致這種算法不管用。

8.1 教室調度問題

很多人都跟我說，這個算法太容易、太顯而易見，肯定不對。但這正是貪婪算法的優點——簡單易行！貪婪算法很簡單：每步都採取最優的做法。

8.2 背包問題

從這個示例你得到了如下啟示：在有些情況下，完美是優秀的敵人。有時候，你只需找到一個能夠大致解決問題的算法，此時貪婪算法正好可派上用場，因為它們實現起來很容易，得到的結果又與正確結果相當接近。

8.3 集合覆蓋問題

使用下面的貪婪算法可得到非常接近的解。(1) 選出這樣一個廣播臺，即它覆蓋了最多的未覆蓋州。即便這個廣播臺覆蓋了一些已覆蓋的州，也沒有關係。(2) 重複第一步，直到覆蓋了所有的州。

判斷近似算法優劣的標準如下：❑ 速度有多快；❑ 得到的近似解與最優解的接近程度。

貪婪算法是不錯的選擇，它們不僅簡單，而且通常運行速度很快。在這個例子中，貪婪算法的運行時間為O(n2)，其中n為廣播臺數量。

❑ 集合類似於列表，只是不能包含重複的元素；❑ 你可執行一些有趣的集合運算，如併集、交集和差集。

8.4 NP完全問題

這兩條路線相同還是不同你可能認為這兩條路線相同，難道從舊金山到馬林的距離與從馬林到舊金山的距離不同嗎？不一定。有些城市（如舊金山）有很多單行線，因此你無法按原路返回。你可能需要離開原路行駛一兩英裡才能找到上高速的匝道。因此，這兩條路線不一定相同。

NP完全問題的簡單定義是，以難解著稱的問題，如旅行商問題和集合覆蓋問題。很多非常聰明的人都認為，根本不可能編寫出可快速解決這些問題的算法。

Jonah需要組建一個滿足所有這些要求的球隊，可名額有限。等等，Jonah突然間意識到，這不就是一個集合覆蓋問題嗎！

Jonah可使用前面介紹的近似算法來組建球隊。(1) 找出符合最多要求的球員。(2) 不斷重複這個過程，直到球隊滿足要求（或球隊名額已滿）。

NP完全問題無處不在！如果能夠判斷出要解決的問題屬於NP完全問題就好了，這樣就不用去尋找完美的解決方案，而是使用近似算法即可。但要判斷問題是不是NP完全問題很難，易於解決的問題和NP完全問題的差別通常很小。

簡言之，沒辦法判斷問題是不是NP完全問題，但還是有一些蛛絲馬跡可循的。❑ 元素較少時算法的運行速度非常快，但隨著元素數量的增加，速度會變得非常慢。❑ 涉及「所有組合」的問題通常是NP完全問題。❑ 不能將問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。❑ 如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。❑ 如果問題涉及集合（如廣播臺集合）且難以解決，它可能就是NP完全問題。❑ 如果問題可轉換為集合覆蓋問題或旅行商問題，那它肯定是NP完全問題。

8.5 小結

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

第9章 動態規劃

❑ 學習動態規劃，這是一種解決棘手問題的方法，它將問題分成小問題，並先著手解決這些小問題。❑ 學習如何設計問題的動態規劃解決方案。

9.1 背包問題

對於背包問題，你先解決小背包（子背包）問題，再逐步解決原來的問題。

動態規劃是一個難以理解的概念，如果你沒有立即搞懂，也不用擔心，我們將研究很多示例。

此時你很可能心存疑惑：原來的問題說的是4磅的背包，我們為何要考慮容量為1磅、2磅等的背包呢？前面說過，動態規劃從小問題著手，逐步解決大問題。這裡解決的子問題將幫助你解決大問題。請接著往下讀，稍後你就會明白的。

9.2 背包問題FAQ

使用動態規劃時，要麼考慮拿走整件商品，要麼考慮不拿，而沒法判斷該不該拿走商品的一部分。

但使用貪婪算法可輕鬆地處理這種情況！首先，儘可能多地拿價值最高的商品；如果拿光了，再儘可能多地拿價值次高的商品，以此類推。

動態規劃功能強大，它能夠解決子問題並使用這些答案來解決大問題。但僅當每個子問題都是離散的，即不依賴於其他子問題時，動態規劃才管用。

最優解可能導致背包沒裝滿嗎完全可能。假設你還可以偷一顆鑽石。這顆鑽石非常大，重達3.5磅，價值100萬美元，比其他商品都值錢得多。你絕對應該把它給偷了！但當你這樣做時，餘下的容量只有0.5磅，別的什麼都裝不下。

9.3 最長公共子串

❑ 動態規劃可幫助你在給定約束條件下找到最優解。在背包問題中，你必須在背包容量給定的情況下，偷到價值最高的商品。❑ 在問題可分解為彼此獨立且離散的子問題時，就可使用動態規劃來解決。

要設計出動態規劃解決方案可能很難，這正是本節要介紹的。下面是一些通用的小貼士。❑ 每種動態規劃解決方案都涉及網格。❑ 單元格中的值通常就是你要優化的值。在前面的背包問題中，單元格的值為商品的價值。❑ 每個單元格都是一個子問題，因此你應考慮如何將問題分成子問題，這有助於你找出網格的坐標軸。

用於解決這個問題的網格是什麼樣的呢？要確定這一點，你得回答如下問題。❑ 單元格中的值是什麼？❑ 如何將這個問題劃分為子問題？❑ 網格的坐標軸是什麼？

計算機科學家有時會開玩笑說，那就使用費曼算法（Feynmanalgorithm）。這個算法是以著名物理學家理察·費曼命名的，其步驟如下。(1) 將問題寫下來。(2) 好好思考。(3) 將答案寫下來。

計算機科學家真是一群不按常理出牌的人啊！

需要注意的一點是，這個問題的最終答案並不在最後一個單元格中！對於前面的背包問題，最終答案總是在最後的單元格中。但對於最長公共子串問題，答案為網格中最大的數字——它可能並不位於最後的單元格中。

我們回到最初的問題：哪個單詞與hish更像？hish和fish的最長公共子串包含三個字母，而hish和vista的最長公共子串包含兩個字母。因此Alex很可能原本要輸入的是fish。

動態規劃都有哪些實際應用呢？❑ 生物學家根據最長公共序列來確定DNA鏈的相似性，進而判斷兩種動物或疾病有多相似。最長公共序列還被用來尋找多發性硬化症治療方案。❑ 你使用過諸如git diff等命令嗎？它們指出兩個文件的差異，也是使用動態規劃實現的。❑ 前面討論了字符串的相似程度。編輯距離（levenshteindistance）指出了兩個字符串的相似程度，也是使用動態規劃計算得到的。編輯距離算法的用途很多，從拼寫檢查到判斷用戶上傳的資料是否是盜版，都在其中。❑ 你使用過諸如Microsoft Word等具有斷字功能的應用程式嗎？它們如何確定在什麼地方斷字以確保行長一致呢？使用動態規劃！

9.4 小結

❑ 需要在給定約束條件下優化某種指標時，動態規劃很有用。❑ 問題可分解為離散子問題時，可使用動態規劃來解決。❑ 每種動態規劃解決方案都涉及網格。❑ 單元格中的值通常就是你要優化的值。❑ 每個單元格都是一個子問題，因此你需要考慮如何將問題分解為子問題。❑ 沒有放之四海皆準的計算動態規劃解決方案的公式。

第10章 K最近鄰算法

❑ 學習使用K最近鄰算法創建分類系統。❑ 學習特徵抽取。❑ 學習回歸，即預測數值，如明天的股價或用戶對某部電影的喜歡程度。❑ 學習K最近鄰算法的應用案例和局限性。

10.1 橙子還是柚子

請看右邊的水果，是橙子還是柚子呢？我知道，柚子通常比橙子更大、更紅。

如果判斷這個水果是橙子還是柚子呢？一種辦法是看它的鄰居。來看看離它最近的三個鄰居。

在這三個鄰居中，橙子比柚子多，因此這個水果很可能是橙子。祝賀你，你剛才就是使用K最近鄰（k-nearestneighbours, KNN）算法進行了分類！這個算法非常簡單。

KNN算法雖然簡單卻很有用！要對東西進行分類時，可首先嘗試這種算法。下面來看一個更真實的例子。

10.2 創建推薦系統

假設你是Netflix，要為用戶創建一個電影推薦系統。從本質上說，這類似於前面的水果問題！

你可以將所有用戶都放入一個圖表中。[插圖]這些用戶在圖表中的位置取決於其喜好，因此喜好相似的用戶距離較近。假設你要向Priyanka推薦電影，可以找出五位與他最接近的用戶。

假設在對電影的喜好方面，Justin、JC、Joey、Lance和Chris都與Priyanka差不多，因此他們喜歡的電影很可能Priyanka也喜歡！

有了這樣的圖表以後，創建推薦系統就將易如反掌：只要是Justin喜歡的電影，就將其推薦給Priyanka。

但還有一個重要的問題沒有解決。在前面的圖表中，相似的用戶相距較近，但如何確定兩位用戶的相似程度呢？

從上圖可知，水果A和B比較像。下面來度量它們有多像。要計算兩點的距離，可使用畢達哥拉斯公式。

假設你要比較的是Netflix用戶，就需要以某種方式將他們放到圖表中。因此，你需要將每位用戶都轉換為一組坐標，就像前面對水果所做的那樣。

下面是一種將用戶轉換為一組數字的方式。用戶註冊時，要求他們指出對各種電影的喜歡程度。這樣，對於每位用戶，都將獲得一組數字！

這個距離公式很靈活，即便涉及很多個數字，依然可以使用它來計算距離。你可能會問，涉及5個數字時，距離意味著什麼呢？這種距離指出了兩組數字之間的相似程度。

太好了！現在要向Priyanka推薦電影將易如反掌：只要是Justin喜歡的電影，就將其推薦給Priyanka，反之亦然。你這就創建了一個電影推薦系統！

如果你是Netflix用戶，Netflix將不斷提醒你：多給電影評分吧，你評論的電影越多，給你的推薦就越準確。現在你明白了其中的原因：你評論的電影越多，Netflix就越能準確地判斷出你與哪些用戶類似。

你求這些人打的分的平均值，結果為4.2。這就是回歸（regression）。你將使用KNN來做兩項基本工作——分類和回歸：

❑ 分類就是編組；❑ 回歸就是預測結果（如一個數字）。

回歸很有用。假設你在伯克利開個小小的麵包店，每天都做新鮮麵包，需要根據如下一組特徵預測當天該烤多少條麵包：❑ 天氣指數1～5（1表示天氣很糟，5表示天氣非常好）；❑ 是不是周末或節假日（周末或節假日為1，否則為0）；❑ 有沒有活動（1表示有，0表示沒有）。你還有一些歷史數據，記錄了在各種不同的日子裡售出的麵包數量。

今天是周末，天氣不錯。根據這些數據，預測你今天能售出多少條麵包呢？我們來使用KNN算法，其中的K為4。首先，找出與今天最接近的4個鄰居。

將這些天售出的麵包數平均，結果為218.75。這就是你今天要烤的麵包數！

餘弦相似度前面計算兩位用戶的距離時，使用的都是距離公式。還有更合適的公式嗎？在實際工作中，經常使用餘弦相似度（cosine similarity）。假設有兩位品味類似的用戶，但其中一位打分時更保守。他們都很喜歡Manmohan Desai的電影AmarAkbar Anthony，但Paul給了5星，而Rowan只給4星。如果你使用距離公式，這兩位用戶可能不是鄰居，雖然他們的品味非常接近。餘弦相似度不計算兩個矢量的距離，而比較它們的角度，因此更適合處理前面所說的情況。本書不討論餘弦相似度，但如果你要使用KNN，就一定要研究研究它！

所謂合適的特徵，就是：❑ 與要推薦的電影緊密相關的特徵；❑ 不偏不倚的特徵（例如，如果只讓用戶給喜劇片打分，就無法判斷他們是否喜歡動作片）。

你認為評分是不錯的電影推薦指標嗎？我給The Wire的評分可能比HouseHunters高，但實際上我觀看HouseHunters的時間更長。該如何改進Netflix的推薦系統呢？

在挑選合適的特徵方面，沒有放之四海皆準的法則，你必須考慮到各種需要考慮的因素。

10.3 機器學習簡介

KNN算法真的是很有用，堪稱你進入神奇的機器學習領域的領路人！機器學習旨在讓計算機更聰明。你見過一個機器學習的例子：創建推薦系統。下面再來看看其他一些例子。

OCR指的是光學字符識別（opticalcharacter recognition），這意味著你可拍攝印刷頁面的照片，計算機將自動識別出其中的文字。Google使用OCR來實現圖書數位化。OCR是如何工作的呢？我們來看一個例子。請看下面的數字。

如何自動識別出這個數字是什麼呢？可使用KNN。(1) 瀏覽大量的數字圖像，將這些數字的特徵提取出來。(2) 遇到新圖像時，你提取該圖像的特徵，再找出它最近的鄰居都是誰！

一般而言，OCR算法提取線段、點和曲線等特徵。

OCR的第一步是查看大量的數字圖像並提取特徵，這被稱為訓練（training）。大多數機器學習算法都包含訓練的步驟：要讓計算機完成任務，必須先訓練它。下一個示例是垃圾郵件過濾器，其中也包含訓練的步驟。

垃圾郵件過濾器使用一種簡單算法——樸素貝葉斯分類器（Naive Bayesclassifier），你首先需要使用一些數據對這個分類器進行訓練。

樸素貝葉斯分類器也是一種簡單而極其有效的算法。我們鍾愛這樣的算法！

未來很難預測，由於涉及的變數太多，這幾乎是不可能完成的任務。

11.1 樹

對於其中的每個節點，左子節點的值都比它小，而右子節點的值都比它大。

然而，二叉查找樹的插入和刪除操作的速度要快得多。

如果你對資料庫或高級數據結構感興趣，請研究如下數據結構：B樹，紅黑樹，堆，伸展樹。

11.2 反向索引

這種數據結構被稱為反向索引（invertedindex），常用於創建搜尋引擎。

11.3 傅立葉變換

絕妙、優雅且應用廣泛的算法少之又少，傅立葉變換算是一個。BetterExplained是一個傑出的網站，致力於以通俗易懂的語言闡釋數學，它就傅立葉變換做了一個絕佳的比喻：給它一杯冰沙，它能告訴你其中包含哪些成分[插圖]。換言之，給定一首歌曲，傅立葉變換能夠將其中的各種頻率分離出來。

這種理念雖然簡單，應用卻極其廣泛。例如，如果能夠將歌曲分解為不同的頻率，就可強化你關心的部分，如強化低音並隱藏高音。傅立葉變換非常適合用於處理信號，可使用它來壓縮音樂。為此，首先需要將音頻文件分解為音符。傅立葉變換能夠準確地指出各個音符對整個歌曲的貢獻，讓你能夠將不重要的音符刪除。這就是MP3格式的工作原理！

數位訊號並非只有音樂一種類型。JPG也是一種壓縮格式，也採用了剛才說的工作原理。傅立葉變換還被用來地震預測和DNA分析。

使用傅立葉變換可創建類似於Shazam這樣的音樂識別軟體。傅立葉變換的用途極其廣泛，你遇到它的可能性極高！

11.4 並行算法

為提高算法的速度，你需要讓它們能夠在多個內核中並行地執行！

並行算法設計起來很難，要確保它們能夠正確地工作並實現期望的速度提升也很難。有一點是確定的，那就是速度的提升並非線性的，因此即便你的筆記本電腦裝備了兩個而不是一個內核，算法的速度也不可能提高一倍，其中的原因有兩個。

並行性管理開銷。假設你要對一個包含1000個元素的數組進行排序，如何在兩個內核之間分配這項任務呢？如果讓每個內核對其中500個元素進行排序，再將兩個排好序的數組合併成一個有序數組，那麼合併也是需要時間的。❑ 負載均衡。假設你需要完成10個任務，因此你給每個內核都分配5個任務。但分配給內核A的任務都很容易，10秒鐘就完成了，而分配給內核B的任務都很難，1分鐘才完成。這意味著有那麼50秒，內核B在忙死忙活，而內核A卻閒得很！你如何均勻地分配工作，讓兩個內核都一樣忙呢？

要改善性能和可擴展性，並行算法可能是不錯的選擇！

11.5 MapReduce

有一種特殊的並行算法正越來越流行，它就是分布式算法。在並行算法只需兩到四個內核時，完全可以在筆記本電腦上運行它，但如果需要數百個內核呢？在這種情況下，可讓算法在多臺計算機上運行。MapReduce是一種流行的分布式算法，你可通過流行的開源工具Apache Hadoop來使用它。

分布式算法非常適合用於在短時間內完成海量工作，其中的MapReduce基於兩個簡單的理念：映射（map）函數和歸併（reduce）函數。

歸併函數可能令人迷惑，其理念是將很多項歸併為一項。映射是將一個數組轉換為另一個數組。

而歸併是將一個數組轉換為一個元素。

11.6 布隆過濾器和HyperLogLog

布隆過濾器是一種概率型數據結構，它提供的答案有可能不對，但很可能是正確的。為判斷網頁以前是否已搜集，可不使用散列表，而使用布隆過濾器。使用散列表時，答案絕對可靠，而使用布隆過濾器時，答案卻是很可能是正確的。

❑ 可能出現錯報的情況，即Google可能指出「這個網站已搜集」，但實際上並沒有搜集。❑ 不可能出現漏報的情況，即如果布隆過濾器說「這個網站未搜集」，就肯定未搜集。

布隆過濾器的優點在於佔用的存儲空間很少。使用散列表時，必須存儲Google搜集過的所有URL，但使用布隆過濾器時不用這樣做。布隆過濾器非常適合用於不要求答案絕對準確的情況，前面所有的示例都是這樣的。對bit.ly而言，這樣說完全可行：「我們認為這個網站可能是惡意的，請倍加小心。」

面臨海量數據且只要求答案八九不離十時，可考慮使用概率型算法！

11.7 SHA算法

另一種散列函數是安全散列算法（secure hash algorithm, SHA）函數。

說明SHA生成的散列值很長，這裡截短了。你可使用SHA來判斷兩個文件是否相同，這在比較超大型文件時很有用。假設你有一個4 GB的文件，並要檢查朋友是否也有這個大型文件。為此，你不用通過電子郵件將這個大型文件發送給朋友，而可計算它們的SHA散列值，再對結果進行比較。

SHA還讓你能在不知道原始字符串的情況下對其進行比較。例如，假設Gmail遭到攻擊，攻擊者竊取了所有的密碼！你的密碼暴露了嗎？沒有，因為Google存儲的並非密碼，而是密碼的SHA散列值！你輸入密碼時，Google計算其散列值，並將結果同其資料庫中的散列值進行比較。

Google只是比較散列值，因此不必存儲你的密碼！SHA被廣泛用於計算密碼的散列值。這種散列算法是單向的。你可根據字符串計算出散列值。

當前，最安全的密碼散列函數是bcrypt，但沒有任何東西是萬無一失的。

11.8 局部敏感的散列算法

SHA還有一個重要特徵，那就是局部不敏感的。

如果你修改其中的一個字符，再計算其散列值，結果將截然不同！[插圖]這很好，讓攻擊者無法通過比較散列值是否類似來破解密碼。

有時候，你希望結果相反，即希望散列函數是局部敏感的。

❑ Google使用Simhash來判斷網頁是否已搜集。❑ 老師可以使用Simhash來判斷學生的論文是否是從網上抄的。❑ Scribd允許用戶上傳文檔或圖書，以便與人分享，但不希望用戶上傳有版權的內容！這個網站可使用Simhash來檢查上傳的內容是否與小說《哈利·波特》類似，如果類似，就自動拒絕。

需要檢查兩項內容的相似程度時，Simhash很有用。

11.9 Diffie-Hellman密鑰交換

這裡有必要提一提Diffie-Hellman算法，它以優雅的方式解決了一個古老的問題：如何對消息進行加密，以便只有收件人才能看懂呢？

在二戰期間，德國人使用的加密算法比這複雜得多，但還是被破解了。Diffie-Hellman算法解決了如下兩個問題。

❑ 雙方無需知道加密算法。他們不必會面協商要使用的加密算法。❑ 要破解加密的消息比登天還難。

Diffie-Hellman使用兩個密鑰：公鑰和私鑰。顧名思義，公鑰就是公開的，可將其發布到網站上，通過電子郵件發送給朋友，或使用其他任何方式來發布。你不必將它藏著掖著。有人要向你發送消息時，他使用公鑰對其進行加密。加密後的消息只有使用私鑰才能解密。只要只有你知道私鑰，就只有你才能解密消息！

11.10 線性規劃

最好的東西留到最後介紹。線性規劃是我知道的最酷的算法之一。

線性規劃是一個寬泛得多的框架，圖問題只是其中的一個子集。但願你聽到這一點後心潮澎湃！

11.11 結語

本章簡要地介紹了10個算法，唯願這讓你知道還有很多地方等待你去探索。在我看來，最佳的學習方式是找到感興趣的主題，然後一頭扎進去，而本書便為你這樣做打下了堅實的基礎。

微信讀書

,