演算法洞見：遞推與遞迴

本書利用遞推與遞迴演算法
來處理各式各樣的資料結構
遞推與遞迴是演算法的根基


演算法是個有趣的東西，針對某個問題設計演算法的時候，不會的人感覺像「大海撈針」，而會的人則感覺像「一葦渡江」。高手的頭腦裡都有一張「演算法地圖」，演算法之間不是孤立的，而是彼此連通的。演算法之間的內在聯繫有很多，但挖掘到根源上，就是遞推與遞迴兩種思想。

本書從深度解析遞推和遞迴這兩種基本演算法思想開始，用它們貫穿起了《演算法導論》中的幾十種經典演算法，包括排序、搜尋、回溯、貪心、分治、動態規劃、圖演算法等。
本書秉持了作者一貫的風趣幽默又不失嚴謹的寫作風格，同時融入了學習心理學和認知科學的實踐原理。

本書適合於所有想通過學習演算法來精進自己程式設計能力的讀者。為了傾聽讀者們的心聲、不斷完善這本書，作者熱切地期待大家與他在領英上建立聯繫。在那裡，作者還將源源不斷地與讀者們分享種類教學資源和工作機會。

劉鐵猛(Timothy)

資深軟體工程師，技術作者、譯者、教育者，現在就職於亞馬遜(美國)。曾就職於微軟(美國)，著有《深入淺出WPF》一書，銷量數萬冊。

精心製作的《C#語言入門詳解》線上課程點擊量超過500萬次。他的多套教學影片已被微軟收錄為官方認證課程。他的所有作品風格一致：內容詳實準確，語言風趣幽默，說理深入淺出，被學習者們奉為佳作。

第一章 觀念與實作
1.1 觀念
1.2 實作
準備一棵樹
以遞推程式碼實作遞推觀念
以遞迴程式碼實作遞推觀念
以遞迴程式碼實作遞迴觀念
「好」的遞迴與「壞」的遞迴
以遞推程式碼實作遞迴觀念
思考題

第二章 實作回溯：上古神話中的演算法
2.1 回溯式遞迴的基本原理
範例1
範例2
2.2 神話故事中的演算法
迷宮設計入門
探尋迷宮中的路徑
用遞推（迴圈）程式碼實作回溯
思考題

第三章 動態規劃：動機決定性質
3.1 什麼是動態規劃
3.2 透徹理解動態規劃
遞推版動態規劃
遞迴版動態規劃
陷阱：這不是動態規劃！
貪心也要動腦子
3.3 更上層樓：讓規劃「動態」起來
切年糕
接訂單
聽講座
思考題
3.4 動態規劃哲思

第四章 演算法皇冠上的明珠
4.1 遊樂園：O(n^2) 的簡單排序
選擇排序
泡沫排序
插入排序
4.2 以空間換取時間：合併排序
4.3 看運氣的快速排序
4.4 兩全其美：堆積排序
什麼是「堆積」
建構最大/ 最小堆積
利用「最大堆積」進行原地排序
利用「最小堆積」產生升冪陣列
思考題

第五章 搜尋：來而不往非禮也
5.1 二分搜尋
在已排序的陣列上
在平衡二元搜尋樹上
5.2 線段樹：化繁為簡
建構線段樹
查詢子段和
5.3 字典樹：字母大接龍
遞推版實作
遞迴版實作
5.4 併查集：朋友的朋友是朋友

第六章 圖：包羅萬象
6.1 圖的表達
鄰接表
鄰接矩陣
應對向、權、環的變化
思考題
6.2 圖的巡訪
廣度優先巡訪
深度優先巡訪
遞推版深度優先巡訪
向、權、環對巡訪的影響
6.3 頂點的連通性
有無權重對連通性的影響
有無向對連通性的影響
環對連通性的影響
6.4 強連通性元件
Kosaraju-Sharir 演算法
6.5 圖上的路徑
BFS 式路徑搜尋
DFS 式路徑搜尋
自下而上式路徑搜尋
回溯式路徑搜尋
取得環路
思考題
6.6 最短路徑
Dijkstra 最短路徑演算法
Bellman-Ford 最短路徑演算法
Floyd-Warshall 最短路徑演算法
6.7 最小生成樹
建構有權無向圖
Prim 演算法
Kruskal 演算法
6.8 最大流：超時空移花接木
殘差邊、反向邊、殘差網路、增廣路徑
容量返還
Ford-Fulkerson 演算法實作
6.9 最小割：流量的瓶頸
6.10 拓撲排序
入度圖與出度圖
理解頂點的入度
遞推實作
遞迴實作
思考題

A 後記