浅谈 $T(n) = a(\lfloor\frac{n}{b}\rfloor) + f(n)$

主定理【master theorem】

本文部分参考《算法导论》。相关证明由于过于复杂，已略去。

前言

$\Theta$ 读作 theta，即等于。
$O$ 读作 big-oh，即小于等于。
$o$ 读作 small-oh，即小于。
$\Omega$ 读作 big omega，即大于等于。
$\omega$ 读作 small omega，即大于。
$T(n)$ 时间复杂度。
$f(n)$ 关于 $n$ 的函数。
若 $f(x)$ 多项式大于 $g(x)$，则存在实数 $e > 0$，使得 $f(x)>g (x) \times x^e$。
若 $f(x)$ 渐进大于 $g(x)$，则存在实数 $c > 0$和 $k$，使得对于任意 $n >= k$ 有 $c\times f(x) >= g(x)$。

对于 $\log n$，不需要弄清其具体的底数。原因在于 $\lim \limits_{n \to \infty}\frac{\log_x n}{\log_y n} = \frac{\ln y}{\ln x}(x \not = y)$。即 $\log$ 级别的渐进意义是一样的。

主定理

对于一个形如 $T(n) = aT(\frac{n}{b}) + f(n)$ 的式子（令 $a \ge 1,b > 1$ 且为常数），有以下渐近界：

$\begin{cases} T(n) = \Theta (n^{\log_b a}) \text{ If }\exists \varepsilon > 0,f(n) = O(n^{\log_b a - \varepsilon})\\\\ T(n) = \Theta (n^{\log_b a}\log n) \text{ If }f(n) = \Theta(n^{\log_b a})\\\\ T(n) = \Theta (f(n)) \text{ If } \exists \varepsilon > 0,f(n) = \Omega(n^{\log_b a + \varepsilon}) \text{ and If } \forall n \to \infty,\exists c < 1, \ aT(\frac{n}{b}) \le cf(n)\\ \end{cases}$

简单的，我们可以描述成以下情况：

$T(n)= \begin{cases} O(n^d),d > \log_b a\\\\ O(n^d \log n),d = \log_b a\\\\ O(n^{\log_b a}),d < \log_b a\\ \end{cases}$

例题

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

$\because b = 2,a = 2,f(n) = \Theta(n^{\log_2 2}) = 1\\ \therefore T(n) = \Theta(n \log n)\\$

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

$\because b = 3,a = 9,f(n) = n\\ \because \Theta (n^{\log_b a}) = \Theta (n^2),f(n) = O(n^{\log_3 9 - \varepsilon})= O(n^2) \textit{ If }\varepsilon = 1\\ \therefore T(n) = \Theta(n^2)\\$

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

$\because b = 4,a = 3,f(n) = n \log n\\ \because \Theta (n^{\log_b a}) = O (n^{0.793}),f(n) = \Omega(n^{\log_b a}) = \Omega(n^{\log_4 3 + \varepsilon})\textit{ If }\varepsilon \thickapprox 0.2\\ \because n \to \infty,aT(\frac{n}{b}) \le cf(n) \textit{ If } c = \frac{3}{4}\\ \therefore T(n) = \Theta(n \log n)\\$

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

可以求出 $b = 2,a = 2,f(n) = n \log n,\Theta (n^{\log_b a}) = O (n)$。看似是主定理的第三种情况，但是发现 $\frac{f(n)}{n^{\log_b a}} = \log n < n^\varepsilon(\varepsilon > 0)$，也就是 $\log n = o(n^\varepsilon)$，即两者不同阶。

故只能采取递归树的方式解决，将叶子节点与非叶子节点分开计算最后答案是 $\Theta(2^{\log n}) + \Theta(n \sum_{i = 1}^{\log n} 1) = \Theta(n) + \Theta(n\frac{\log n(1 + \log n)}{2}) \thickapprox O(n \log^2 n)$。

总结

其中第一情况要求的小于是多项式意义下的小于，也就是 $f(n)$ 渐近小于 $n^{\log_b a}$，即相差一个因子 $n^\varepsilon$，其中 $\varepsilon$ 是一个大于 $0$ 的常数。第三种情况同理，但多了一个“正则”的条件。
$T(n) = \Theta (n^{\log_b}\log^{k + 1} n) \text{ If }f(n) = \Theta(n^{\log_b a} \log^k n),k \ge 1$
主定理并不能覆盖所有的情况，但是可以通过递归树的方式求解。