AI及機器學習的經脈: 演算法新解 | 誠品線上

AI及機器學習的經脈: 演算法新解

內容簡介

內容簡介 《AI及機器學習的經脈：演算法新解》同時用函數式方法和傳統方法介紹主要的基本演算法和資料結構，資料結構部分包括二叉樹、紅黑樹、AVL樹、Trie、Patricia、尾碼樹、B樹、二叉堆、二項式堆、斐波那契堆、Pairing堆、佇列、序列等；基本演算法部分包括各種排序演算法、序列搜索演算法，字串匹配演算法（KMP等），深度優先、廣度有限搜索演算法、貪心演算法以及動態規劃。

作者介紹

作者介紹 ■作者簡介劉新宇1999年和2001年分別獲得清華大學自動化系學士和碩士學位，之後長期從事軟體研發工作。關注基本演算法和資料結構，尤其是函數式演算法，目前任職於亞馬遜中國倉儲和物流技術團隊。

產品目錄

產品目錄 前言第一部分 樹 第1章 二叉搜尋樹：資料結構中的“hello world”1.1 定義. 1.2 資料組織1.3 插入1.4 檢查.1.5 搜索1.6 刪除.1.7 隨機建置二叉搜尋樹第2章 插入排序的進化2.1 簡介2.2 插入2.3 改進一：二分尋找2.4 改進二：使用鏈結串列2.5 使用二叉搜尋樹的最後改進2.6 小結第3章 並不複雜的紅黑樹3.1 紅黑樹的定義3.2 插入3.3 刪除3.4 指令式的紅黑樹演算法3.5 小結第4章 AVL 樹4.1 AVL 樹的定義4.2 插入4.3 刪除4.4 AVL 樹的指令式演算法4.5 小結.第5章 基數樹：Trie 和Patricia5.1 整數Trie5.2 整數Patricia5.3 字元Trie5.4 字元Patricia 5.5 Trie 和Patricia 的應用5.6 小結第6章 副檔名樹6.1 副檔名Trie6.2 副檔名樹6.3 副檔名樹的應用6.4 小結第7章 B樹7.1 插入7.2 刪除7.3 搜索7.4 小結第二部分 堆第8章 二叉堆積8.1 用陣列實現隱式二叉堆積8.2 左偏堆積和skew 堆積：顯性的二叉堆積8.3 延伸堆積8.4 小結第9章 從吃葡萄到世界盃：選擇排序的進化9.1 尋找最小元素9.2 細微改進.9.3 本質改進9.4 小結第10章 二項式堆積、費氏堆積和配對堆積10.1 二項式堆積10.2 費氏堆積10.3 配對堆積10.4 小結第三部分 佇列和序列第11章 並不簡單的佇列11.1 單向鏈結串列和循環緩衝區實現的佇列11.2 純函數式實現.11.3 小改進：平衡佇列.11.4 進一步改進：即時佇列11.5 惰性即時佇列11.6 小結第12章 序列：最後一塊磚12.1 二叉隨機存取列表12.2 二叉隨機存取列表的數值表示12.3 指令式雙陣列清單12.4 可連接列表12.5 手指樹12.6 小結第四部分 排序和搜索13.1 快速排序13.2 快速排序的效能分析13.3 工程實作中的改進13.4 針對最差情況的工程實作13.5 其他工程實作13.6 其他13.7 歸併排序13.8 原地歸併排序13.9 自然歸併排序13.10 自底向上歸併排序.13.11 平行處理13.12 小結第14章 搜索14.1 序列搜索14.2 解的搜索14.3 小結8附錄列表參考文獻索引

商品規格

試閱文字

內文 : ✤ 演算法有用嗎
「演算法有用嗎？」經常有人問我這個問題。很多人在工作中根本不用演算法。偶爾碰到的時候，也不過是使用一些實現好的函數庫。舉例來說，C++

標準範本函數庫（STL）中有現成的排序、尋找函數；常用的資料結構，如向量（vector）、佇列（queue）、集合（set）也都實現好了。日常工作中了解如何使用這些函數庫似乎就足夠了。
但是，演算法在解決一些「有趣」的問題時會造成關鍵作用。不過，這些問題本身的價值卻是見仁見智。
讓我們用實例來說話吧。接下來的兩道題目，即使是初學程式設計的人，應該也很容易解決。

✤ 最小可用ID，演算法的威力
這道題目來自Richard
Bird
所著書中的第1章[1]。現代社會中，有很多服務依賴一種稱為ID的概念。例如身份證就是一種ID，銀行帳戶也是一種ID，電話號碼本質上也是一種ID。假設我們使用非負整數作為某個系統的ID，所有使用者都由一個ID唯一確定。任何時間，這個系統中的有些ID處於使用中的狀態，有些ID則可以分配給新使用者。現在的問題是，怎樣才能找到最小的可分配ID呢？例如下面是目前正在使用的ID：
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
最小的可分配ID，也就是不在這個清單中的最小非負整數，即10。
有些程式語言內建了這一線性尋找的實現，例如Python。我們可以直接將這一解法翻譯成下面的程式：
def brute_force(lst):
i = 0
while True:
if i not in lst:
return i
i = i + 1
但是這道題目僅是看上去簡單。在儲存了幾百萬個ID的大型系統中，這個方法的效能很差。對於一個長度為n的ID清單，它需要O(n2
)的時間才能找到最小的可分配ID。在我的電腦上（雙核心2.10 GHz處理器，2 GB憶體），使用這一方法的C語言程式平均要5.4
s才能在10萬個ID 找到答案。當ID的數量上升到100萬時，平均用時則長達8min。
改進一
改進這一解法的關鍵基於這一事實：對於任何n個非負整數x1
, x2 , ···, xn，如果存在小於n的可用整數，必然存在某個xi不在[0, n) 範圍內。否則這些整數一定是0, 1, ···, n
−1 的某個排列，這種情況下，最小的可用整數是n。於是我們有以下結論：
minf ree(x1 , x2 , ···, xn) 至n (1)
根據這一結論，我們可以用一個長度為n + 1 的陣列，來標記區間[0, n]內的某個整數是否可用：

其中第2
行將標示陣列中的所有值初始化為False，這一步驟需要O(n)
的時間。接著我們檢查A中的所有元素，只要小於n，就將對應的標記置為True，這一過程也需要O(n)的時間。最後我們線性尋找標示陣列中第一個值為False的位置。整個演算法的效能是線性時間O(n)。

活動

• 6/18前 圖書滿$1,000折$100
• 6/18前 全站滿$1,688享92折
• 6/18前 全站滿$3,688享9折