# 分治
## 主定理

大多數的分治都可以寫成
$$T(n) = aT(\frac{n}{b})+f(N)$$

- $T(N) \implies$總複雜度
- $n \implies$ 問題大小
- $n/b \implies$子問題大小

:::success
就只要 $O(n^{log_ba})$和 $f(n)$ 比較誰大
誰大取誰，一樣大就多一個$log$
:::

$$
\begin{cases}
\begin{align}
T(n) = O(n^{log_ba}) \qquad & if \; n^{log_ba} \gt f(n) \\
T(n) = O(f(n)) \qquad & if \; n^{log_ba} \lt f(n) \\
T(n) = O(n^{log_ba}) \qquad & if \; n^{log_ba} = f(n)
\end{align}
\end{cases} $$

## 主定理應用

### 最近點對、合併排序
諸如$T(n) = 2T(\frac{n}{2}) + f(n)$
帶入即得$n^{log_22} = n \implies T(n) = O(nlogn)$

### 多項式乘法
假設有兩個多項式 $f(x), g(x)$同為$N$次
將$f(x)$分成兩個$N/2$次的多項式$f(x) = f_l(x) + x^{\frac{N}{2}} f_r(x)$
將$g(x)$分成兩個$N/2$次的多項式$g(x) = g_l(x) + x^{\frac{N}{2}} g_r(x)$
假設$f_l(x) = a_1, f_r(x) = a_2, g_l(x) = b_1, g_r(x) = b_2$
$$
\begin{align}
f(x) \times g(x)
&= (a_1 + x^{N/2} a_2 ) \times (b_1 + x^{N/2}b_2) \\
&= a_1b_1 + x^{N/2}(a_1b_2+a_2b_1) + x^N a_2b_2
\end{align}
$$
:::danger
這邊的a, b都是多項式乘法，亦即若函數叫做mul(f,g), $a_1b_1$亦需要呼叫$mul(a_1,b_1)$ 只是變成子問題
:::
會發現這樣做會有四次的矩陣相乘($a_1b_1, a_1b_2, a_2b_1, a_2b_2$)需要相加，且妹次的$N\rightarrow N/2$，然後相加都是$O(N)$
可以得到$$T(n) = 4T(N/2) + f(N)$$
由主定裡得到複雜度$O(N^2), (n^{log_24}=n^2)$

#### 優化
可以嘗試做一些優化, 觀察到 $$(a_1+a_2)\times(b_1+b_2) =a_1b_1 + a_1b_2 + a_2b_1 + a_2b_2$$
發現四個都出現了，又因為多項式相加不影響次數，所以$(a_1+a_2)(b_1+b_2)$一樣可以拆成$N\rightarrow N/2$的子問題

所以如果假設 $c=(a_1+a_2)\times(b_1+b_2)$
$$f(x) \times g(x) = a_1b_1 + x^{N/2}(c-a_1b_1-a_2b_2) + x^N ( a_2b_2)$$

只需要算出$a_1b_1, a_2b_2, (a_1+a_2)(b_1+b_2)$這三個的矩陣相乘再透過$c-a_1b_1-a_2b_2$得到$a_1b_2+a_2b_1$即可

分治式變成$T(N)=\color{red}{3}T(N/2)+f(N)$
複雜度$O(n^{log_{2}\color{red}{3}})$