主定理学习笔记
xiaoniu142857
·
·
算法·理论
主定理（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))
-
-
\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))
-
性质 2~6 同样适用于 \mathcal{O} 和 \mathcal{\Omega}。
这些性质会在后面的证明中用到。
主定理简化版
设 T\left(n\right) 为分治算法处理规模为 n 的问题的复杂度，且满足：
T\left(n\right)=
\begin{cases}
aT\left(\frac{n}{b}\right)+\mathcal{\Theta}\left(n^d\right) & \text{if}\;n\ge b\\
\mathcal{\Theta}\left(1\right) & \text{if}\;n<b
\end{cases}
其中：
则有：
T\left(n\right)=\begin{cases}
\mathcal{\Theta}\left(n^{\log_b a}\right) & \text{if} \; d<\log_b a \\
\mathcal{\Theta}\left(n^d \log n\right) & \text{if} \; d=\log_b a \\
\mathcal{\Theta}\left(n^d\right) & \text{if} \; d>\log_b a
\end{cases}
\mathcal{\Theta}$ 也可以替换成
\mathcal{O,\Omega}$。
这对于 OI 来说已经够用了。
例子
- 对于归并排序，a=2,b=2,d=1，有 d=\log_ba，因此时间复杂度为 \Theta(n\log n)。
- 对于 a=2,b=2,d=2 的完全二叉树上背包问题，有 d>\log_ba，因此时间复杂度为 \Theta(n^2)。
证明
不失一般性地，假设 n 是 b 的整数次幂。
考虑递归树。若根节点算一层，则树高为 \log_b n+1。单独计算叶子节点，展开得：
\begin{aligned}
T\left(n\right)&=\mathcal{\Theta}\left(a^{\log_bn}\right)+\sum_{k=0}^{\log_b n-1}a^k\cdot \mathcal{\Theta}\left(\left(\frac{n}{b^k}\right)^d\right)\\
&=\mathcal{\Theta}\left(a^{\log_bn}\right)+\sum_{k=0}^{\log_b n-1}\mathcal{\Theta}\left(a^k\right)\cdot \mathcal{\Theta}\left(\left(\frac{n}{b^k}\right)^d\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\sum_{k=0}^{\log_b n-1}\mathcal{\Theta}\left(a^k\cdot \frac{n^d}{\left(b^d\right)^k}\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\sum_{k=0}^{\log_b n-1}\mathcal{\Theta}\left(\left(\frac{a}{b^d}\right)^k\cdot n^d\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(\sum_{k=0}^{\log_b n-1}\left(\frac{a}{b^d}\right)^k\cdot n^d\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\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<\log_ba \\
p=1 & \text{if} \; d=\log_ba \\
0<p<1 & \text{if} \; d>\log_ba \\
\end{cases}
且
T\left(n\right)=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot\sum_{k=0}^{\log_b n-1}p^k\right)
情况 1（d<\log_ba）
此时 p>1。
由等比数列求和公式，得：
\begin{aligned}
T\left(n\right)&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \frac{p^{\log_bn}-1}{p-1}\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \left(p^{\log_bn}-1\right)\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \left(\left(\frac{a}{b^d}\right)^{\log_bn}-1\right)\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \left(\frac{a^{\log_bn}}{b^{d\log_bn}}-1\right)\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot\left(\frac{n^{\log_b a}}{n^d}-1\right)\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^{\log_b a}-n^d\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)
\end{aligned}
情况 2（d=\log_ba）
此时 p=1。
\begin{aligned}
T\left(n\right)&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \log_bn\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\log n\right)\\
&=\mathcal{\Theta}\left(n^d\log n\right)
\end{aligned}
情况 3（d>\log_ba）
此时 0<p<1。
由等比数列求和公式，得：
\begin{aligned}
T\left(n\right)&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \frac{p^{\log_bn}-1}{p-1}\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\cdot \frac{1-p^{\log_bn}}{1-p}\right)\\
&=\mathcal{\Theta}\left(n^{\log_ba}\right)+\mathcal{\Theta}\left(n^d\right)\cdot \mathcal{\Theta}\left(1\right)\\
&=\mathcal{\Theta}\left(n^d\right)
\end{aligned}
注意 p-1<0，故应将分母化为 1-p。
对于 \mathcal{O,\Omega}，证明同理。
证毕。
主定理完整版
$$
T(n)=aT\left(\frac{n}{b}\right)+f(n)\quad\left(n\ge b\right)
$$
则有：
$$
T(n)=\begin{cases}
\Theta(n^{\log_b a}) & \text{if}\;f(n)=O(n^{\log_b a-\epsilon})\\
\Theta(f(n)) & \text{if}\;f(n)=\Omega(n^{\log_b a+\epsilon})\\
\Theta(n^{\log_b a}\log^{k+1}n) & \text{if}\;f(n)=\Theta(n^{\log_b a}\log^k n)
\end{cases}
$$
其中 $\epsilon>0,k\ge 0$。
注意其中第二条还必须满足正则条件（Regularity Condition），即存在正常数 $c<1,n_0$ 使得 $\forall n\ge n_0$ 都有 $a f\left(\frac{n}{b}\right) \le c f(n)$。
证明比较繁琐，这里不作展开。思路大致就是代入关于 $f(n)$ 的渐进符号然后化简。
Update 2026.2.1：优化几处格式。