主定理（一般式）

主定理（Master Theorem）是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系，通常采用分治策略解决问题的情况。

主定理简化版的局限

主定理简化版的三种情况：

1. $IF$ $f(n)=O(n^{lo{g}_b(a-\epsilon )})$，and $\epsilon >0$，Then $T(n)=\Theta (n^{lo{g}_b(a)})$
2. $IF$ $f(n)=\Theta (n^{lo{g}_b(a)}\cdot lo{g}^{k}n)$，and $k\ge 0$，Then $T(n)=\Theta (n^{lo{g}_b(a)}\cdot lo{g}^{k+1}n)$
3. $IF$ $f(n)=\Omega (n^{lo{g}_b(a+\epsilon )})$，and $\epsilon >0$，$a\cdot f(\frac{n}{b})\le c\cdot f(n)$ 对于某个常数 $c<1$ 和所有足够大的 $n$ 成立，Then $T(n)=\Theta (f(n))$

简化形式具有一定的限制条件，比如形式上必须是： $$T(n)=a\cdot T(\frac{n}{b})+f(n)$$

并且 $f(n)=n^c$

三个反例：

1. 子问题数量不是常数

$$T(n)=n\cdot T(\frac{n}{2})+n^2$$

2. 子问题数量小于1

$$T(n)=\frac{1}{2}T(\frac{n}{2})+n^2$$

3. 分解问题和合并解的时间不是 $n^c$

$$T(n)=2T(\frac{n}{2})+nlogn$$

---

主定理一般形式

$$T(n)=a\cdot T(\frac{n}{b})+f(n),a>0,b>1$$

1. $IF$ $\exists \epsilon >0$ 使得 $f(n)=O(n^{lo{g}_b(a-\epsilon )})$ ，Then $T(n)=\Theta (n^{lo{g}_b(a)})$
2. $IF$ $\exists k\ge 0$ 使得 $f(n)=\Theta (n^{lo{g}_b(a)}\cdot lo{g}^{k}n)$，Then $T(n)=\Theta (n^{lo{g}_b(a)}\cdot lo{g}^{k+1}n)$
3. $IF$ $\exists \epsilon >0$ 使得 $f(n)=\Omega (n^{lo{g}_b(a+\epsilon )})$，
   且对于某个常数 $c<1$ 和所有足够大的 $n$ 有 $a\cdot f(\frac{n}{b})\le c\cdot f(n)$ ，Then $T(n)=\Theta (f(n))$

主要考虑 函数 $n^{lo{g}_{b}a}$ 与 $f(n)$ 的增长率关系

情况1：$n^{lo{g}_{b}a}$ 比 $f(n)$ 增长的快

$$T(n)=9T(\frac{n}{3})+n$$

• $n^{lo{g}_{b}a}=n^2$,
• $f(n)=n=O(n^{2-ϵ}),ϵ\le 1$
• $\Rightarrow T(n)=O(n^2)$

---

情况2：$n^{lo{g}_{b}a}$ 与 $f(n)$ 增长率类似

$$T(n)=T(\frac{2n}{3})+1$$

• $n^{lo{g}_{b}a}=n^{lo{g}_{3/2}1}=n^0=1$,
• $f(n)=1=\Theta (n^{lo{g}_{b}a}lo{g}^{0}n)$
• $\Rightarrow T(n)=O(logn)$

---

情况3：$n^{lo{g}_{b}a}$ 比 $f(n)$ 增长的慢

• $f(n)$比$n^{lo{g}_{b}a}$ 增长的更快，至少要快 $\Theta (n^{ϵ})$ 倍，且 $af(\frac{n}{b})\le cf(n)$

$$T(n)=3T(\frac{n}{4})+nlogn$$

• $n^{lo{g}_{b}a}=n^{lo{g}_{4}3=n^{0.793}}$,
• $f(n)=nlogn=\Omega (n^{lo{g}_{4}3+ϵ}),ϵ\le 0.207$
• $af(\frac{n}{b})=3(\frac{n}{4})log(\frac{n}{4})\le \frac{3}{4}nlogn=cf(n),c=\frac{3}{4}$
• $\Rightarrow T(n)=O(nlogn)$

---

主定理不适用的情况

1. $n^{lo{g}_{b}a}$ 与 $f(n)$ 的增长率不可比
2. $n^{lo{g}_{b}a}$ 比 $f(n)$ 增长的快，但没有快 $O(n^{ϵ})$ 倍
3. $n^{lo{g}_{b}a}$ 比 $f(n)$ 增长的慢，但没有慢 $O(n^{ϵ})$ 倍

---