主定_

主定理

证明先不写

将一个规模为 $n$ 的问题，通过分治得到 $a$ 个规模为 $n/b$ 的子问题，每个递归带来的额外计算为 $f(n)$ ，则有

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

其中 $a,b$ 为常数， $n\in \mathbb{N}^*,a\ge 1,b > 1,n/b$ 解释为 $\left\lfloor{\dfrac{n}{b}}\right\rfloor$ 或 $\left\lceil\dfrac{n}{b}\right\rceil$

1. 若 $\exists \epsilon > 0$ 使得 $f(n)=O(n^{\log_b{a}-\epsilon})$，则 $T(n)=\Theta(n^{\log_ba})$
2. 若 $\exists \epsilon \ge 0$ 使得 $f(n)=\Theta(n^{\log_ba}\log^\epsilon n)$，则 $T(n)=\Theta(n^{\log_ba}\log^{\epsilon+1}n)$
3. 若 $\exists \epsilon>0$ 使得 $f(n)=\Omega(n^{\log_ba+\epsilon})$ ，且 $\exists c<1 , \forall n \gg 1$ 使得 $af(n/b)\le cf(n)$ ，则 $T(n)=\Theta(f(n))$

其中 $\epsilon,c$ 均为常数。

---

常用结论

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

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

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

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

---

例题

---

例1：

$$T(n) = 6T(n/3) + O(n^{\frac{3}{2}})$$

解：

根据公式 $a=6,b=3$

$$\log_b a = \log_3 6 = 1 + \frac{\ln 2}{\ln 3} \approx 1.63$$

注：不要问我为什么可以手算出来，因为我背了自然对数表

并且

$$f(n) = O(n^{\frac{3}{2}}) = O\left(n^{\log_3 6 - \epsilon}\right)$$

故

$$T(n) = \Theta\left(n^{1 + \log_3 2}\right)$$

---

例2：

$$T(n) = 4T(n/2) + \Theta(n^2)$$

解：

根据公式 $a=4,b=2$

$$\log_b a =2$$

并且

$$f(n) = \Theta(n^2) = \Theta(n^2\log^0 n)$$

故

$$T(n) = \Theta(n^2 \log n)$$

---

例3：

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

解：

根据公式 $a=1,b=2$

$$\log_b a = 0$$

并且

$$f(n) = \Theta(\sqrt{n}) = \Omega(n^{0 + \frac{1}{2}})$$

同时

$$\exists c < 1 \quad \mathrm{s.t.} \quad f(n/2) = \frac{\sqrt{2}}{2}f(n) \le c f (n)$$

此时 $\frac{\sqrt{2}}{2}< c < 1$ ，故

$$T(n) = \Theta(\sqrt{n})$$

---

例4：

$$T(n) = 4T(n/3) + \Theta(n^2)$$

解：

根据公式 $a=4,b=3$

$$\log_b a = 2\log_32 \approx 1.26$$

并且

$$f(n) = \Theta(n^2) = \Omega(n^{1.26 + \epsilon})$$

同时

$$\exists c < 1 \quad \mathrm{s.t.} \quad 4f(n/3) = \frac{4}{9}f(n) \le cf(n)$$

此时 $\frac{4}{9} < c < 1$

故

$$T(n) = \Theta(n^2)$$