演算法洞見:遞推與遞迴

劉鐵猛(Timothy) 著 廖信彥 審校

  • 演算法洞見:遞推與遞迴-preview-1
  • 演算法洞見:遞推與遞迴-preview-2
  • 演算法洞見:遞推與遞迴-preview-3
  • 演算法洞見:遞推與遞迴-preview-4
  • 演算法洞見:遞推與遞迴-preview-5
  • 演算法洞見:遞推與遞迴-preview-6
  • 演算法洞見:遞推與遞迴-preview-7
  • 演算法洞見:遞推與遞迴-preview-8
  • 演算法洞見:遞推與遞迴-preview-9
  • 演算法洞見:遞推與遞迴-preview-10
  • 演算法洞見:遞推與遞迴-preview-11
  • 演算法洞見:遞推與遞迴-preview-12
  • 演算法洞見:遞推與遞迴-preview-13
  • 演算法洞見:遞推與遞迴-preview-14
演算法洞見:遞推與遞迴-preview-1

買這商品的人也買了...

商品描述

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



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

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

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

作者簡介

劉鐵猛(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 後記