我的第一本算法書

四年前，當我決定找工作後大概又過一年時間，經歷好幾場面試又經由身邊大佬提醒，我終於意識到自己作爲技術人員所欠缺的點之一：深度不夠。 我提升深度的方法，大致分作兩個階段。 第一階段是看教學視頻，視頻來源於兩位老師，它們是李建忠老師的《C++設計模式》，以及侯捷老師的一系列C++教學視頻。 看設計模式當時，我的感受又分作兩點，一是前人的抽象總結能力真厲害，二是搭建我們項目的幾位哥哥好厲害，他們在項目中用到許多設計模式，那種學習同時能於實際項目中立馬驗證的感覺真不錯。 看完侯捷老師的視頻，我寫過一篇更新以整理自己的收穫：除收穫技術認知之外，聽侯捷老師沉穩、溫和的講課讓我靜心；知道底層原理之後的“胸中自有溝壑”，依然是我喜歡的評語。 第二階段是看書，我已經整理過許多篇文章來講述自己如何養成閱讀習慣以及讀書如何對我產生影響：我讀很多書，很多不同類型的書，這些書幫助我以不同視角去看世界、看自己，其中一個方向是技術。關於技術，近四年的讀書，可以這樣分類：從《Python源碼剖析》，到HTTP: The Definitive Guide，到《操作系統導論》，再到《深入理解軟件性能》，大概每年都有一本主要的每天都會閱讀的技術書。 隨着面試次數增多，我發現自己突破不了一面的很大一個原因是：算法題沒做出來。刷題對我來說，是一件很難堅持事情，於是我便找尋折中方案：既然已經養成閱讀習慣，不然在每天的某個固定時間段讀一讀專講做題的書好啦？ 由此，我依次讀完《程序員面試金典》《劍指Offer：專項練習版》《我的第一本算法書》，正閱讀的是《算法（第4版）》。（對的，《算法》這本書，目前進展龜速……） 《我的第一本算法書》，今年3月便已經讀完，這本書的作者是一位日本作家，有日本作家那種簡練、實用風格，簡練於是短小；本書，算是一本算法方向的入門書籍。作者在書中說：“數據存儲於內存時，決定了數據順序和位置關係的便是‘數據結構’，而算法是藉助於數據結構來計算或者解決問題的步驟。” 我不確定自己遲遲不寫本書讀書筆記的原因是由於本書太短小，還是在於就算法和數據結構這一塊的理解不夠自信；總之，就這樣一週周耽擱下來。轉眼已到10月，今年已經讀完但沒寫讀書筆記的書還有很多，可不能再拖。 我強迫自己先靠記憶行事，列舉出數據結構與算法都有哪些內容。 常用的數據結構有數組、字符串（也可以算作數組）、鏈表、隊列（先進先出）、棧（後進先出）、哈希表、樹（二叉樹感覺出現的會更多些、B+樹曾經有過一篇博客整理、堆也是一種樹）、圖。 排序是最基礎內容，絕大部分基於數組，有時候會和鏈表聯動，也會需要對鏈表進行排序。 （關於排序，我曾經有一個囧囧問答。面試官問我：“歸併排序知道麼？”我回答說：“我不太知道，但比較熟悉冒泡排序。”啊！當我會爲面試做些準備時候，開始對這回答感到慚愧，特別是我說自己熟悉冒泡排序時，似乎還帶着些驕傲情緒。） （啊哈哈，我現在寫出來其實是有臉紅的，記下之後又生出些坦然，坦然接受當年那個不想着跳槽的我；然後，讀書筆記偏了題，我將本篇加到“第四份工作”系列。） 對排序過的數據進行二分查找，會將時間複雜度從遍歷的O(n)縮小到O(log2n)。 如果某個題目某種場景中需要對字符串或是鏈表做些判定（比如字符串是否迴文，鏈表是否有環），可以使用的算法之一叫做“雙指針”，一快一慢或者一前一後。 哈希表，常用來以空間換時間，當數據存儲於哈希表時，定位數據的時間複雜度，可以縮小到O(1)。 隊列與棧的實現，可以是一道題目。但它們更多是給其它算法打輔助，比如二叉樹的廣度優先搜索，需要用到隊列，而深度優先搜索，則使用棧。 書中內容雖然簡潔，但除了以上我能看懂部分之外，還有安全算法以及許多需要很花時間、心力去學習的內容，比如回溯法、動態規劃、聚類、A*等。 回溯法和動態規劃，很常見，我在閱讀當時有搞懂算法流程。但現在？老話常談，我已然不能（閱讀當時也不太能）使用自己語言將它們呈現出來。 《我的第一本算法書》是一本有許多圖片的書，書中圖片很好看，對算法的闡述很直觀。然而，僅僅看書真的能夠幫助自己提高做題成功率麼？ 就我的經驗來看，答案是可以的。 隨着看的算法、解法多些，我開始對算法有一種“慢慢都能理解”的感受。對的，此處又關於讀書，即便讀過之後會忘記，但一點點積攢，借不同書一遍遍思考，慢慢將那些不熟悉記憶變做較熟悉的，較熟悉的變做熟悉的，慢慢匯總成一種對於數據結構和算法的一個籠統信心：算法題並不難，一點點回憶，是能想出解決方案來的，請不要害怕。 當然，臨上陣時依然會緊張，那些不熟悉題目，在有限時間內依然會做不出來。這信心對我說：“別怕，你過去的積攢已經讓成功做題的概率，更大了些。” 最後，要再談一談我對面試中需要做算法題態度的轉變。最開始，我是全不知道面試要現場做題的，也就對面試不做準備，全靠工作中的不多積攢與面試當時的“聰明才智”。待發現面試時要做題，一開始的想法是牴觸的：“這些工作中又不常用，真不知道考了做啥。”當自己看了些算法書，又生出許多崇拜：“還能這樣做麼？數據結構與算法確實該是計算機基礎，多看些基礎內容，對敲代碼，對拓展思維，是真會有些幫助的。” 技術迭代很快，AI已經到來，對於“瞭解更多底層規則後對新事物的理解速度會變快”，我依然相信着。

上學期通過小破站先學了部分數據結構與算法，今天開設課程的第一節課，我坐在一個靠牆的位置邊看這本書邊在自己的書上做筆記，特別簡單易懂。我對計算機其實是有些興趣指引的，但大一一整年都在學各種數學，我也學得一塌糊塗哈哈。還有相對於學校開的C語言課程，我更想學習與人工智能相關性更大的Python語言……等等等等。意識到，跟着老師走，等着他/她來投餵，對我來說是一種惰性，吸收的知識不夠，遺忘速度太快…所以採用主動學習的狀態，加油啦

什麼是能力？把晦澀難懂的專業術語變成簡單通俗的語言傳達給你。這本書就是如此。越來越喜歡閱讀這類輕鬆的書，在學習中體會快樂，在快樂中收穫知識！ 若上學時有幸遇見這本書，可能會對數據結構和各類算法理解得更加透徹吧！好在現在也不晚。 有趣，值得一讀。

日本人寫的知識工具書、科普書或技術教程都非常容易懂，真保姆式教學，把讀者當作白紙一般初學者對待。另外，日本教材普遍喜歡利用圖解大大降低理解難度。 但比起書我還是喜歡視頻講解，就去B站搜索了排序算法，竟然發現有人利用谷歌的notebookLM把整本書都做成了教學視頻，視頻合集叫“第一本算法書”。心中佩服，雖然我也用它整理知識和做ppt，但搞一整套教學視頻還是很花功夫。

對於算法初學者是很好的讀物，配合精彩的插圖，簡潔的描述，感覺全書脈絡很清晰，希望順着這個思路，可以多介紹些東西。 對於聚類算法，之前瞭解的比較少，前段時間算法同事分享聚類知識，到現在看到這裏更清楚了些，很不錯，瞭解算法第一步。

《我的第一本算法書》以大量動畫式插圖，將鏈表、數組、棧等 7 種數據結構及二分查找、快速排序等 26 個基礎算法的原理與操作娓娓道來，大幅降低了抽象概念的理解門檻。排版清新、色彩柔和，對沒有深厚數學背景的讀者也十分友好，被多篇讀者稱爲“人人都能看懂的算法入門書”。書中每章配合步驟圖與實戰示例，幫助讀者在閱讀過程中就能動手驗證，對編程初學者和需要系統複習算法的職場人都頗具實用價值。若你渴望在輕鬆的視覺體驗中迅速建立算法與數據結構的整體框架，這本書會是理想的起點。 下面是一些總結： 第1章　數據結構 • 本章指出數據結構決定數據在內存中的排列方式，並通過電話簿示例說明順序與索引的權衡。 • 1-2 鏈表：數據分散、靠指針串聯，插入刪除 O(1)，但訪問需從頭開始，適合頻繁修改的場景。 • 1-3 數組：支持隨機訪問，但插入刪除需移動元素，時間複雜度均爲 O(n)；適合讀多寫少。 • 1-4 棧：後進先出，典型應用是表達式匹配與深度優先搜索。 • 1-5 隊列：先進先出，用於廣度優先搜索等需要“先來先服務”的場合。 • 1-6 哈希表：利用哈希函數加速查詢，衝突可用鏈地址法或開放地址法處理；在密碼學中需注意哈希的不可逆性。 • 1-7 堆：樹形結構，父節點不大於子節點，根節點最小，支持 O(1) 取最值與 O(log n) 調整，常用於優先隊列和 Dijkstra 算法。 • 1-8 二叉查找樹：左子樹所有節點小於根，右子樹大於根，查找、插入、刪除平均 O(log n)，最壞情況取決於樹高；可通過平衡機制保持效率。 第2章　排序 • 本章指出排序是將序列按升序排布的過程，並展示了冒泡、選擇、插入、堆、歸併、快速等常見算法。 • 2-2 冒泡排序：通過相鄰交換把最小元素逐步浮到左側，最壞與平均複雜度均爲 O(n²)。 • 2-3 選擇排序：每輪找剩餘最小元素與左端交換，比較次數相同但交換次數少，複雜度仍爲 O(n²)。 • 2-4 插入排序：維護已排好序的前綴，右側元素逐個插入，最壞 O(n²)，但在近乎有序序列上表現佳。 • 2-5 堆排序：利用堆性質，整體複雜度 O(n log n)，比冒泡等更高效。 • 2-6 歸併排序：分治思想，拆分到單元素後合併，總時間 O(n log n)。 • 2-7 快速排序：隨機選基準值 partition 後遞歸，期望 O(n log n)，最壞 O(n²)，實踐中最快。 第3章　數組的查找 • 3-1 線性查找：從數組首元素開始逐個比較，適用於無序數據，複雜度 O(n)。 • 3-2 二分查找：要求數組有序，每次將搜索範圍減半，複雜度 O(log n)，在頻繁查找、少量插入的場景優勢明顯。 第4章　圖的搜索 • 本章首先定義圖由頂點和邊組成，並區分有向與無向圖，爲後續搜索算法奠定基礎。 • 4-2 廣度優先搜索：從起點層序擴展，最先發現的路徑即最短，用於尋找無權圖的最短路徑。 • 4-3 深度優先搜索：沿一條路徑儘可能深入，再回溯，實現上採用棧，適合探測連通分量或迷宮。 • 4-4 貝爾曼-福特算法：通過鬆弛邊直到無更新，可處理負權重邊，複雜度 O(nm)。 • 4-5 狄克斯特拉算法：結合優先隊列選擇當前最短距離頂點，複雜度 O(m + n log n)，不能處理負權重邊。 • 4-6 A*算法：在狄克斯特拉基礎上加入啓發式評估，優先擴展最有希望的節點，可顯著減少搜索節點數，常用於遊戲路徑尋找。 第5章　安全算法 • 本章概述互聯網通信需解決的竊聽、假冒、篡改、否認四大問題，並引入加密、MAC、數字簽名、證書等技術。 • 5-2 加密基礎：對稱加密使用同一密鑰加解密，示例凱撒密碼、AES；難點在於密鑰分發。 • 5-3 哈希函數：將任意數據映射爲固定長度值，不可逆，用於密碼存儲等場景。 • 5-4 共享密鑰加密：發送方與接收方使用同一密鑰，加密速度快但密鑰分發需額外保護。 • 5-5 公開密鑰加密：成對密鑰，公鑰加密、私鑰解密，解決密鑰分發問題，但速度慢。 • 5-6 混合加密：結合對稱與非對稱優點，先用對稱加密數據，再用非對稱加密對稱密鑰，SSL/TLS 即採用此方案。 • 5-7 迪菲-赫爾曼密鑰交換：雙方在不安全信道中協商出共享密鑰，安全性依賴離散對數難題。 • 5-8 消息認證碼：利用共享密鑰生成 MAC，可檢測篡改但無法證明來源；用於保證數據完整性。 • 5-9 數字簽名：用發送方私鑰簽名，公鑰驗證，可提供來源認證與不可否認性，但需證書綁定公鑰。 • 5-10 數字證書：由認證中心簽發，用於驗證公鑰所有權，構建 PKI 信任鏈。 第6章　聚類 • 本章指出聚類是按相似性把數據分成簇的過程，相似性的定義取決於數據類型和應用場景。 • 6-2 k-means 算法：需預先指定 k，隨機選中心迭代分配數據與更新中心，直至收斂；層次聚類則無需預設簇數，通過不斷合併最近簇完成。 第7章　其他算法 • 7-1 歐幾里得算法：輾轉相除求最大公約數，時間複雜度接近 O(log min(a,b))。 • 7-2 素性測試：試除法適合小數，費馬測試與改進的米勒-拉賓用於大數；AKS 證明了多項式時間素性檢測可行但實際常以費馬測試爲主。 • 7-3 網頁排名：通過鏈接結構計算網頁重要性，用隨機跳轉模型解決環狀鏈接導致的無限循環問題。 • 7-4 漢諾塔：遞歸思想的經典示例，證明了任何 n 個圓盤均可在 2ⁿ⁻¹ 步內完成移動。

世界圖書日時買了幾本人工智能（AI）相關的書籍，剛看完《算法圖解》與《我的第一本算法書》這兩本，前一本是美國人寫的，後一本是日本人寫的。雖然都是寫算法的書，也都是用圖說明算法的書，但差異還是蠻大！ 算法是什麼呢？——計算或解決問題的步驟。算法與程序有些相似，區別在於：程序是以計算機能夠理解的編程語言編寫而成，可在計算機上運行；算法是以人類能夠理解的方式描述的，用於編寫程序之前。不過，這個過程中，到哪裏爲止是算法、從哪裏開始是程序，並沒有明確的界限。 即使同一個算法，編程語言也許不同，寫出來的程序也可能不同；即便使用相同的編程語言，寫程序的人不同，編寫出的程序也會不同。 算法的運行時間是從輸入數據到輸出數據結果這個過程所花費的時間。就算使用同樣的算法，花費的時間也會根據所用計算機的不同而產生偏差。在這裏，使用“步數”來描述運行時間，“1步”就是計算的基本單位。通過測試“計算從開始到結束總共執行了多少步”來求得算法的運行時間。  《我的第一本算法書》 先說明何爲算法，與程序的區別； 然後分別介紹了7種數據結構； 最後是排序、查找、搜索、安全算法（哈希函數和7種加密），以及聚類（K-means算法）和其他算法（歐幾里得算法、素性測試、網頁排名、漢諾塔）的步驟和原理，每步都用一張圖解說。的確是以人類能夠理解的方式描述！ 而且邏輯非常清晰，比如，講解完離散數學中的圖、加權圖、有向圖後，隨後介紹應用這些圖的廣度優先搜索、深度優先搜索，還有求最短路徑的貝爾曼-福特算法（Bellman-Ford）、狄克斯特拉算法（Dijkstra）、A*（A-Star）算法。同樣都是求最短路徑，還會對比三種算法在不同情境下的優劣勢。如果圖中含有負數權重，不能使用狄克斯特拉算法：貝爾曼-福特算法可直接認定不存在的最短路徑，但在狄克斯特拉算法中，即便不存在最短路徑，也會算出一個錯誤的最短路徑。距離估算值越接近當前頂點到終點的實際值，A-Star算法的搜索效率也越高；反之，若距離估算值與實際值相差較大，該算法的效率可能會比狄克斯特拉算法還要低；如果差距再大，甚至可能無法得到正確答案。 此書中沒有介紹編程語言，更沒有一步一步的編程代碼。而《算法圖解》第1章就說明書中示例都使用Python編寫的一步一步代碼，明確了編程語言是Python，而不是C語言、Ruby或其他。而實際上，算法可以用Python，也可以用C語言、Ruby或其他編程語言編寫代碼。所以，此書名好像改成“用Python編程語言編寫算法與圖解”更貼切[微笑] （連同另一本關於算法書籍，寫了篇字數更多的讀後感，於2019年7月5日發佈在“N書齋”微信公衆號，多謝指正[抱拳]）

1. 數據結構 主要講了數組、鏈表、棧、隊列、哈希表、堆、二叉查找樹 在存儲數據的過程中，如果發生衝突，可以利用鏈表在已有數據的後面插入新數據來解決衝突。這種方法被稱爲“鏈地址法”。除了鏈地址法以外，還有幾種解決衝突的方法。其中，應用較爲廣泛的是“開放地址法”。這種方法是指當衝突發生時，立刻計算出一個候補地址（數組上的位置）並將數據存進去。如果仍然有衝突，便繼續計算下一個候補地址，直到有空地址爲止。可以通過多次使用哈希函數或“線性探測法”等方法計算候補地址。 堆是一種圖的樹形結構，被用於實現“優先隊列”（priority queues），在堆中存儲數據時必須遵守這樣一條規則：子結點必定大於父結點。因此，最小值被存儲在頂端的根結點中。往堆中添加數據時，爲了遵守這條規則，一般會把新數據放在最下面一行靠左的位置。當最下面一行裏沒有多餘空間時，就再往下另起一行，把數據加在這一行的最左端。 二叉查找樹（又叫作二叉搜索樹或二叉排序樹）是一種數據結構，採用了圖的樹形結構。 二叉查找樹有兩個性質。第一個是每個結點的值均大於其左子樹上任意一個結點的值。 第二個是每個結點的值均小於其右子樹上任意一個結點的值。 首先，二叉查找樹的最小結點要從頂端開始，往其左下的末端尋找。此處最小值爲3。 比較的次數取決於樹的高度。所以如果結點數爲n，而且樹的形狀又較爲均衡的話，比較大小和移動的次數最多就是log2n。因此，時間複雜度爲O（logn）。但是，如果樹的形狀朝單側縱向延伸，樹就會變得很高，此時時間複雜度也就變成了O（n）。 有很多以二叉查找樹爲基礎擴展的數據結構，比如“平衡二叉查找樹”。這種數據結構可以修正形狀不均衡的樹，讓其始終保持均衡形態，以提高查找效率。另外，雖然文中介紹的二叉查找樹中一個結點最多有兩個子結點，但我們可以把子結點數擴展爲m（m爲預先設定好的常數）。像這種子結點數可以自由設定，並且形狀均衡的樹便是B樹。 2. 排序 主要講了冒泡排序、選擇排序、插入排序、堆排序、歸併排序、快速排序。 在冒泡排序中，第1輪需要比較n-1次，第2輪需要比較n-2次……第n-1輪需要比較1次。因此，總的比較次數爲（n-1）+（n-2）+…+1≈n2/2。這個比較次數恆定爲該數值，和輸入數據的排列順序無關。不過，交換數字的次數和輸入數據的排列順序有關。假設出現某種極端情況，如輸入數據正好以從小到大的順序排列，那麼便不需要任何交換操作；反過來，輸入數據要是以從大到小的順序排列，那麼每次比較數字後便都要進行交換。因此，冒泡排序的時間複雜度爲O（n2）。 選擇排序使用了線性查找來尋找最小值，因此在第1輪中需要比較n-1個數字，第2輪需要比較n-2個數字……到第n-1輪的時候就只需比較1個數字了。因此，總的比較次數與冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。每輪中交換數字的次數最多爲1次。如果輸入數據就是按從小到大的順序排列的，便不需要進行任何交換。選擇排序的時間複雜度也和冒泡排序的一樣，都爲O（n2）。 插入排序是一種從序列左端開始依次對數據進行排序的算法。在排序過程中，左側的數據陸續歸位，而右側留下的就是還未被排序的數據。插入排序的思路就是從右側的未排序區域內取出一個數據，然後將它插入到已排序區域內合適的位置上。 在插入排序中，需要將取出的數據與其左邊的數字進行比較。就跟前面講的步驟一樣，如果左邊的數字更小，就不需要繼續比較，本輪操作到此結束，自然也不需要交換數字的位置。然而，如果取出的數字比左邊已歸位的數字都要小，就必須不停地比較大小，交換數字，直到它到達整個序列的最左邊爲止。具體來說，就是第k輪需要比較k-1次。因此，在最糟糕的情況下，第2輪需要操作1次，第3輪操作2次……第n輪操作n-1次，所以時間複雜度和冒泡排序的一樣，都爲O（n2）。和前面講的排序算法一樣，輸入數據按從大到小的順序排列時就是最糟糕的情況。 堆排序一開始需要將n個數據存進堆裏，所需時間爲O（nlogn）。排序過程中，堆從空堆的狀態開始，逐漸被數據填滿。由於堆的高度小於log2n，所以插入1個數據所需要的時間爲O（logn）。每輪取出最大的數據並重構堆所需要的時間爲O（logn）。由於總共有n輪，所以重構後排序的時間也是O（nlogn）。因此，整體來看堆排序的時間複雜度爲O（nlogn）。這樣來看，堆排序的運行時間比之前講到的冒泡排序、選擇排序、插入排序的時間O（n2）都要短，但由於要使用堆這個相對複雜的數據結構，所以實現起來也較爲困難。 歸併排序算法會把序列分成長度相同的兩個子序列，當無法繼續往下分時（也就是每個子序列中只有一個數據時），就對子序列進行歸併。歸併指的是把兩個排好序的子序列合併成一個有序序列。該操作會一直重複執行，直到所有子序列都歸併爲一個整體爲止。 歸併排序中，分割序列所花費的時間不算在運行時間內（可以當作序列本來就是分割好的）。在合併兩個已排好序的子序列時，只需重複比較首位數據的大小，然後移動較小的數據，因此只需花費和兩個子序列的長度相應的運行時間。也就是說，完成一行歸併所需的運行時間取決於這一行的數據量。看一下上面的圖便能得知，無論哪一行都是n個數據，所以每行的運行時間都爲O（n）。而將長度爲n的序列對半分割直到只有一個數據爲止時，可以分成log2n行，因此，總共有log2n行。也就是說，總的運行時間爲O（nlogn），這與前面講到的堆排序相同。 快速排序算法首先會在序列中隨機選擇一個基準值（pivot），然後將除了基準值以外的數分爲“比基準值小的數”和“比基準值大的數”這兩個類別，再將其排列成以下形式。[比基準值小的數] 基準值 [比基準值大的數]接着，對兩個“[ ]”中的數據進行排序之後，整體的排序便完成了。對“[ ]”裏面的數據進行排序時同樣也會使用快速排序。 分割子序列時需要選擇基準值，如果每次選擇的基準值都能使得兩個子序列的長度爲原本的一半，那麼快速排序的運行時間和歸併排序的一樣，都爲O（nlogn）。和歸併排序類似，將序列對半分割log2n次之後，子序列裏便只剩下一個數據，這時子序列的排序也就完成了。 3. 圖的搜索 主要講了廣度優先搜索、深度優先搜索、貝爾曼-福特算法、狄克斯特拉算法、A*算法。 圖的搜索指的就是從圖的某一頂點開始，通過邊到達不同的頂點，最終找到目標頂點的過程。根據搜索的順序不同，圖的搜索算法可分爲“廣度優先搜索”和“深度優先搜索”這兩種。 深度優先搜索會沿着一條路徑不斷往下搜索直到不能再繼續爲止，然後再折返，開始搜索下一條候補路徑。 深度優先搜索的特徵爲沿着一條路徑不斷往下，進行深度搜索。雖然廣度優先搜索和深度優先搜索在搜索順序上有很大的差異，但是在操作步驟上卻只有一點不同，那就是選擇哪一個候補頂點作爲下一個頂點的基準不同。廣度優先搜索選擇的是最早成爲候補的頂點，因爲頂點離起點越近就越早成爲候補，所以會從離起點近的地方開始按順序搜索；而深度優先搜索選擇的則是最新成爲候補的頂點，所以會一路往下，沿着新發現的路徑不斷深入搜索。 將圖的頂點數設爲n、邊數設爲m，我們來思考一下貝爾曼-福特算法的時間複雜度是多少。該算法經過n輪更新操作後就會停止，而在每輪更新操作中都需要對各個邊進行1次確認，因此1輪更新所花費的時間就是O（m），整體的時間複雜度就是O（nm）。 與前面提到的貝爾曼-福特算法類似，狄克斯特拉（Dijkstra）算法也是求解最短路徑問題的算法，使用它可以求得從起點到終點的路徑中權重總和最小的那條路徑路徑。 比起需要對所有的邊都重複計算權重和更新權重的貝爾曼-福特算法，狄克斯特拉算法多了一步選擇頂點的操作，這使得它在求最短路徑上更爲高效。將圖的頂點數設爲n、邊數設爲m，那麼如果事先不進行任何處理，該算法的時間複雜度就是O（n2）。不過，如果對數據結構進行優化，那麼時間複雜度就會變爲O（m+nlogn）。 A*（A-Star）算法也是一種在圖中求解最短路徑問題的算法，由狄克斯特拉算法發展而來。狄克斯特拉算法會從離起點近的頂點開始，按順序求出起點到各個頂點的最短路徑。也就是說，一些離終點較遠的頂點的最短路徑也會被計算出來，但這部分其實是無用的。與之不同，A*就會預先估算一個值，並利用這個值來省去一些無用的計算。 4. 安全算法 哈希函數的算法中具有代表性的是MD5[插圖]、SHA-1[插圖]和SHA-2等。其中SHA-2是現在應用較爲廣泛的一個，而MD5和SHA-1存在安全隱患，不推薦使用。 加密數據的方法可以分爲兩種：加密和解密都使用相同密鑰的“共享密鑰加密”和分別使用不同密鑰的“公開密鑰加密”。 實現共享密鑰加密的算法有凱撒密碼、AES[插圖]、DES[插圖]、動態口令等，其中AES的應用最爲廣泛。 公開密鑰加密是加密和解密使用不同密鑰的一種加密方法。由於使用的密鑰不同，所以這種算法也被稱爲“非對稱加密”。加密用的密鑰叫作“公開密鑰”，解密用的叫作“私有密鑰”。 X把密文發送給B，這個密文由B發出的公開密鑰PB加密而成，所以B可以用自己的私有密鑰SB來解密。從收到密文到解密密文都沒發生任何問題，因此B也意識不到數據已經被竊聽。這種通過中途替換公開密鑰來竊聽數據的攻擊方法叫作“中間人攻擊”（man-in-the-middle attack）。 公開密鑰的可靠性會出現問題，就是因爲A無法判斷收到的公開密鑰是否來自B。要想解決這個問題，就要用到之後會講到的“數字證書”。公開密鑰加密還有一個問題，那就是加密和解密都比較耗時，所以這種方法不適用於持續發送零碎數據的情況。要想解決這個問題，就要用到“混合加密”。 共享密鑰加密存在無法安全傳輸密鑰的密鑰分配問題，公開密鑰加密又存在加密解密速度較慢的問題。結合這兩種方法以實現互補的一種加密方法就是混合加密。共享密鑰加密存在無法安全傳輸密鑰的密鑰分配問題，公開密鑰加密又存在加密解密速度較慢的問題。結合這兩種方法以實現互補的一種加密方法就是混合加密。 消息認證碼可以實現“認證”和“檢測篡改”這兩個功能。 數字簽名不僅可以實現消息認證碼的認證和檢測篡改功能，還可以預防事後否認問題的發生。 通過數字證書，信息的接收者可以確認公開密鑰的製作者。數字證書就是像這樣通過認證中心來擔保公開密鑰的製作者。這一系列技術規範被統稱爲“公鑰基礎設施”（Public Key Infrastructure, PKI）。 5. 小結 第5章的安全算法很精彩！把各個算法用圖描述的這麼清楚還是比較難得的，我之前寫了一篇相關算法的文章，畫了幾十張圖前後花了一週的時間，費時費力，我是能體會出作者的用心的。

＃我的第一本算法書＃讀後分享 首先這是一本深入淺出的書籍，相信即使不是軟件出身的夥伴都能看的津津有味，這本書讀它有什麼作用呢？ 第一，你如果對了解如今各個app和網站都在做各類的推薦算法有興趣，那麼去了解算法背後的推薦機制根源，便是不錯的入門方法，因爲它可能來源於一些基礎查詢和排序算法，而這裏面就涉及到從最基本的數據存儲結構，也就是不同的數據結構，如鏈表、數組、堆棧、圖、哈希表、隊列、樹，他們其實會根據不同場景得到不同應用，效率也不同。其中哈希表讓我印象深刻。 哈希表存儲的是鍵值對，大家可以理解爲， 如果我們要存儲多個類似於“小步-男”，這樣的數據，在表中的順序如果用1-n的方式去存儲，那麼數據越多，我們查找的時間越長，而這裏哈希表的方式，就是把，“小步”進行哈希計算並按要存儲數據的長度，取餘數，將得到的值作爲數組編號，這樣後續做查找的時候，其實我們只需要查找“小步”的哈希值，便可快速得到數據，而不用線性查找 第二，網絡世界由於開始蓬勃發展，網絡安全已經是作爲一個安全上網的支撐，因此，你可曾想過，如果你的所有通訊內容，可能被監聽，或者你接收的內容被篡改，那麼網絡對於我們來說是怎樣的存在？那這背後是有哪些加密方式在支撐呢，那麼這本書會通過比較容易理解的圖文告訴你關於對稱加密，不對稱加密，數字證書這些我們陌生的內容如果幫我們做好加密這一關。(以前學CCNA的時候咋沒有發現這麼通俗易懂的講解) 第三，當你慢慢了解了算法在排序和查詢方面那巧妙的計算原理，特別是圖的概念後，你可能會將它的某些機理聯想到生活中的方方面面，比如它採用的計算某個頂點到另一個頂點的最短路徑權重方式，解決了複雜圖節點的最小路徑的計算。 最後，這本書某種意義上，就是完成對一些算法背景的瞭解，沒有方法論可以獲得，不過你閱讀後，如果你是非開發人員，至少你會慢慢理解爲啥有時候，我們在app中查詢東西的時候，有些網站很快，有些很慢。很大可能就是，數據結構使用的差異和查詢sql可能需要優化。

其實用配套的軟件演示，比看這本書好，因爲從動畫演示中抽取部分圖片有時候和文字匹配的不好，存在略微錯位。 本書的排序，圖搜索和安全三章可以看看，有個直觀印象即可。因爲沒有涉及具體實現，一些描述可能存在困惑，例如那幾種圖搜索算法，其實需要隊列，棧或者堆來存儲候選節點，本書不會涉及這些，所以再走完一路選另一路時，新人可能會困惑。 還有一些描述不到位，有誤的，看到的就在文中說了，這裏不重複了。