# 麻省理工學院公開課-算法導論_第二講-漸近符號，遞迴以及解法
###### tags: `MIT` `Algorithms` `網易`

[課程連結](http://open.163.com/newview/movie/free?pid=M6UTT5U0I&mid=M6V2T4T2E)

## Asymptotic Notation

$f(n) = O(g(n))$，裡面的$O$稱為Big O notation，意謂著存在著$c > 0$、$n_0 > 0$，使得$0 \leq f(n) \leq c \cdot g(n) \space \text{for all} \space n \geq n_0$，值得注意的是，這邊的等號並不代表相等，舉例來說，$2n^2 = O(n^3)$，Big O意謂著Upper Bound，也就是小於等於。直觀來看，這代表著$f(n)$是$g(n)$的某些函數的集合。


我們可以將$O(g(n))$定義為一個函數集，也就是$f(n), \space \text{exists} \space c > 0, n_0 > 0$，使得$0 \leq f(n) \leq c \cdot g(n) \space \text{for all} \space n \geq n_0$

因此，上面的範例$2n^2 = O(n^3)$意謂著$2n^2 \in O(n^3)$

## Macro convention

我們定義Big O來代表某一個事情它是Big O，舉例來說：
* $f(n) = n^3 + O(n^2)$

這代表說，這個$f(n)$主要是$n^3$，但它還有一些低階項，也就是$O(n^2)$，也就是$f(n)$還存在著一個函數$h(n) = O(n^2)$，即$f(n) = n^3 + h(n)$


另一個範例，$n^2 + O(n) = O(n^2)$，一樣的，這邊的等號不是相等(equal)，而是代表著"is"，左邊的東西就是右邊的意思。也就是對任意的$f(n) \in O(n)$，如果$h(n) \in O(n^2)$，那麼$n^2 + f(n) = h(n)$

## Omega notation

$\Omega(g(n)) = f(n), \space \text{exists} \space c > 0, n_0 > 0$，使得$0 \leq c \cdot g(n) \leq f(n) \space \text{for all} \space n \geq n_0$


舉例，$\sqrt{n} = \Omega(\log n)$(假設$n=8$)

## Theta notation

* $\Theta$，是Big-O與$\Omega$的交集
* little-o，小於
* little-omega，$\omega$，大於

little不同於Big在於，little是對任意的c都存在一個constant $n_0$


舉例，$2n^2 = o(n^3)$，這個式子成立於$n_0 = \dfrac{2}{c}$，這邊的$c$你可以把它想成是一個$\epsilon$，一個非常小的值。

但換個範例來看，$\dfrac{1}{2}n^2 = \Theta{^2}$是不可能成立的。

## Solving recurrences

有三種方式可以解遞迴問題，首先說明的是substitution method，也就是代換法。課程中提到，目前並沒有一種通用的方式可以很好的解遞迴問題，因此只能嚐試，但要確認是否正解解題是很容易的。

代換法通常有效，以下是步驟：
1. 猜答案，但你要猜的對，這一步很困難，不過又不是那麼難，只要猜個大概
2. 解出常數項，試著驗證這個遞迴式是否滿足條件，這是一個關鍵問題，也就是說，代換法是使用歸納的方式來驗證假設是正確的
3. 得到常數項，讓假設成立

## Substitution Method Example

$T(n) = 4T(n/2) + n$：
* 猜，忽略掉常數項$n$，看$4T(n/2)$，其中$T(n/2)$的兩倍就是$T(n)$，然後乘上一個乘數$4$，什麼樣的函數在你對參數加倍的時候，其輸出會增加4倍?就是$n^2$，不過先假設$T(n)=O(n^3)$
* 代換法中不能用Big-O，因此假設$T(k) \leq ck^3 \space \text{for} \space k < n$
* 沒有使用Big-O的關鍵在那，如果你有一個有限的Big-O關聯鏈(finite chain of Big-O relation)，舉例來說，$n^2 = O(n^3) = O(n^4)$，你得到了$n^2 = O(n^4)$，但如果這是一個無限的關聯鏈，那第一項與最後一項的Big-O的關聯就不成立
* 舉例來說，證明$n = O(1)$(我們知道這是假的)，利用歸納來做證明，$1 = O(1)$，這是對的，$n-1 = O(1)$，那$n = (n-1) + 1$，剛才已經說明了，$1 = O(1)$，$n - 1 = O(1)$，這樣還會成立嗎?因此，我們不能在Big-O上做歸納，所以我們要保證常數不會變化，因此用代換法
* 因為我們說，對所有的$k < n$成立，所以我們要來證明$k = n$的情況。
* 將遞迴式展開$T(n) = 4T(n/2) + n$，根據上面的假設，我們代換為$T(n) \leq 4c(n/2)^3 + n = \dfrac{1}{2}cn^3 + n$，我們的目標是證明$\leq cn^3$，因此寫下目標，再處理餘項，因此$=cn^3 + (\dfrac{1}{2}cn^3 + n) \ leq cn^3$，其中$(\dfrac{1}{2}cn^3 + n)$就是餘項
* 為了讓上面的數學式成立，我們必須保證餘項的部份不會是負數，因為負負得正，就不會成立，因此$(\dfrac{1}{2}cn^3 + n) \geq 0$，只要$c \geq 1$就可以成立，這邊的$n$是任意數$n^3 > n$，因此$n \geq 1$

我們證明，$T(n)$小於等於某一個常數乘上$n^3$，某一個常數就是指1，剛才證明得到的。雖然證明，但這並不是一個嚴謹的Upper Bound，因為我們知道$n^2$也是成立的。


現在證明，$T(n) = 4T(n/2) + n$ = O(n^2)$：
* 假設，$T(k) \leq c \cdot k^2 \space \text{for} \space k < n$
* $T(n) = 4T(n/2) + n \leq 4c(n/2)^2 + n = cn^2 + n = cn^2 - (-n)$，這邊可以發現到，我們希望最終bound在結果小於等於$cn^2$，那$n$就必需是一個負值，不然無法成立，但$n$必需大於0，因此最後雖然可以看的出來是$O(n^2)$，但這並沒有用，這個歸納證明並沒有成功


我們需要改變假設，可以發現到上面在平方項的部份，其常數$4$很漂亮的就被約掉然後就剩一個$c$，也因此我們無法再減掉低階項的$n$，那我們是不是可以再引入一個參數：
* 假設，$T(k) \leq c_1 \cdot k^2 - c_2 \cdot k \space \text{for} \space k<n$
* $T(n) = 4T(n/2) + n = 4(c_1(n/2)^2 - c_2(n/2)) + n = c_1n^2 + (1 - 2c_2) \cdot n = c_1n^2 - c_2n - (-1+c_2) \cdot n$，一樣的，我們需要餘項的部份是非負
* 什麼時候$c_2 - 1 \geq 0$?，就在$c_2 \geq 1$，這樣，我們就可以寫下bound，$\leq c_1n^2 - c_2n \space \text{if} \space c_2 \geq 1$，就在任意的$c_1$與$c_2 \geq 1$的情況下，我們bound住了

但要注意的是，$c_1$要夠大，我們看一下base case，$T(1) \leq c_1 - c_2$，而$T(1) = \Theta(1)$，因此我們說，$c_1$必須有相對於$c_2$明顯的大才能夠成立。

## Recursion-tree method

假設，$T(n) = T(n/4) + T(n/2) + n^2$，意謂著一個工作會分四個，再分兩個，最終再處理一個$n^2$的工作。遞迴樹的展開如上圖所示，不斷的往下擴展。


一路的展開到最後$T$是常數的狀態，我們要知道，最終會有多少的節點，這是一個很困難的問題，因為每一個枝的大小都是不一樣的。不過，有一點可以先知道的是，它不會超過$n$。


然後，我們對每一層求和，很直觀的：
1. 第一層是$n^2$
2. 第二層是$\dfrac{5}{16}n^2$
3. 第三層是$\dfrac{25}{256}n^2$
4. ...

(搞數學的有三種人，會計算跟不會計算的，那還一種是什麼人??叫底下的人計算..我猜)


我們看到一個脈絡，每一層都是乘上$\dfrac{5}{16}$，這是一個等比級數的問題，將式子列出來：
* $1 + 5/16 + 25/16 + \cdots + 5^k/16^k < 2n^2 = O(n^2)$
* 等比級數的一個特性：$1 + 1/2 + 1/4 + .... = 2$，上面的式子更小，因此可以推論結果

等比級數：$S_n=a_1(1-r^n)/(1-r)$，參考[等比級數師傅](https://web.ntnu.edu.tw/~496403367/teach/master4.htm)

## Master method

限制較多，只能應用於某些狀況，即$T(n) = aT(n/b) + f(n)$(明顯不適用剛才的案例)：
* $a$意謂著切成幾個子問題，且$a \geq 1$
* 每個子問題的大小為$n/b$，且$b > 1$，我們要確認問題的大小有縮減
* 再加上一個非遞迴的$f(n)$，其漸近為正(asymptotically positive)，也就是對足夠大的$n$而言，$f(n)$是正的，也就是$f(n) > 0 \space \text{for} \space n \geq n_0$


Master method的一個簡單的觀念，就是將非遞迴的部份跟一個非常特殊的函數做比較，也就是$n^{\log{b^a}}$，這是遞迴樹枝葉節點的數點，分三種情況：
1. $f(n) = O(n^{\log{b^{a-\epsilon}}}) \space \text{for} \space \epsilon > 0$，這種情況下的結果為$T(n) = \Theta(n^{\log{b^a}})$
2. $f(n) = \Theta(n^{\log{b^{a}}} \text{lg}^kn) \space \text{for} \space k \geq 0$，這種情況下的結果為$T(n) = \Theta(n^{\log{b^{a}}} \text{lg}^{k+1}n)$


3. $f(n) = \Omega(n^{\log{b^{a+\epsilon}}}) \space \text{for} \space \epsilon > 0$，且$af(n/b) \leq (1- \epsilon ')f(n) \space \text{for} \space \epsilon ' > 0$這種情況下的結果為$T(n) = \Theta(f(n))$


範例說明Case1，$T(n) = 4T(n/2) + n$，$a=4, b=2$：
1. 計算$n^{\log{b^a}} = n^2$，比$n$多了一個項次，因此為$T(n)=\Theta(n^2)$


範例說明Case2，$T(n) = 4T(n/2) + n^2$，$k=0, a=4, b=2$：
1. $T(n)=\Theta(n^2 \text{lg} n)$


範例說明Case3，$T(n) = 4T(n/2) + n^3$：
1. $T(n)=\Theta(n^3)$

最後一個範例，$T(n) = 4T(n/2) + n^2/\text{lg}n$，這個問題並不適合用Master method來解，必需用遞回樹來求解。


我們用遞迴樹來說明Master method，root是$f(n)$，根據$a$展開子工作，每個子工作有著$f(n/b)$的量，一直展開到最後的base case，$\Theta(1)$，那樹的高度是多少?是$\log_bn$，就是我們將所有的工作一路降到最1所需要的次數。

現在我們知道，我們有$a$個分枝，跟樹的高度為$\log_bn$，我們就可以知道最終的節點，也就是$\Theta(1)$的數量會有$a^h$，也就是$a^{\log_bn}$，依據對數的特性，把$a, n$調換，得到$n^{\log_ba}$。

最頂層的$f(n)$、第二層的$a(f(n/b))$、第三層的$a^2(f(n/b^2))$，在Case3中，這呈幾何級數遞減，因此，最高項的$f(n)$就會是主要的部份，因此在Case3中我們得到的是$\Theta(f(n))$


1. 在Case3中，我們假設成本是隨著遞迴樹向下以幾何級數遞減，因此最高項是在最頂層。
2. 在Case1中，我們假設成本是隨著遞回樹向下以幾何級數遞增，因此最高項是在最下面。
3. 在Case2中，我們假設遞迴樹的最上、最下的最高項是一樣的，因此為$f(n) \cdot h$，也就是$f(n) \cdot \log_bn$，不考慮常數$b$，因此得到$f(n) \cdot \log n$

以上都是概略說明，以課本證明為主。