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

前言

第一部分  樹
01 二元搜尋樹：資料結構中的「hello world」
1.1 定義.
1.2 資料組織
1.3 插入
1.4 檢查.
1.5 搜索
1.6 刪除.
1.7 隨機建置二元搜尋樹
02 插入排序的進化.
2.1 簡介
2.2 插入
2.3 改進一：二分尋找
2.4 改進二：使用鏈結串列
2.5 使用二元搜尋樹的最後改進
2.6 小結
03 並不複雜的紅黑樹
3.1 紅黑樹的定義
3.2 插入
3.3 刪除
3.4 指令式的紅黑樹演算法
3.5 小結
04 AVL 樹
4.1 AVL樹的定義
4.2 插入
4.3 刪除
4.4 AVL樹的指令式演算法
4.5 小結.
05 基數樹： Trie 和Patricia
5.1 整數Trie
5.2 整數Patricia
5.3 字元Trie
5.4 字元Patricia
5.5 Trie 和Patricia 的應用
5.6 小結
06 後綴樹
6.1 後綴Trie
6.2 後綴樹
6.3 後綴樹的應用
6.4 小結
07 B樹.
7.1 插入
7.2 刪除
7.3 搜索
7.4 小結

第二部分 堆積
08 二元堆積
8.1 用陣列實現隱式二元堆積
8.2 左偏堆積和skew 堆積：顯性的二元堆積
8.3 延伸堆積
8.4 小結
09 從吃葡萄到世界盃：選擇排序的進化
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 分而治之：快速排序和歸併排序
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 小結

A 列表
B 參考文獻
 

前言

　　✤ 演算法有用嗎

　　「演算法有用嗎？」經常有人問我這個問題。很多人在工作中根本不用演算法。偶爾碰到的時候，也不過是使用一些實現好的函數庫。舉例來說，C++ 標準範本函數庫（STL）中有現成的排序、尋找函數；常用的資料結構，如向量（vector）、佇列（queue）、集合（set）也都實現好了。日常工作中了解如何使用這些函數庫似乎就足夠了。

　　但是，演算法在解決一些「有趣」的問題時會造成關鍵作用。不過，這些問題本身的價值卻是見仁見智。

　　讓我們用實例來說話吧。接下來的兩道題目，即使是初學程式設計的人，應該也很容易解決。

　　✤ 最小可用ID，演算法的威力

　　這道題目來自Richard Bird 所著書中的第1章[1]。現代社會中，有很多服務依賴一種稱為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)

　　✤ 小結

　　回顧前面兩個有趣的例題，暴力解法都捉襟見肘。對於第一題，暴力解法尚能解決較短的列表，而在第二題中暴力解法根本行不通。

　　第一個實例展示了演算法的力量，第二個實例展示了資料結構的重要性。有很多有趣的題目在電腦發明之前很難解決，但是透過程式設計和電腦，可以用和傳統方式完全不同的方法找到答案。相對於中小學數學課上所學的方法，這樣的方法並沒有被普遍教授。

　　雖然優秀的演算法、資料結構和數學書汗牛充棟，但是對程序式解法和函數式解法進行對比的卻寥寥無幾。從上面的實例中可以看到，有時函數式解法十分簡潔，並且很接近我們在數學課上所熟悉的思考方式。

　　本書力圖同時介紹指令式和函數式的演算法和資料結構。（Okasaki 的著作[3]中有很多函數式資料結構可供進一步參考，關於指令式的內容可以參考一些經典書[4] 以及維基百科。）本書的範例程式使用了多種程式語言，包含C、C++、Python、Haskell 和Lisp 方言Scheme， 讀者可以從https://github.com/liuxinyu95/AlgoXY 上下載本書的全部範例程式。為了讓具有不同背景的讀者都容易閱讀，所有演算法都提供虛擬程式碼和數學函數描述。

　　由於時間倉促，書中難免存在錯誤，歡迎讀者們和專家批評指正，提供意見和回饋。

　　本書作者電子電子郵件：liuxinyu95@gmail.com。

　　✤ 內容組織

　　在接下來的章節中，我們將先介紹基本的資料結構，此後的一些演算法都會用到它們。第一部分首先介紹資料結構中的"hello world"--二元搜尋樹，接下來說明如何解決二元樹的平衡問題。然後我們將介紹更多有趣的樹，其中Trie、Patricia 和後綴樹可以用於文字處理，而B樹則廣泛應用於檔案系統和資料庫。

　　第二部分介紹堆積的相關內容。我們列出一個抽象堆積的定義，然後介紹如何使用陣列和各種二元樹實現二元堆積（binary heap），接著擴充到其他的堆積，包含二項式堆積、費氏堆積和配對堆積（pairing heap）。

　　陣列和佇列通常被認為是簡單的資料結構，但我們將在第三部分看到，它們實現起來並不容易。

　　作為基本的排序演算法，我們將介紹指令式和函數式的插入排序、快速排序和歸併排序等演算法。第四部分介紹尋找和搜索的相關內容，除了基本演算法，還會介紹諸如KMP這樣的文字比對演算法。

　　附錄介紹關於鏈結串列的基本內容。