讀書筆記：圖解算法
算法簡介
二分查找 O(log n)
大O表示法
大O表示法 讓你能夠比較操作數，它指出了算法運作時間的增速
大O表示法 指出了最糟糕情況下的運作時間
下面按從快到慢的順序列出了你經常會遇到的5種大O運作時間。
O(log n)，也叫對數時間，這樣的算法包括二分查找。
O(n)，也叫線性時間，這樣的算法包括簡單查找。
O(n * log n)，這樣的算法包括第4章将介紹的快速排序——一種速度較>快的排序算法。
O(n 2 )，這樣的算法包括第2章将介紹的選擇排序——一種速度較慢的排序算法。
O(n!)，這樣的算法包括接下來将介紹的旅行商問題的解決方案——一種非常慢的算法
算法的速度指的并非時間，而是操作數的增速。
選擇排序 O( n^2 )
先找最大，再找第二大…
數組和連結清單
數組： 記憶體中連續
連結清單： 随機
快速排序
O(n log n)
遞歸
兩部分：基線條件（不在調用自己）、遞歸條件（調用自己）
棧
快速排序
分而治之（divide and conquer，D&C）
這裡重申一下D&C的工作原理：
(1) 找出簡單的基線條件；
(2) 确定如何縮小問題的規模，使其符合基線條件。
散清單
散列函數
沖突
較低的填裝因子；散列包含的元素數/位置總數
良好的散列函數。
廣度優先搜尋
breadth-first search，BFS 廣度優先搜尋：一種圖算法
圖由節點（node）和邊（edge）組成。
第一類問題：從節點A出發，有前往節點B的路徑嗎？
第二類問題：從節點A出發，前往節點B的哪條路徑最短？
隊列
隊列是一種先進先出（First In First Out，FIFO）的資料結構，而棧是一種後進先出（Last In
First Out，LIFO）的資料結構。
有向圖（directed graph），其中的關系是單向的。
無向圖（undirected graph）沒有箭頭，直接相連的節點互為鄰居
如果任務A依賴于任務B，在清單中任務A就必須在任務B後面。這被稱為拓撲排序，使用它可根據圖建立一個有序清單。
樹是一種特殊的圖，其中沒有往後指的邊。
狄克斯特拉算法
狄克斯特拉算法包含4個步驟。
(1) 找出“最便宜”的節點，即可在最短時間内到達的節點。
(2) 更新該節點的鄰居的開銷，其含義将稍後介紹。
(3) 重複這個過程，直到對圖中的每個節點都這樣做了。
(4) 計算最終路徑。
邊 有權
帶權重的圖稱為權重圖（weighted graph），不帶權重的圖稱為非權重圖（unweighted graph）
狄克斯特拉算法隻适用于有向無環圖（directed acyclic graph，DAG）。
不能将狄克斯特拉算法用于包含負權邊的圖
在包含負權邊的圖中，要找出最短路徑，可使用另一種算法——貝爾曼福德算法（Bellman-Ford algorithm）
貪婪算法
旅行商問題和集合覆寫問題有一些共同之處：你需要計算所有的解，并從中選出最小/最短
的那個。這兩個問題都屬于NP完全問題。
NP完全問題特點
元素較少時算法的運作速度非常快，但随着元素數量的增加，速度會變得非常慢。
涉及“所有組合”的問題通常是NP完全問題。
不能将問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。
如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。
如果問題涉及集合（如廣播台集合）且難以解決，它可能就是NP完全問題。
如果問題可轉換為集合覆寫問題或旅行商問題，那它肯定是NP完全問題。
動态規劃
但僅當每個子問題都是離散的，即不依賴于其他子問題時，動态規劃才管用
最長公共子序列：兩個單詞中都有的序列包含的字母數
K最近鄰算法
使用KNN來做兩項基本工作——分類和回歸：
分類就是編組；
回歸就是預測結果（如一個數字）
總結
KNN用于分類和回歸，需要考慮最近的鄰居。
分類就是編組。
回歸就是預測結果（如數字）。
特征抽取意味着将物品（如水果或使用者）轉換為一系列可比較的數字。
能否挑選合适的特征事關KNN算法的成敗
MapReduce
映射（ map ）函數和歸并（ reduce ）函數
布隆過濾器：
可能出現錯報的情況，即Google可能指出“這個網站已搜集”，但實際上并沒有搜集。
不可能出現漏報的情況，即如果布隆過濾器說“這個網站未搜集”，就肯定未搜集。
局部不敏感 SHA 局部改變整體改變（不會區分是否是局部的變化）
局部敏感 Simhash 局部改變整體細微變化（會區分是否是局部的變化）
Diffie-Hellman算法及其替代者RSA
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)