時間複雜度 — 遞迴(下) — Master Theorem
本篇接續上一篇，要介紹的是第二個方法Master Method。
本篇章節：
1. Master Theorem定義
2. Master Theorem所出現的三種 Case
3. 幫助理解原理之 Recursion Tree
4. Master Theorem的出處
5. 總結論
6. 範例
分析Divide & Conquer演算法時，我們通常使用以下兩種方法：
1. Recursion-Tree Method搭配Substitution Method(這裡稱為「數學歸納法」)
2. Master Method：這個方法很直觀（有時間的話，建議先瞭解「方法一」再了解這個方法會比較全面）
為什麼會說Master Method比較直觀呢？
Ans: 因為它就像食譜(Cookbook)一樣，只要照著書上的指示，就可以找到得到美味的食物(答案)。
1. Master Theorem定義：
以我自己理解後的翻譯：
假設有個 a ≥ 1和 b > 1 的常數，f(n)為一函式，然後假設 T(n)定義在非負整數上，遞迴公式如下：T(n) = a T( n / b ) + f(n)。2. Master Theorem所歸納的三種情況：
依照上述定理，歸類出三種情況（這邊先講結論之後，之後再說明理由）
Case 1：
Case 2：
Case 3：
為什麼Case 3 要多加一個 Regularity Condition（正規條件）?
Ans: 只是想要更加確認，所得出的答案一定會贏過「葉節點的部分」。
詳細說明請參考：Regularity condition
在上述所說的3個Case中，應該會想說為什麼都是用log跟f(n)來做比較吧。接下來就讓來做解釋吧！
3. 幫助理解之Recursion Tree
先看一個範例來幫助後面的理解。
遞迴關係式如下：
畫 Tree應該要逐步來畫，為了方便，這邊暫時省略。
有了上面的圖後，我們可以用上一篇所說的來將此遞迴關係式作拆解。
這邊跟上次有c * n 的不一樣是因為，上次題目給的遞迴關係式有Θ(n)，為了做替換，所以我們把它換成cn。而這次題目沒有給，直接給了n。
首先，先看我們Cost的部分，總共做了多少次的合併？
Ans: 從圖二，看到每一層的 Cost從 n² + 2¹n² + 2²n² + 2³n³ +… + 2^k n² ，先把 n²提出來，再利用等比公式得到：
再來，前面T(1)的部分，要得出T(1)的話，前面需要拆成多少個子問題？
Ans: 從圖二得到，經過 8^k次方後，我們可以拆解到 T(1)。
總和上述結果：
那k又是多少？
和上一篇所說的相同，從圖二得到： n/ (2^k) = 1 (原始資料 n不斷砍半再砍半，經過 k次的砍半後，最終只剩一個)
整合所有的資訊後：
想必看到這邊一定會有疑問，那這棵樹到底跟Master Theorem的logb a有什麼關係啊？
我們就快要講到了！再等一下～～
4. Master Theorem的出處
由前面的範例後，我們可以自然的延伸到下圖：（這邊我就直接把參考資料的圖片，放上來）
看到上面一對可怕的數字，大家不用害怕，先從圖上面找一些性質。
從圖八中Recursion Tree所得到的特性：
把圖八中的 Total ，類似此式：
最後我們用上面的想法來帶入課本的結論得到：
其實這些遞迴關係式即是把他們拆成兩個部分，一個是由leaf主導，一個是由root主導。用「主導(Dominated)」這個詞的原因是說，用這兩個來判斷，是Leaf還是Root影響T(n)比較多，如果較多的那個理所當然，漸進函數就會以它為主了。
5. 總結論
如果不清楚怎麼用的話，請看下方例子。
6. 範例
題目一：
題目二：
Case 3比較麻煩一點，還需要多證明一個Regularity Condition
題目三：
這篇也就到這邊結束了，如果有錯誤還請各位多多指教，比較多手寫的部分，希望大家不要太介意。那我們就下次再見吧～～
