主定理
证明先不写
将一个规模为 \(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\)
- 若 \(\exists \epsilon > 0\) 使得 \(f(n)=O(n^{\log_b{a}-\epsilon})\)，则 \(T(n)=\Theta(n^{\log_ba})\)
- 若 \(\exists \epsilon \ge 0\) 使得 \(f(n)=\Theta(n^{\log_ba}\log^\epsilon n)\)，则 \(T(n)=\Theta(n^{\log_ba}\log^{\epsilon+1}n)\)
- 若 \(\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) \]
