浅谈扩展主定理（Extended Master Theorem）
LG_jyc
·
·
算法·理论
一些约定
T(n)=aT(\dfrac{n}{b})+f(n),T(1)=O(1),\epsilon>0
主定理
这里就不多说了，形式与证明都可以看这篇文章，里面提到的主定理是这样的（这里面的公式与我们常用的有一点不同，但是严格包含我们常用的主定理）：
T(n)=\begin{cases}
\Theta(n^{\log_ba}) & f(n)=\mathcal{O}(n^{(\log_ba)-\epsilon}) \\
\Theta(f(n)) & f(n)=\Omega(n^{(\log_ba)+\epsilon}) \\
\Theta(n^{\log_ba}\log^{k+1} n) & f(n)=\Theta(n^{\log_ba}\log^kn),k \ge 0
\end{cases}
注意第二条中还应该存在 c<1 满足在 n 足够大时 af(\dfrac{n}{b}) \le cf(n)。
扩展主定理
扩展主定理将主定理中的第三条的 k 的范围从 k \ge 0 扩展到了任意实数，它的形式如下：
T(n)=\begin{cases}
\Theta(n^{\log_ba}) & f(n)=\mathcal{O}(n^{(\log_ba)-\epsilon})\\
\Theta(n^{\log_ba}\log^{k+1} n) & f(n)=\Theta(n^{\log_ba}\log^kn),k>-1\\
\Theta(n^{\log_ba}\log\log n) & f(n)=\Theta(n^{\log_ba}\log^{-1}n)\\
\Theta(n^{\log_ba}) & f(n)=\Theta(n^{\log_ba}\log^kn),k<-1\\
\Theta(f(n)) & f(n)=\Omega(n^{(\log_ba)+\epsilon})
\end{cases}
同理，第五条中还应该存在 c<1 满足在 n 足够大时 af(\dfrac{n}{b}) \le cf(n)。
证明
这一部分不是我想的。
我们只需要证明第二到四条，接下来我们设 m=\log_bn 且公式统一使用小括号。
展开并带入
我们先展开递归树，那么第零层贡献为 f(n)，第 i 层贡献为 a^if(\dfrac{n}{b^i})，而递归树有 a^m=n^{\log_ba} 个叶子，每个叶子代价为 \Theta(1)。
综上 T(n) 可以表示为：
T(n)=\Theta(\sum_{i=0}^{m-1}a^if(\dfrac{n}{b^i}))+\Theta(n^{\log_ba})
当 f(n)=\Theta(n^{\log_ba}\log^kn) 时，就有：
f(\dfrac{n}{b^i})=\Theta((\dfrac{n}{b^i})^{\log_ba}\log^k(\dfrac{n}{b^i}))
又因为：
(\dfrac{n}{b^i})^{\log_ba}=n^{\log_ba} \times b^{-i\log_ba}=n^{\log_ba} \times a^{-i}\\
\log(\dfrac{n}{b^i})=(\log n)-i(\log b)
所以有：
f(\dfrac{n}{b^i})=\Theta(n^{\log_ba}a^{-i}((\log n)-i(\log b))^k)
带入 T(n) 的求和式子得到：
T(n)=\Theta(n^{\log_ba}(\sum_{i=0}^{m-1}a^ia^{-i}((\log n)-i(\log b))^k))+\Theta(n^{\log_ba})=\Theta(n^{\log_ba}(\sum_{i=0}^{m-1}((\log n)-i(\log b))^k))+\Theta(n^{\log_ba})
令 j=m-i，则求和部分变为：
\begin{align*}
& \Theta(\sum_{i=0}^{m-1}((\log n)-i(\log b))^k)\\
& =\Theta(\sum_{j=1}^{m}((\log n)-(m-j)(\log b))^k)\\
& =\Theta(\sum_{j=1}^{m}((\log n)-m(\log b)+j(\log b))^k)\\
& =\Theta(\sum_{j=1}^{m}((\log n)-(\log n)+j(\log b))^k)\\
& =\Theta(\sum_{j=1}^{m}(j\log b)^k)\\
& =\Theta(\log^k b\sum_{j=1}^{m}j^k)
\end{align*}
因此，我们得到：
T(n)=\Theta(n^{\log_ba}\log^k b\sum_{j=1}^{m}j^k)+\Theta(n^{\log_ba})
分析渐进结果
关键在于 \sum_{j=1}^{m}j^k 部分的结果，根据 k 的取值分类讨论。
当 k>-1 时，有以下结果：
\Theta(\sum_{j=1}^{m}j^k)=\Theta(\int_0^mx^k\mathrm{d}x)=\Theta(\dfrac{m^{k+1}}{k+1})=\Theta(m^{k+1})
此时 T(n) 为：
\begin{align*}
&\Theta(n^{\log_ba}\log^k b \cdot m^{k+1})\\
&=\Theta(n^{\log_ba}\log^k b \cdot (\dfrac{\log n}{\log b})^{k+1})\\
&=\Theta(n^{\log_ba}\log^k b \cdot (\dfrac{\log^{k+1} n}{\log^{k+1} b}))\\
&=\Theta(n^{\log_ba} \cdot (\dfrac{\log^{k+1} n}{\log b}))\\
&=\Theta(n^{\log_ba}{\log^{k+1} n})
\end{align*}
当 k=-1 时，求和将变成调和级数的形式：
\Theta(\sum_{j=1}^{m}j^k)=\Theta(\sum_{j=1}^{m}\dfrac{1}{j})=\Theta(\log m)=\Theta(\log \log n)
此时就有：
T(n)=\Theta(n^{\log_ba}\log^{-1} b\log\log n)=\Theta(n^{\log_ba}\log\log n)
当 k<-1 时，求和将会收敛，所以会有：
\Theta(\sum_{j=1}^{m}j^k)=\Theta(1)
因此就会有：
T(n)=\Theta(n^{\log_ba})
综上，我们证明了扩展主定理的所有扩展部分。
使用示例
假设现在 T(n)=2T(\dfrac{n}{2})+\Theta(\dfrac{n}{\log n})。
我们发现这个函数不能使用标准主定理，但是可以使用我们的扩展主定理。
这里 f(n)=n\log^{-1}n，满足扩展主定理的第三条，所以有：
T(n)=\Theta(n^{\log_22}\log\log n)=\Theta(n\log\log n)
至此，我们将主定理的应用范围扩展到了几乎所有 f(n)=n^p\log^qn 的情况。