《算法之道》精華 經典算法部分
- 本書作者鄒恒明，作者另有一本書《數據結構之弦》，以及《操作系統之哲學原理》都是非常好的書
- 這本書能夠算得上是深入淺出，文筆非常好。作者加入了非常多自己的思考
- 本文包含經典算法部分
第十章 排序與次序
- 插入排序
- 從無序部分抽取一張插入有序部分
- 為原地排序。無需占用暫時存儲空間
- 最優情況下為O(n)。平均O(n^2)
- 折半插入排序
- 插入時使用二分查找
- 歸并排序
- 分治，從中間分解，分別排序后進行細致的合并
- 異地排序，須要占用額外空間
- n>=30時性能比插入排序更好。
復雜度固定為O(nlog(n))
- 快排
- 分治，復雜的部分在于分解。而歸并復雜在于合并
- 原地排序
- 最壞情況為O(n^2)，但僅僅要不是每次都是最壞，復雜度就不是n^2，具有韌性
- 不論什么基于比較的排序，決策樹高度至少為nlog(n)
- 計數排序
- 元素值范圍必須有限
- 空間復雜度高
- O(n)
- 基數排序
- 從最低位到最高位排序，每一位排序都採用穩定排序，如計數排序
- 一位排序應該選擇log(n)個比特。使總體成本最低
- 桶排序
- 把n元素按值分到n個桶里，每一個桶內部進行插入排序。將各桶首位相連
- 元素應該是均勻分布
- 高速次序選擇：求第K大的數
- 使用快排的partition
- 最差O(n^2)。平均O(n)
- 線性最差高速次序選擇
- 將元素每5個一組。分別取中值。在n/5個中值里面找到中值，作為partition的pivot
- 為什么*不每3個一組？
- 保證pivot左邊右邊至少3n/10個元素
- 最差O(n)
第十一章 搜索與散列
- 順序搜索
- 在序列里面假設搜索頻率從頭到尾指數遞減。則為O(1)
- 折半搜索
- 對于有序序列，為O(logn)
- 常數搜索：散列搜索
- 直接散列：很easy，不會發生碰撞，空間浪費大
- 除法（模除法）散列
- 元素對散列表大小m取模得到
- m必須為素數，否則造成不均勻散射。比方m包括因子d，而大部分元素對d余數相等
- m不能靠近2的冪。如m為2的冪，散列結果將不依賴元素的全部位。靠近也不行，為什么？
- 乘法散列
- h(k) = (A * k ) % 2^r >> (w - r)。w為計算機字寬，A為2^(w-1)與2^w之間的一個奇數
- 乘方取中法：乘方n次（常取n=2），取中間r位
- 開放尋址散列：散列碰撞時縱深擴展，加入一個鏈表
- 平均搜索時間為O(1+a)，a為載入因子
- 封閉尋址散列：散列碰撞時為元素找到還有一個位置
- 找還有一個位置的操作稱為探尋
- 線性探尋
h(k,i) = (h'(k) + i) % m，h'(k)為家位- 向單方向尋找未被占用的位置
- 易出現頂級聚集
- 非線性探尋
- 平方探尋?
h(k,i) = (h'(k) + c1 * i + c2 * i^2) % m?易出現次級聚集
- 平方探尋?
- 雙重散列探尋
- 使用兩個散列函數h1、h2來構造新散列函數
h(k,i) = (h1(k) + i * h2(k) ) mod m
- 偽隨機探尋
- 使用偽隨機序列
- 存在次級聚集
- 不成功搜索的探尋次數期望為
1/(1-a) - 成功搜索探尋次數最多為
1 / a * ln( 1/(1-a)) - 封閉散列不能刪除元素。能夠放標記解決。假設插入相比搜索很稀疏，則能夠通過又一次散列解決空位問題
- 隨機化散列
- 找到一組散列函數。每次隨機選擇一個不同的散列函數
- 用于避免單個散列函數極端情況下聚集效應嚴重
- 全域散列
- 一組H個散列函數，將隨意兩個不同的元素映射到同一位置的函數個數為H/m
- 完美散列
- n個元素。構造m=O(n)大小的散列表，使搜索最壞達到O(1)
- 採用雙層散列，第一層大小n，第二層每一個表的大小為落到第一層位置i上的元素個數的平方
- 空間消耗為O(n)
第十二章 最短路徑
- 假設圖中有負環，則不存在最短路徑
- 單源多點最短路徑
- Dijkstra算法
- 貪婪算法。要求不存在負路徑
- 最優子結構：最短路徑里的每一段都是兩點之間的最短路徑
- 貪婪選擇屬性：路徑向外延伸的下一個節點就是離源點近期的節點
- 每次選取離源點近期的節點，更新全部與此節點相鄰節點的距離
- 時間復雜度為O(V^2)。採用堆實現。能夠達到O(E log(V))。
與Prim算法同樣
- Bellman-Ford算法
- 能夠應對負權重
- 進行V-1輪降距，每次更新圖中全部邊
- 復雜度為O(VE)
- BFS
- 各邊權重相等的情況
- O(V+E)
- Dijkstra算法
- 多源多點最短路徑
- Floyd-Warshall算法
- 動態規劃算法
- 子問題為從i到j，中間結點僅僅屬于集合1...k的最短路徑長度
- c_ijk = min{c_ij(k-1), c_ik(k-1) + ckj(k-1)}|k
- 復雜度O(n^3)
- Jonhson算法
- 等效變換為無負權重的圖，使用Dijkstra算法
- 加入一個節點s，到全部點路徑長度為0，執行Bellman-Ford算法，對節點賦值
- 對每一個節點執行Dijkstra算法
- 復雜度主要是Dijkstra算法運算，為O(VE + V^2 log(V))
- 若Bellman-Ford算法報告有負環存在，不能使用此方法
- Floyd-Warshall算法
 B. The Bakery)
