Ai-Reads: Grokking Algorithms.png

簡短點評：愛因斯坦說，“如果你不能把它解釋給你外婆聽，那么你就沒有弄明白?！保╕ou do not really understand something unless you can explain it to your grandmother.）用來解釋這本用心的書再合適不過。真的弄明白了才能把文縐縐的理論說成大白話。這是一本鼓勵人學習計算機算法的好書。

前言：這篇是「威玲旺卡Aileen」在讀過中譯版的《Grokking Algorithms》后的筆記。轉(zhuǎn)載筆記不用注明我，但請注明原書作者和譯者，及標注鏈接到購買鏈接，謝謝。

第1章：二分查找（Binary Search）+ 時間復雜度O

• 二分查找：對數(shù)時間 O(log n) ，前提：有序
• 簡單查找 （Simple Search）：線性時間O(n)

第2章：選擇排序（Selection Search）+ 數(shù)組（Array）+ 鏈表（List）

• 數(shù)組：讀取 O(1) 插入 O(n) 刪除 O(n)
• 鏈表：讀取 O(n) 插入 O(1) 刪除 O(1)
• 混合數(shù)據(jù)：鏈表數(shù)組
• 選擇排序：O(n^2)

第3章：遞歸（Recursion）+棧（Stack）

• 循環(huán)都可以用遞歸取代
• 基線條件（Base Case）+ 遞歸條件（Recursive Case）
• 調(diào)用棧（Call Stack） FILO

第4章：快速排序（Quick Sort）+分而治之（Divide & Conquer）

• D&C：關鍵1. 找出基準條件 2. 每次遞歸縮小問題規(guī)模
• D&C：不是一種解決算法，而是一種解決思路
• 拓展：歐幾里德算法
• 快速排序：選擇一個基準值（Pivot），分成兩個分區(qū)（Partition），對分區(qū)進行快速排序
• 拓展：歸納證明。需要基線條件，歸納條件，就如同遞歸
• 運行時間：快速排序的平均情況是O(n log n)，最糟糕是O(n^2)
• 拓展：合并排序（Merge Sort）的運行時間是O(n log n)
• O的常量影響：合并排序的常量比快速排序大。所以在平均情況下，快速排序更快。

第5章：散列表，a.k.a. 哈希表（Hash Table）

• 散列表所有操作時間都是常量時間O(1)
• Python dict() 或 {}
• 應用場合：仿真映射，防止重復給flag，緩存/記住數(shù)據(jù)
• 沖突（Collision）：指產(chǎn)生的相同散列函數(shù)地址，解決方法是加鏈表（鏈地址法），拖慢散列表速度是缺點
• 防止沖突：1. 及時調(diào)整長度（Resizing），保持較低的填充因子（<0.7）2. 用好的散列函數(shù)（SHA）

第6章：廣度優(yōu)先搜索（Breadth-First-Search，BFS）+ 圖（有向/無向）+ 隊列（Queue）

• 例子：在FB找芒果銷售商，從一度關系到二度關系類推
• Python deque()
• 復雜度：O(V+E)V指頂點（vertices），E指邊（edges），O(V+E)是因為隊列需要檢查每個頂點，而搜索需要過每條邊。
• 因為檢查順序很關鍵，所以需要先進先出的隊列，最終才能得到最短距離。
• 最短序列問題 -> 圖建模 -> 用廣度優(yōu)先搜索解決

第7章：狄克斯特拉算法（Dijkstra's Algorithm）+ 加權圖（Weighted Graph）

• 算法過程：1. 找出最便宜的節(jié)點； 2. 遍歷鄰居，如果有前往它們的更短路徑，就更新開銷； 3. 重復，直到找過每個節(jié)點 ；4. 計算最終路徑。
• 只用于有向無環(huán)圖（Directed Acyclic Graph, DAG）
• 負權邊用貝爾曼-福德算法（Bellman-Ford Algthorithm）
• 3個散列表實現(xiàn)Dijkstra：1. Graph 2. Costs 3. Parents

第8章：貪婪算法 （Greedy Algorithm）+ NP完全問題（NP-completeness）+ 集合 （Set）

• 貪婪算法：一直取最優(yōu)解
• Python set()
• 集合覆蓋問題：廣播電臺企圖覆蓋所有州，復雜度O(2^n)，可以用近似算法求近似最優(yōu)解
• 旅行商問題（Travelling Salesman Problem）：復雜度O(n!)
• NP完全：求近似解更可行
• 如何識別可能的NP完全：1. 元素少時很快，速度隨著元素變多而速度迅猛下跌 2. 所有組合問題 3. 不能用D&C降解 4. 設計序列，如旅行商問題（Travelling salesman problem），設計集合，如廣播臺集合問題 5. 可以轉(zhuǎn)換為集合覆蓋問題或者旅行商問題的都是NP完全問題。

第9章：動態(tài)規(guī)劃 （Dynamic Programming, DP）

• 動態(tài)規(guī)劃用于求在約束條件下的最優(yōu)解，在問題可分解為彼此獨立且離散的子問題時。
• 背包問題
• 動態(tài)規(guī)劃的解決一定涉及網(wǎng)格，單元格的值就是要優(yōu)化的值，每個單元格都是一個自問題，所以應該考慮如何將問題分成子問題。這有助于找到網(wǎng)格的坐標軸。
• 例：找最大公共字串和最大公共序列
• 應用：git diff，levenshtein距離，Microsoft Word行斷
• 計算動態(tài)規(guī)劃方案的公式按情況不同而變化

第10章：K最近鄰（K Nearest Neighbor, KNN）

• 分類就是編組，回歸就是預測
• 除了用歐幾里得距離作為距離公式，還有余弦相似度（Cosine Similarity）
• 應用：OCR，郵件分類用到了樸素貝葉斯分類（Naive Bayes Classifier），預測股票
• 選取的特征關系KNN的成敗

第11章：展望

• 二叉查找樹（Binary Tree）：操作平均情況復雜度O(log n)。相關：B樹，紅黑樹，堆，伸展樹。
• 反向索引（Inverted Indexes），創(chuàng)建搜索引擎
• 傅里葉變換（The Fourier Transform），時域->頻域
• 并行算法（Parallel Algorithms）。MapReduce，工具Apache Hadoop，映射函數(shù)Map，歸并函數(shù)Reduce
• 布隆過濾器（Bloom Filter），一種概率型數(shù)據(jù)結(jié)構(gòu)，可能錯報，但不可能漏報
• Hyperloglog，類似布隆過濾器
• SHA算法，應用相同文件/檢查密碼
• 局部敏感的哈希算法Simhash，SHA局部不敏感
• Diffie-Hellman，RSA密鑰，公鑰+私鑰
• 線性規(guī)劃（Epilogue），圖是線性規(guī)劃的一個子集

復雜度集合：

• 二分查找：O(log n)
• 簡單查找：O(n)
• 選擇排序：O(n^2)
• 合并排序：O(n log n)
• 快速排序：O(n log n)
• 旅行商問題：O(n!)
• 二叉查找樹：O(log n)
• 散列表一項操作：O(1)
• 集合覆蓋問題：O(2^n)
• 廣度優(yōu)先搜索：O(V+E)

最后更新時間：2017年8月