# substitution method

去猜遞迴式(recurrence)可能的上下限，然後嘗試使用歸納法進行證明，成功證明之後再去證明 base case 也成立，而 base case 就是一開始假設的 $n_0$ 的範圍 $n_0\le n \le b\cdot n_0$。

例如 $T(n)=2T(n/2)+\Theta(1)$，我們猜 $T(n)=O(n)$，所以假設對於某個 $n_0$ 只要 $n_0 \le n$ 都正確，**那麼我們接著就是要推如果 $n$ 再放大 2 倍會不會正確**

- 因為如果 $2n_0 \le n$，那麼代回 $T(n)=2T(n/2)+\Theta(1)$ 會發現裡面 $T(n/2)$ 的部分就可以使用假設
- 只要使用假設後依舊可以推出 $T(n)=O(n)$，就代表說把 $n$ 的範圍從 $n_0\le n$ 放大 2 倍變成 $2 n_0\le n$ 也是對的
- 那麼之後再放大不管多少倍也都會是對的

所以歸納法證明完畢之後，就是證明沒有證明到的 base case，也就是 $n_0\le n \le 2\cdot n_0$ 的部分

## subtracting a low-order term

如果發現歸納法最後只差一點點，例如：

$$
T(n)=2T(n/2)+\Theta(1)
$$

猜 $T(n)=O(n)$，然後我們假設 $T(n)\le c\cdot n$ 對於足夠大的 $n$，推導後會發現：

$$
\displaylines{
T(n)\le 2T(n/2)+\Theta(1)\\
T(n)\le c \cdot n+\Theta(1)\\
}
$$

- 如果某種情況下得到是減號的話就沒這問題，可以直接再用另一個小於等於移除他
- 但現在因為是加號，必須採用另一種方法，就是重新假設
- 改成假設 $T(n)\le cn-d$，這樣代進去才可以消掉那個加號
- 這樣會得出 $d$ 這個常數的範圍，之後再解出 $c$ 跟 $n_0$ 即可

## Avoiding pitfalls

證明過程中切記別把漸進符號代到過程中使用，因為很容易忽略被隱藏的常數。

例如當你假設 $T(n)=O(n),\ T(n)\le cn$，當你代進式子後：

$$
\displaylines{
T(n)\le 2 T(n/2)+\Theta(n)\\
T(n)\le cn+ \Theta(n)
}
$$

如果你在最後一步很開心的使用 $T(n)\le cn+ \Theta(n) = O(n)$ 那就錯了，原因是因為這個 $O(n)$ 中的那個常數 $c'$ 他必須比你歸納假設中的 $c$ 還要大，所以歸納假設是不成立的。

所以最好是把所有的常數都明寫出來：

$$
\displaylines{
T(n)\le 2 T(n/2)+\Theta(n)\\
T(n)\le cn+ c'n
}
$$

不過最後一樣會湊不出來，因為這個 recurrence 理論上應該是 $\Theta(nlogn)$

# recursion-tree method

$$
T(n)=aT(n/b)+\Theta(n^m)
$$

根據遞迴樹展開的情形可以知道：

- 高度為 $\log_{b}n$
- 第 $i$ 層的花費是 $a^i$ 個 $\frac{n}{b^i}$ 大小的工作 $\Theta((\frac{n}{b^i})^m)$，所以全層 internal node 的花費也就是：
- $$\sum_{i=0}^{\log_{b}n}c\cdot\left(\frac{a}{b^m}\right)^in^m<\sum_{i=0}^{\infty}c\cdot\left(\frac{a}{b^m}\right)^in^m$$
- 如果 $\frac{a}{b^m} < 1$ 的話才有必要換成右邊無限的方式使用無限的等比級數公式，不然就直接加總就行
- 例如像 merge sort 這種，每一項都是 $cn$ 就不能用等比級數公式
- 最後一層葉子的總開銷是 $a^{\log_{b}n}$ 個 $\Theta(1)$ 的工作，也就是 $\Theta(n^{\log_{b}a})$

所以整個遞迴樹就是在看到底是葉子的開銷大，還是過程 internal node 的開銷大。

:::info
如果是不平衡分割的話，算葉子節點的開銷時就不能那樣算，而是要用替代法證明葉子節點是 $O(n)$ 還是怎樣的。
:::

# master method

對於

$$
T(n)=aT(n/b)+f(n)
$$

可以依照三種情形，快速得知複雜度，這三種情形就是上面遞迴樹探討的內部節點大還是葉子大。

## 葉子節點開銷大

如果 $f(n) = O\left(n^{\log_b a - \epsilon}\right)$，其中 $\epsilon > 0$ 是一個常數（即 $f(n)$ 多項式小於 $n^{\log_b a}$），則：

$$T(n) = \Theta\left(n^{\log_b a}\right)$$

## 內部節點比葉子開銷多一點點

如果存在 $k\ge0$

$$f(n) = \Theta\left(n^{\log_b a}lg^kn\right)$$

即 $f(n)$ 與 $n^{\log_b a}lg^kn$ 漸近相等，則：

$$T(n) = \Theta\left(n^{\log_b a} lg^{k+1}n\right)$$

:::info
可以回顧上面遞迴樹法，會發現因為這個情形會讓 Sigma 裡面變成 1，也就是每一層的消費都是一樣的都是 $cn^{\log_ba}\log^kn$，所以乘上有 $\log n$ 層就得到結果了。
:::

## 內部節點開銷大

如果 $f(n) = \Omega\left(n^{\log_b a + \epsilon}\right)$，其中 $\epsilon > 0$ 是一個常數（即 $f(n)$ 多項式大於 $n^{\log_b a}$），並且 $f(n)$ 滿足正則條件 (Regularity Condition)：$a f(n/b) \le c f(n)$ 對於某個常數 $c < 1$ 和所有足夠大的 $n$ 成立，則：

$$T(n) = \Theta(f(n))$$

會需要正則條件是為了保證每往下一層，開銷是變小的

## Change of Variable

如果遇到看起來不適用 master theorem 的情況，通常是分割子問題時不是除以某個常數而是開指數之類的：

$$
T(n)=2T(\sqrt{n})+\Theta(\log(n))
$$

這時候使用變數變換，令 $k=\lg(n),\ 2^k=n$，所以上式可以變成：

$$
T(2^k)=2T(2^{k/2})+\Theta(k)
$$

但是這樣還是不算可使用範圍內，但是很接近了，我們可以定義新的函數 $S(k)=T(2^k)$，所以得到：

$$
S(k)=2S(k/2)+\Theta(k)
$$

這時就可以使用大師法則了，並且瞪眼可以知道這是 $S(k)=\Theta(k\log(k))$。

所以代回去就可以知道 $S(k)=T(2^k)=T(n)=\Theta(k\log(k))=\Theta(\log(n)\log(\log n))$。

# Akra-Bazzi method

大師法則只能適用等分分割的 recurrence，不等分分割的除了使用最原始的替換法之外，還可以使用 Akra-Bazzi method 這個重工具。

準確來說這個 Akra-Bazzi method 是用來解下列的 **Akra-Bazzi recurrence**

$$
T(n)=f(n)+\sum_{i=1}^{k}a_iT\left(\frac{n}{b_i}\right)
$$

其中每個 $a_i$ 是正實數，$b_i$ 是大於 1 的正實數，$k$ 是正數，$f(n)$ 定義在足夠大的非負實數並且那時候自己是非負的。

也就是說每一項子問題有自己的大小跟係數。

## polynomial-growth condition

但是由於實際問題大多是由天花板跟地板函數構成，想要不管他們直接來分析問題並不妥，想要直接套用某些快速工具也不行；但好在只要滿足某些條件，我們就可以安心的去除天花板跟地板。

對於 Akra-Bazzi method，要滿足的條件就是 polynomial-growth condition，不過這個條件的敘述挺長的：

對於定義在足夠大的的正實數的 $f(n)$，如果存在一個 $\hat{n}>0$，使得：

對每個常數 $\phi\ge1$ 存在一個依賴於 $\phi$ 的常數 $d>1$ 使得對所有 $1\le \psi \le \phi$ 跟 $n\ge \hat{n}$，滿足：

$$f(n)/d\le f(\phi n)\le df(n)$$

這個定義告訴我們一些事，像是：

- $f(\Theta(n))=\Theta(f(n))$
- $f(n)$ 漸進上來說是正的 asymptotically positive

但簡單來說，只要 $f(n)$ 長得像：

$$
f(n)=\Theta(n^\alpha \lg^\beta n \lg\lg^\gamma n)
$$

只要 $\alpha,\ \beta,\ \gamma$ 是常數就好，那 $f(n)$ 就滿足 polynomial-growth condition。

但是要注意，指數跟超指數($x^x$ 這種)則不滿足，有一些奇奇怪怪的多項式函數也不滿足。

:::warning
$\lg^\beta n$ 是指 $(\lg n)^\beta$；另一種特殊的是 $\lg^{(\beta)} n$，意思是套用 $\beta$ 次 $\log$ 在 $n$ 上面
:::

### 更高的忍受度

對於滿足 polynomial-growth condition 的 $f(n)$，除了天花板地板不影響分析外，就算把每個子問題函數改成下面這種：

$$
T\left(\frac{n}{b_i}+h_i(n)\right)
$$

只要 $|h_i(n)|=O\left(\frac{n}{\lg^{1+\epsilon}n}\right),\ \epsilon>0$ 和足夠大的 $n$，忽略 $h_i$ 依舊是不影響分析的。
>像是隨便加個常數之類的

## Akra-Bazzi method

使用 Akra-Bazzi method 時要找到一個特殊的實數 $p$，滿足：

$$
\sum_{i=1}^{k}\frac{a_i}{b_i^p}=1
$$

因為只要 $p$ 趨近無限大就會得到 0，趨近負無限大會得到無限大，所以必定存在一個 $p$ 使得上述為 $1$。

接著 Akra-Bazzi method 告訴我們：

$$
T(n)=\Theta\left( n^p \left(1+\int_{x_0}^{n}\frac{f(x)}{x^{p+1}}dx\right)\right)
$$

$x_0$ 是一個足夠大的常數。

但是實際上通常不需要知道 $p$ 是多少，因為可以消掉，例如

$$
T(n)=T(n/5)+T(7n/10)+n
$$

如果真的去找的話 $(1/5)^p+(7/10)^p=1$ 會得到 $p\approx 0.84$，而且通常也解不出來；但是可以換個方法：

- $(1/5)^0+(7/10)^0=2$
- $(1/5)^1+(7/10)^1=0.9$

可知 $0<p<1$。

總先先使用 Akra-Bazzi method 解上述的 recurrence：

$$
\begin{align}
T(n)&=\Theta\left( n^p \left(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx\right)\right)\\
&=\Theta\left( n^p \left(1+\int_{1}^{n}x^{-p}dx\right)\right)\\
&=\Theta\left( n^p \left(1+\left[\frac{x^{1-p}}{1-p}\right]_{1}^{n}\right)\right)\\
&=\Theta\left( n^p \left(1+\frac{n^{1-p}}{1-p}-\frac{1}{1-p}\right)\right)\\
&=\Theta\left( n^p \Theta(n^{1-p})\right)\\
&=\Theta(n)
\end{align}
$$

- 積分時要小心，$\int x^k=\frac{x^{k+1}}{k+1}$ 要先確認 $k\ne -1$
- 因為上面有保證 $0<p<1$ 所以倒數第 3 個等號才可以直接換成 $\Theta(n^{1-p})$