# 主定理 Master Theorem

###### tags: `競程`

主定理用來估計遞迴式的複雜度。

## 主定理

有一遞迴式的複雜度如下：

$$
T(n) = a \times T(\frac n b) + n^c
$$

一個規模為 $n$ 的問題，分成 $a$ 個規模為 $\frac n b$ 的子問題，並且需要花 $O(n^c)$ 該層所有子問題合併起來。

想著一顆分治樹，$log_b n$ 為樹高度，$a$ 是每次展開的子節點數量，$n^{log_b a}$ 為所有葉子節點的數量。

**可以想像成，$c$（合併）和 $log_b a$（葉節點數量）哪個大，哪個就決定複雜度。**

\begin{align*}
當\ log_b a < c,\quad T(n) &= O(n^c)\\
當\ log_b a = c,\quad T(n) &= O(n^{log_ba} \times logn)\\
當\ log_b a > c,\quad T(n) &= O(n^{log_ba})
\end{align*}

證明的部分，主定理是把他展開成等比級數，然後用公式求和。

## 主定理的使用

1. 例如 merge sort：
$$
T(n) = 2 \times T(\frac n 2) + n^1
$$

那麼：

\begin{align*}
a &= 2 \\
b &= 2 \\
c &= 1 \\
T(n) &= nlogn
\end{align*}