主定理学习笔记

主定理（Master Theorem）是用于分析分治算法复杂度的重要定理。
前置知识

渐进符号的概念

1. \(\mathcal{\Theta}\)（紧确渐进界）

若存在正常数 \(c_1,c_2,n_0\) 使得 \(\forall n\ge n_0\) 都有：

\[0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)\]
则记 \(f(n)=\mathcal{\Theta}(g(n))\)。\(\mathcal{\Theta}\) 是等价关系，表示 \(f,g\) 增长速度同阶，类似 \(=\)。
2. \(\mathcal{O}\)（渐进上界）

若存在正常数 \(c,n_0\) 使得 \(\forall n\ge n_0\) 都有：

\[0\le f(n)\le c\cdot g(n)\]
则记 \(f(n)=\mathcal{O}(g(n))\)。\(\mathcal{O}\) 是拟序关系，类似 \(\le\)（小于等于）。
3. \(\mathcal{\Omega}\)（渐进下界）

若存在正常数 \(c,n_0\) 使得 \(\forall n\ge n_0\) 都有：

\[0\le c\cdot g(n)\le f(n)\]
则记 \(f(n)=\mathcal{\Omega}(g(n))\)。\(\mathcal{\Omega}\) 也是拟序关系，类似 \(\ge\)（大于等于）。
三者如下图所示。

常用性质

• \(f(n)=\mathcal{\Theta}(g(n))\Leftrightarrow f(n)=\mathcal{O}(g(n)) \land f(n)=\mathcal{\Omega}(g(n))\)
  
• \(f(n)=\mathcal{\Theta}(f(n))\)
  
• \(c\cdot \mathcal{\Theta}(f(n))=\mathcal{\Theta}(f(n))\)（\(c>0\) 且 \(c\) 与 \(n\) 无关）
  
• \(\mathcal{\Theta}(f(n))+\mathcal{\Theta}(g(n))=\mathcal{\Theta}(f(n)+g(n))=\mathcal{\Theta}(\max(f(n),g(n)))\)
  
• \(\mathcal{\Theta}(f(n))\mathcal{\Theta}(g(n))=\mathcal{\Theta}(f(n)g(n))\)
  
• \(\mathcal{\Theta}(\log_b n)=\mathcal{\Theta}(\log_2 n)\)（\(b>1\)）
  

性质 2~6 同样适用于 \(\mathcal{O}\) 和 \(\mathcal{\Omega}\)。
这些性质会在后面的证明中用到。
主定理简化版

设 \(T\left(n\right)\) 为分治算法处理规模为 \(n\) 的问题的复杂度，且满足：

\[T\left(n\right)=\begin{cases}aT\left(\frac{n}{b}\right)+\mathcal{O}\left(n^d\right) & \text{if}\;n\ge b\\\mathcal{O}\left(1\right) & \text{if}\;n<b\end{cases}\]p/pp其中：/pulli\(a\)：子问题个数（\(a\in \mathbb{Z},a\ge 1\)）。/lili\(\frac{n}{b}\)：每个子问题大小（\(b\in \mathbb{R},b>1\)）。\(\mathcal{O}\left(n^d\right)\)：合并子问题的解得到原问题解的额外复杂度（\(d\ge 0\)）。
</ul>则有：

\[T\left(n\right)=\begin{cases}\mathcal{O}\left(n^{\log_b a}\right) & \text{if} \; d\log_b a\end{cases}\]
这对于 OI 来说已经够用了。
例子

• 对于归并排序，\(a=2,b=2,d=1\)，有 \(d=\log_ba\)，因此时间复杂度为 \(O(n\log n)\)。
  
• 对于 \(a=2,b=2,d=2\) 的完全二叉树上背包问题，有 \(d>\log_ba\)，因此时间复杂度为 \(O(n^2)\)。
  

证明

不失一般性地，假设 \(n\) 是 \(b\) 的整数次幂。
考虑递归树。若根节点算一层，则树高为 \(\log_b n+1\)。单独计算叶子节点，展开得：

\[\begin{aligned}T\left(n\right)&=\mathcal{O}\left(a^{\log_bn}\right)+\sum_{k=0}^{\log_b n-1}a^k\cdot \mathcal{O}\left(\left(\frac{n}{b^k}\right)^d\right)\\&=\mathcal{O}\left(a^{\log_bn}\right)+\sum_{k=0}^{\log_b n-1}\mathcal{O}\left(a^k\right)\cdot \mathcal{O}\left(\left(\frac{n}{b^k}\right)^d\right)\\&=\mathcal{O}\left(n^{\log_ba}\right)+\sum_{k=0}^{\log_b n-1}\mathcal{O}\left(a^k\cdot \frac{n^d}{\left(b^d\right)^k}\right)\\&=\mathcal{O}\left(n^{\log_ba}\right)+\sum_{k=0}^{\log_b n-1}\mathcal{O}\left(\left(\frac{a}{b^d}\right)^k\cdot n^d\right)\\&=\mathcal{O}\left(n^{\log_ba}\right)+\mathcal{O}\left(\sum_{k=0}^{\log_b n-1}\left(\frac{a}{b^d}\right)^k\cdot n^d\right)\\&=\mathcal{O}\left(n^{\log_ba}\right)+\mathcal{O}\left(n^d\cdot\sum_{k=0}^{\log_b n-1}\left(\frac{a}{b^d}\right)^k\right)\\\end{aligned}\]
设 \(p=\frac{a}{b^d}\)，则：

\[\begin{cases}p>1 & \text{if} \; d