遞迴關係（四）（Recurrence relation-4）

遞迴關係（四）（Recurrence relation-4）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授責任編輯

連結：遞迴關係（三）

摘要：本篇介紹電腦科學中的「合併排序法（merge sort）」，藉此呈現遞迴關係在電腦科學領域的應用。

接著要介紹電腦科學中非常根本的排序（sort），這個領域的理論發展完全立基於對遞迴式的分析。底下因篇幅關係只介紹「合併排序法（merge sort）」，希望藉此能使讀者一窺遞迴關係在電腦科學中所扮演的的根本角色。

$$(2)$$  Merge Sort（合併排序法）

假設有排成一列打亂順序的 $$8$$ 個相異數字要重新由小排到大。一個簡單的想法是不停地把較小的數和其左邊的數交換，這就是所謂的泡沫排序法（Bubble sort，想像小泡泡不停往水面移動）。比如 $$87654321$$ 要排成 $$12345678$$，一共要交換 $$28$$ 次（$$1$$ 換到最左邊要 $$7$$ 次，$$2$$ 換到最左邊要 $$6$$ 次，以此類推，所以要 $$7+6+5+4+3+2+1=28$$ 次）。

一般來說 $$n,…,3,2,1$$ 按此方法要排好，要交換 $$C_2^{n}=\frac{n(n-1)}{2}$$ 次。這是一個平方增長的函數，用電腦科學的講法是 $$O(n^2)$$。

但泡沫排序法並不是好的排法。另一個想法是這樣。假設左手邊有四個數已經排好，右邊有四個數也已經排好。不妨假設是

$$2457,~~~1368$$

則現在要把兩個併成一個，只要不停地比較每個字串的最頭頭，取出小數即可，這樣要用掉 $$8$$ 次動作。

取出 $$1$$，剩下 $$2457,~~~368$$
取出 $$2$$，剩下 $$~~457,~~~368$$
取出 $$3$$，剩下 $$~~457,~~~~~68$$
取出 $$4$$，剩下 $$~~~~57,~~~~~68$$
取出 $$5$$，剩下 $$~~~~~~7,~~~~~68$$
取出 $$6$$，剩下 $$~~~~~~7,~~~~~~~8$$
取出 $$7$$，剩下 $$~~~~~~\varnothing,~~~~~~8$$
取出 $$8$$，結束

所以，將排這八個需要的動作次數記為 $$a_8$$，則有遞迴關係

$$a_{8}=a_{4}+a_{4}+8=2a_{4}+8$$

其中 $$a_4$$ 為將四個數按照同樣方法由小到大順序的動作次數。這樣的排序法就稱為 Merge Sort。

一般來說，將 $$n$$ 個數排序需要的動作次數是

$$\displaystyle a_n=2a_{\frac{n}{2}}+n$$

（此處不妨假設 $$n$$ 是 $$2$$ 的冪次，這樣一直除以 $$2$$ 才會除得盡。實際上是不是 $$2$$ 的冪次並不影響最後的結論，只要在分兩堆時盡量均分就好。）

怎麼解？先不管怎麼解這個遞迴一般項，上述想法顯然可以推而廣之，分成三堆，四堆或更多堆，然後再併起來，都可以得到遞迴。沒錯，這就是所謂的 Divide and Conquer（各個擊破法，或稱 D&Q，分治法）思考 — 先把問題分成一些小片，每片處理後再併起來。一般來說，分治法可以得到遞迴式

$$a_n=p\cdot a_{\frac{n}{q}}+f(n)$$

其中 $$p\geq 1,q>1$$ 都是常數，$$f(n)$$ 是 $$n$$ 的函數。

問題是，得到遞迴是一回事，解出一般項是另一回事。即使連 Merge sort 都是非常困難的（比上一篇解費波那契遞迴還難）。幸運的是，在電腦科學中，我們只要得到影響力最大的最關鍵的那一項（如同泡沫排序的 $$C_2^{n}=\frac{n(n-1)}{2}$$ 之中我們只關心 $$N^2$$，即 $$O(n^2)$$。

關於分治法所得的遞迴式 $$a_{n}=p\cdot a_{\frac{n}{q}}+f(n)$$，可以利用一個相當有用的定理，稱為 Master Theorem（主定理），得到最關鍵的那一項。以Merge sort 而言，利用 Master Theorem 可以得到重要的結論：

$$a_{n}=O(n \log n)$$。

因為 $$\lim\limits_{n\to\infty}\frac{n^2}{n\log n}=\infty$$，所以當資料數多時，Merge Sort 的效率比泡沫排序法好太多太多，兩者完全是不同數量級的。沿著這條線下去，就是「演算法」這門學問的核心目標了  —  如何設計更有效率的演算法，而遞迴在其理論發展中扮演著重要的角色。

連結：遞迴關係（五）

參考文獻：

1. Tucker, Applied Combinatorics, 5th edition, Wiley.
2. Brualdi, Introductory Combinatorics, 5th Edition, Pearson.

延伸閱讀：

1. 教育部，高中課程綱要(99)，2010。
2. Knuth , Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition), 1998.
3. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 2009.