好書一起讀(85)：演算法筆記

這陣子看了兩本演算法書，《演算法》和《演算法導論》。

前一本讀著很輕鬆，內容基本與大學數據結構課程重疊，示例代碼用java編寫，學習曲線平緩，對應用程序員來說，讀它就挺好。

後一本我是邊看麻省理工的《演算法導論》公開課邊讀的，力不從心，因為我數學基礎不好（詳下），如果不看數學證明，其內容跟前一本就差不多了，數學基礎比較好、對演算法感興趣的朋友，可以嘗試之。

強烈建議各公開課平台的學習資源，質量非常高，相見恨晚！足不出戶，就能學習名校的課程。但學習時別忘了跟著做習題、做筆記、預習複習。

下面是我的《演算法》筆記。

零、思想

重中之重。演算法真正的精髓。內功心法所在。相比之下，後面講到的都是具體招式。

內功心法的意義就在，有朝一日你遇到一個沒有既有經驗的問題，能自己設計出適當的數據結構和演算法，而不是只會用別人的輪子。

演算法的根本思想，是大問題化為多個小問題，逐漸解決之。（《孫子兵法》：治眾如治寡，分數是也；斗眾如斗寡，形名是也。）

1.分治

如果能將大問題拆為同性質的小問題，當小到一定程度，能直接解決之。

則採用分治法，遞歸解決。

2.貪心

如果為小問題找到的最優解，能通過增加一點步驟，解決一個大一點的問題，並依然是最優解。

則採用貪心法，從0開始，逐步蠶食掉大問題。

3.動態規劃

如果用分治法拆出的小問題中常見到相同問題，重複計算它們，成本太高。

則採用備忘法，計算完每個小問題的結果後，記錄之，下次見到同一小問題，不再重複計算。

一、數學基礎

《演算法導論》在附錄中給出了4項必備的數學基礎。

我看了之後，很羨慕考研的同學，他們這幾門課都很紮實。

這4門數學除了是考研數學科目、演算法的基礎外，其實更是觀察世界、指導生活（不僅僅是生產！）的工具，我決定要以看公開課的方式，逐步重新學之。

1.微積分

2.離散數學

3.概率論

4.線性代數

二、線性表

1.按實現分類

順序表：隨機訪問方便，插入刪除成本高，因為一側的元素要「噠噠噠」依次移動一格。

鏈表：隨機訪問麻煩，因為要從頭「一二三」數過去，插入刪除方便，將特定兩三個節點的指針「咔吧」重新接一下就好了。

2.按作用分類

棧：後進先出，直觀理解就是坐電梯。用處主要在處理大問題時，細化為小問題，小問題解決完再繼續處理大問題的時候。計算機的函數調用的核心數據結構。如果不幸小問題沒完沒了，如無限遞歸，則stackoverflow。

隊列：先進先出，講「先來後到」的數據結構。典型使用就是「任務隊列」，先到的先處理。如果允許「插隊」，就是「優先順序隊列」了，讓領導先走！

三、排序

假設有一個初始隊列4132，目標是從小到大排序成1234。

1.冒泡排序

最簡單也最慢的演算法，慢到不少書都不講了。

思想是讓最後一個元素儘力向上爬，遇見比它大的就壓過之(交換次序)，如果遇到比它小的就停下，由小的繼續往上爬。爬到第一個元素時，就保證了第一個元素是全部元素中最小的一個。

不再考慮第一個元素，重複這一過程。4132，1/423，12/43，123/4。

2.選擇排序

每次都從隊列中選出一個最小的元素，放到「已排序隊列」里，直到選完。

/4132，1/432，12/43，12/34。

3.插入排序

每次都從「未排序隊列」中選第一個元素，插到「已排序隊列」的適當位置，直到插完。

我玩撲克時理牌就用這法。

4/132，14/32，134/2，1234

4.希爾排序

先把「相距較大間距」的元素們排序一遍，再適度減小間距再排一遍，最後一次相距零間距排。

4132，先間隔較大間距（這個簡陋例子，姑且間隔1），4與3排序，1與2排序，得3142，再間隔較小間距（本例中直接到0了）排序。

5.快速排序

最被喜歡的排序，既容易理解，又快。

選一個數字為軸，比它小的放左邊，比它大的放右邊，然後對其兩邊各進行這一變化即可。

4132，第一步選4，第二步選1，都是把全部剩餘元素放到同側，不划算，所以隨機選擇軸元素很關鍵。

假設第一步選了3，12放左側，4放右側，右側完結，左側繼續，假設選2為軸，1放左側，右側沒有，即得結果1234。

6.歸併排序

所謂歸併，比如一班和二班已經各排成了從矮到高的有序隊列，想歸併成一隊，怎麼辦？比較一班和二班的排頭，更矮的選出來站到「結果隊列」里，該班的新排頭再跟對方排頭比，以此類推。

歸併成一個新隊列後，再跟別的隊列歸併，直到統統歸併為一隊。

14/23 -> 1|4/23 -> 12|4/3 -> 123|4 -> 1234

7.堆排序

所謂堆，就是一棵每個父節點數值都大於其一切子孫節點數值的完全二叉樹，如果看不懂，先跳到下面看樹那節。

為方便說（放圖太麻煩了，我相信純文字能說清），這次咱們從大到小排序，道理當然是一樣的。

分兩步，一是從無序隊列構造樹，二是從樹輸出有效隊列，結合起來，就是從無序隊列，得到了有序隊列。

第一步，拿一個新節點，放到原樹的最後一個位置，然後使之儘力向上冒泡，直到冒不動為止，再拿下一個新節點。如處理4132：

4 -> 4左下1 -> 4左下1右下3 -> 4左下1右下3，1左下2 -(2冒泡)-> 4左下2右下3，2左下1

第二步，取出根節點放到結果隊列，把最後一個節點僭越到根位置，然後考察其兩個葉子節點，如果有更有實力的，則向最有實力的退位讓賢，交換位置，到新崗位後繼續考察下屬能力，直到降到自己勝任的位置。

4左下2右下3，2左下1 -(取出4，1上位)-> 1左下2右下3 -(3篡位)-> 3左下2右下1 -(取出3，1上位)-> 1左下2 -(2篡位)-> 2左下1 -(取出2)-> 1孤家寡人 -(取出1)-> 結果4321

四、樹

若干節點，及若干連接節點的無向邊，構成的圖，如果從每個節點出發，都能到達任意一個節點（強連通），同時圖中不存在環，即稱為樹。

數據結構中說的樹，在此基礎上再嚴格點，分為若干層。如某團長手下有若干連長，每個連長手下有若干班長，畫組織結構圖，把直接領導和直接下屬連接起來。直接領導稱為父節點，如團長是連長的父節點，連長是其屬下每個班長的父節點；直接下屬稱為子節點；最高長官稱為根節點，即沒有父節點的節點；沒有子節點的節點稱為葉子節點，比如《士兵突擊》里鋼七連只剩老七(連長)和三多(班長)的時候，三多是葉子節點，如果這時三多被老A挖走（實際劇情是老七先走，不贅），則老七堂堂連長，將不幸成為葉子節點。

1.二叉樹

如果樹的每個父節點最多只有兩個子節點，該樹即稱為二叉樹。

最典型用途是二叉查找，即如果每個根節點數值都比其左子樹（此概念望文生義，不贅）任意節點數值更大，比其右子樹的任意節點數值更小，該樹即稱為二叉排序樹。在想尋找某個數值時，可以先將該數值與根節點比，如果比根節點大，則去與其右子樹根節點比，如果比根節點小，則去與其左子樹根節點比，直到找到或比到葉子節點為止。

好像「猜數字」遊戲，一本好書價值1元到256元之內，假設你蠢到看不出那書不可能1元，又聰明到知道採用二叉查找，則該先猜128元，根據主持人說「高了」「低了」再決定猜64還是192元，假如64還是「高了」，則該繼續猜32，以此類推。

2.紅黑樹

強烈推薦看《演算法》中紅黑樹的章節，從2-3樹開始講，講到紅黑樹，學習曲線非常平滑。

二叉樹和紅黑樹都有著清晰的用於保持樹平衡的邏輯，限於篇幅不多講。平衡的目的是保持最差情況下的查找程度為logN(以2為底，總節點數的對數)。

3.散列表

這個不是樹……但在邏輯上放在這裡最好，因為都是用於「查找」的數據結構。

編程中最基本的兩種數據結構，list和map，list就是上文說的線性表，核心是有順序，map就是這裡說的散列表(hashmap)或樹(treemap)，核心是鍵值對。set呢，多以map做底層結構。

樹上面說了，這裡說散列表。

散列表又叫字典，從這字面可知，主要用途是查找，通過鍵(key)查找值(value)，首先，要把鍵算成一個數字，這演算法(散列函數)就是java里類們都要實現的hashcode方法。

然後，有兩種可選的實現方式，一是鏈接法，首先有個主list裝著鍵們，比如123，然後1對應一個list，2對應一個list，3對應一個list，我把鍵算出是1之後，就到1對應的list元素里去找元素。顯然，1對應的list長度越短，查找時間越短，那似乎主list的鍵們越多越好，比如1到30，那每個子list的長度將變為原長度的十分之一，但主list的鍵們也不能太多，比如1到30000，那大部分鍵對應的其實是空，裡面一個元素都沒有，就浪費空間了，所以要權衡。

另一種實現方式是散列法，不存在次list，把鍵算成數字後，直接往主list對應的位置存，如果該位置已經被別的元素佔了(碰撞)怎麼辦？則用某種演算法，算出一個新數，再嘗試往新位置放(再散列)，以此類推。顯然，這種方法，主list的長度也很關鍵，如果太短，則碰撞太多，插入、查找都麻煩，如果太長，又浪費地方。

對兩種方法，散列函數都非常重要，如果所有元素的散列函數都計算出同一個值，散列表就毫無意義了。

五、圖

終於到圖了！這是我最喜歡的部分，好玩，而且熟悉，因為我認識一個同學，數據結構年年掛，直到大四，所以我每年都陪他複習備考一次，老師考卷中的高分的題目，就是考圖的幾個演算法，迪傑斯特拉，普里姆，克魯斯卡爾……好懷念那段日子。

什麼是圖？一堆節點，及若干邊，就構成了圖，根據線路是否有方向性，分為有向圖、無向圖，根據圖中是否有環，分為有環圖、無環圖。

如果任意兩個節點都有線路連接，則稱為強連通圖，這裡主要聊的都是這種。

1.深度優先、廣度優先遍歷

A連B，B連C，B連D，C連E

想把圖裡所有節點都研究一遍，怎麼辦？

從一個節點開始，走向下一個節點，然後再走向下一個節點的下一個節點，直到「眼前無路想回頭」，就是「深度優先遍歷」。在例子里，從A到B，從B到C，從C到E，E回頭到C，C回頭到B，從B到D，完成遍歷。

「廣度優先遍歷」則是，從一個節點開始，先扇面狀把能到的節點都掃一遍(廣嘛)，然後再「移步」到子節點們。在例子里，從A到B，從B到C，從B到D，從C到E，完成遍歷。

2.最小生成樹

如果樹的每條邊都有個權值，要求選出總權值最小的一些邊，讓所有節點都能互相連通，怎麼辦？

這就是「最小生成樹」問題，顯然，選出的結果肯定是一棵樹，樹的兩個條件，連通和無環，連通不必講，為什麼無環？如果有環，去掉任意一條邊，節點們依然相互連通，權值變小了，由此反證，必然無環。

解此問題，兩種方法，一是普里姆演算法，二是克魯斯卡爾演算法，好專業，終於有點演算法的感覺了。

其實都很簡單，先說普里姆，將圖劃為「已解決」和「未解決」兩個部分，一開始「已解決」為空，「未解決」是全集，首先，任選一個點放到「已解決」，然後考察所有從「已解決」連向「未解決」的邊，哪條最短，就把該邊連向的「未解決」節點納入「已解決」集合，如此反覆，直到全部節點都「已解決」，結果就是最小生成樹。

再說克魯斯卡爾，一開始，把每個節點視為一個「分量」，尋找全部「連接兩個不同分量的邊」中最短的一條，將其連接的兩個分量合併為一個分量，並重複這一行為，直到全部節點都屬於同一分量，結果就是最小生成樹。

3.單源最短路徑

最小生成樹研究的是無向圖，最短路徑則研究有向圖。

顧名思義，最短路徑是要求給出從某地到另外某地的最便捷走法，這有兩個演算法，一是迪傑斯特拉演算法，二是貝爾曼福特演算法。

先說迪傑斯特拉，這是類似普里姆的「貪婪演算法」，從一個極小的「已解決」開始，逐步蠶食，直到將「未解決」吃掉。差別在這回每個節點上都有個數字，代表其到起點的距離，每次都選全部「從已解決到未解決的邊」指向的「未解決」節點中，數字最小的一個。比如起點是家，家距離學校500米，家距離市場600米，學校距離公園200米，根據演算法，把學校標註500，市場標註600，500小於600，把學校納入「已解決」，學校進入「已解決」之後，公園也變成了從「已解決」可以到達的「未解決」的節點，用學校的500加200，公園標註為700，與市場的600米相比，600較小，把市場納入「已解決」。注意，這個步驟，如果是普里姆演算法，納入的是公園而非市場，因為普里姆不存在起點，都連上就ok，只考慮哪條邊最短，但迪傑斯特拉有起點，要比較的是「從起點出發直到這裡的距離」。

再說貝爾曼福特，這演算法是把每個節點賦予一個表示「距離起點有多遠」的數值，除了起點外，其他起點一開始都是無窮大，然後依次考察每條邊，如果這條邊能讓指向的節點的數值變小，就將該節點數值變小(收縮)，把所有邊都考察一遍之後，如果這一遍中執行了「收縮操作」，則再把所有邊都考察一遍，直到某一遍完全沒收縮為止。上面的例子，比如考察次序是200-500-600，則第一遍200啥用沒有，500將學校的+∞變為500，600將市場的+∞變為600，這遍進行了收縮，再來一遍，這回200有用了，將公園的+∞變為700，500和600都沒有，這遍也收縮了，再來一遍，200/500/600都沒用，完結。

六、字元串

字元串本質是字元數組。說到演算法，最常說的就是字元串查找的KMP演算法。

比如想從「子龍子龍世無雙」里尋找「子龍子翼」，「子」等於「子」，「龍」等於「龍」，「子」等於「子」，「龍」不等於「翼」，糟糕！這時源文本的「已搜索序列」的「後綴們」有「子龍子龍」「龍子龍」「子龍」「龍」四個，而目標文本的「前綴們」有「子龍子翼」「子龍子」「子龍」「子」四個，考察兩個「們」，發現有個相同元素，即「子龍」，長度為2（如果有多個相同元素，則取最長的），意味著源文本的「已搜索序列」中最後兩個字與目標文本的前兩個字相同，下次用源文本的下一個字「世」與目標文本的第三個字「子」相比即可。如果是樸素演算法，則要用「子龍子龍世無雙」的第一個「龍」字與「子龍子翼」的第一個「子」字相比，KMP演算法比樸素演算法快多了！

七、寫在後面

演算法的水太深，我僅僅入了個門，回頭看看，上面所寫，全是大學《數據結構》的內容，長嘆一聲。

也有更深入學習的意願，但在這之前要鞏固數學基礎，我在看網易公開課上的《線性代數》和《微積分》的公開課。

好在，這些「入門知識」，平日工作倒也夠用，而數學、計算機基礎的鞏固和學習，是一輩子的事，不用太急。

不要哀嘆過去的荒蕪，唯一的方法是立足於現在的狀態，選取最優的進步路線，勤勉地躬行之。

學過一點點經濟學基礎的人，不會為「沉沒成本」沮喪。

數學太美，邏輯太美，演算法太美。

我卻近來才發現。讀書的時候全沒省得。

不省得也沒關係，老老實實聽話就好，現在想想，是「獨立思考」得過於早了。

這是我的人生歷程，沒什麼可後悔，寫這只是想規諫還在念書的朋友。

別急著自行其是，以後的人生里，有的是機會讓你自行決策，還在念書的時候，請聽話。

聽老師的話，好好學習，天天向上。