演算法從入門到「放棄」（2）- 分而治之和解決循環

來自專欄 AnotherWorld1 人贊了文章

本系列文章

演算法從入門到「放棄」（1）- 什麼是演算法？

本文提煉

分而治之（Divide - and - Conquer）和3種解決循環的方法。

分而治之 Divide - and - Conquer

分而治之，簡單來講，就是三步：

1. 分開 Divide，把問題分成一個個小問題，這些小問題是一個個小實例
2. 解決 Conquer，用遞歸把一個個小問題解決掉。如果一個個小問題很少，那就直接把它們解決掉，不需要用到遞歸了
3. 合併 Combine，把一個個小問題的答案合併起來組成原問題的答案

當一個個小問題足夠多的時候，我們就稱之為遞歸情況（recursive case）；當一個個小問題變少了，不再需要用到遞歸的時候，我們稱這個遞歸「到底」了，到達了基礎情況（base case）。

所以，當我們用遞歸解決一個問題的時候，我們會在遞歸的每一個水平都帶入這三步。

循環 Recurrences

那什麼是循環呢？

按照書本上的解釋，循環就是一個描述了按照更小的輸入得到值的函數的等式或不等式。（an equation or inequality that describes a function on terms of its value on smaller inputs）

我個人的理解就是，任何重複執行一個函數的過程，就都是循環。就像書本的解釋，最小的輸入經過一個函數得到一個結果/值，我們再用這個值當做輸入經過同一個函數得到值，再用這個值經過同一個函數。。。。。直到達到我們在第一部分提到的基礎情況，這時候，循環就結束了。

3種解決循環的方法

• 替換法 substitution method，首先猜一個範圍，接著用數學歸納法證明我們的猜想是正確的。

舉個例子（例子來源），有下面這個循環，我們需要確定上範圍 (upper bound)。

就像上圖所寫，先是猜想，T(n) <= cn*log(n)；接著是證明，第一步是驗證基礎情況，n=1；正確之後是第二步，歸納過程，對T(n) 和cn*log(n)里所有的n 用n/2 代替。

為什麼用n/2 ？我們要假設這個範圍是對任何小於n 的正數m 有效，大部分情況直接使用m = n/2 了。

為什麼在這裡不用n-1 呢？因為我們的猜想里有log 函數，想想log 函數在x = 1 臨界點左右兩邊正負不同的情況（個人理解，若不對或則是別的原因，請在評論區指明，謝謝！）。

一直覺得這個辦法像玄學，怎麼猜這個範圍，需要你做很多演算法題得出的經驗和自己的想像力。但是憑藉下面將要介紹的另外一種方法，猜想也就變得不那麼雲里霧裡。

• 遞歸樹方法 recursion-tree method，把循環轉換成每個節點代表遞歸中不同水平里產生的成本的樹。我們再用方法把邊界的和求出，就可以解決循環了。

遞歸樹可以幫助我們想出一個好的猜想，然後我們就可以用替換法來驗證。舉個例子（例子來源），下面的函數畫成遞歸樹。

首先我們看下這棵數有多高呢？因為這棵樹的每個節點的尺寸都是上一個的1/2，當我們最終到達底端，底端(在深度i）的節點尺寸是n/(2^i)。也就是說，當n=1，節點的尺寸是n/(2^i) = 1，換句話說，當i = log2(n)。所以這棵樹的高度是log2(n)。

接著，我們來判斷這棵樹每個水平消耗的成本。從圖中可以看出，每個水平的節點數量是上一水平的8倍，所以在深度i，節點數量是8^i。因為每個小問題的尺寸都是上一級的1/2，所以每個深度為i (i=0,1,2,3....log2(n-1))的節點，消耗的成本是(n/2^(i))^2. 現在求每個深度為i 的水平上所有節點的成本，8^i* (n/2^(i))^2 = (8/4)* n^2 = 2n^2. 而在底層，當深度為log2(n), 我們有8^(log2(n)) = n^(log2(8)) = n^3 個節點，每個都消耗成本T(1) = 1，所以總消耗是n^3.

然後就是計算整棵樹所有水平消耗的成本了。就是上圖中最後一個等式。我們將它整理一下，

因此我們有了一個猜想，T(n) = O(n^3)，然後我們就可以用替換法來驗證了。XD

• 主方法 master method，提供了類似下面格式 T(n) = aT(n/b) + f(n) 的循環的範圍。格式中a>=1, b>1，f(n) 是一個已知函數。

整理完前兩種方法，第三種即將要說明的方法真的是太簡便了。這就像是提供給了我們菜譜，只要材料對了，跟著步驟走肯定就能做出一道美味可口的菜。

但是也有限制，除了上面提到的格式，我們還得記住三種情況：

我們在格式中提到的n/b 即可以代表floor n/b 也可以代表 ceil n/b. (地板功能就是我們輸入一個實數x，它給出小於或等於x 的最大整數。類似地，天花板函數就是將x 轉換到大於或等於x 的最小整數。例如，floor(2.4)=2, ceil(2.4)=3)

1. 如果存在大於0的x 滿足f(n) = O(n^(logb(a) - x) ，也就是說f(n) 小於n^(logb(a) 函數，那麼T(n) = ?(n^(logb(a)).
2. 如果f(n) = ?(n^(logb(a))，那麼T(n) = ?(n^(logb(a)* lg(n)) = ?(n^(f(n)* lg(n)) .
3. 如果存在大於0的x 滿足f(n) = Ω(n^(logb(a) + x) ，也就是說f(n) 大於n^(logb(a) 函數，而且同時滿足「如果存在小於1的c，對於所有的足夠大的n，a* f(n/b) <= c* f(n)」的條件，那麼T(n) = ?(f(n)).

針對這三種情況，書本給出了對應的三個例子。

這三種方法里我最喜歡的就是主方法，只要循環符合它的特定形式，直接公式走起，簡潔明了。

補充 - 循環(loop), 遞歸(recursion), 遍歷(traversal), 迭代(iterate)之間的區別

在查閱網上資料的時候，發現了這個有趣的區別總結，就作為補充放在這了。來源：編程中，循環、迭代、遍歷和遞歸之間的區別，侵權刪。

• 循環(loop) - 最基礎的概念, 所有重複的行為。大部分的遞歸, 遍歷, 迭代, 都是循環。
• 遞歸(recursion) - 在函數內調用自身, 將複雜情況逐步轉化成基本情況；經典的解釋就是，什麼是遞歸，參見遞歸。
• (數學)迭代(iterate) - 在多次循環中逐步接近結果
• (編程)迭代(iterate) - 按順序訪問線性結構(數組, 隊列)中的每一項，在很多編程語言中表現為foreach語句
• 遍歷(traversal) - 按規則訪問非線性結構(樹, 圖)中的每一項

在接下來的幾篇文章中，將著重講的是各種排序演算法。

如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！