#主定理

主定理 (Master Theorem) 是算法分析领域中，用于求解分治策略（Divide and Conquer）递归关系式渐近界的最强力工具。它最早在 《算法导论》(Introduction to Algorithms, CLRS) 中被系统化阐述。

#1. 标准递归形式

主定理适用于求解以下形式的递归关系式：

$$T(n) = a T(n/b) + f(n)$$

其中：

• $n$ ：问题的规模。
• $T(n)$ ：解决规模为 $n$ 的问题所需的时间/计算量。
• $a \geq 1$ ：子问题的数量（必须是常数）。或者说是每次递归拆分出的问题的个数。
• $b > 1$ ：子问题规模缩减的因子（必须是常数）。
• $\displaystyle\frac{n}{b}$ ：每个子问题的规模，通常是原问题的 $\displaystyle\frac{1}{b}$
• $f(n)$ ：当前层（递归之外）所做的工作，包括划分问题和合并结果的代价（必须是渐近正函数）。

注 ：严格来说，$T(n/b)$ 可以是 $T(\lfloor n/b \rfloor)$ 或 $T(\lceil n/b \rceil)$，但这不会影响渐近时间复杂度分析的结果。

#2. 递归计算量

递归到底时，也就是到了第 $k$ 层的时候，子问题的个数为 $a^k$ ，每个问题的规模是 $\displaystyle \frac{n}{b^k}$ 。

又由于递归到底时，子问题的规模为 1，所以令 $\displaystyle \frac{n}{b^k}=1$ 得 $k=\log_b n$ 。

子问题的个数，同时也是第 $k$ 层叶子节点的数量：$a^k = a^{\log_b n}$ 。为了方便与额外计算量 $f(n)$ 进行比较，利用对数恒等式将其转化为 $a^k = a^{\log_b n} = n^{\log_b a}$ （ $a^{\log_b n} = b^{\log_b a^{\log_b n}} = b^{\log_b n \cdot \log_b a} = (b^{\log_b n})^{\log_b a}= n^{\log_b a}$ ）

通常，叶子节点的计算量为 $\Theta(1)$ ，所以整个递归树的叶子部分的总计算量为 $\Theta(n^{\log_b a})$ 。

#3. 核心思想：比较 $f(n)$ 与 $n^{\log_b a}$

主定理的核心在于比较两个函数的增长速率：

1. $f(n)$ ：递归树“根节点”的工作量（也代表每一层非递归工作的趋势）。
2. $n^{\log_b a}$ ：递归树“叶子节点”的总数量（或者说叶子层的总工作量）。

我们将 $n^{\log_b a}$ 视为临界函数。根据 $f(n)$ 与该临界函数的大小关系，分为三种情况。

#4. 三种情况 (The Three Cases)

所用概念解释：$f(n)$ 多项式地小于/大于 $g(n)$ 意味着两个函数的差距必须足够大，大到一个 $n^\epsilon$ 的程度

#情况 1：叶子节点占主导 (Heavy Leaves)

如果 $f(n)$ 的增长速率多项式地小于 $n^{\log_b a}$，即存在常数 $\epsilon > 0$，使得：

$$f(n) = O(n^{\log_b a - \epsilon})$$

那么，递归树叶子层的工作量决定了总复杂度：

$$T(n) = \Theta(n^{\log_b a})$$

#情况 2：权重平衡 (Balanced)

如果 $f(n)$ 的增长速率与 $n^{\log_b a}$ 相当（通常只差一个对数因子），即：

$$f(n) = \Theta(n^{\log_b a} \log^k n)$$

其中 $k \ge 0$（最常见的是 $k=0$）。那么，总复杂度为：

$$T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$$

特例：当 $k=0$ 时（即 $f(n) = \Theta(n^{\log_b a})$），$T(n) = \Theta(n^{\log_b a} \log n)$。这也是归并排序的情况。

#情况 3：根节点占主导 (Heavy Root)

如果 $f(n)$ 的增长速率多项式地大于 $n^{\log_b a}$，即存在常数 $\epsilon > 0$，使得：

$$f(n) = \Omega(n^{\log_b a + \epsilon})$$

且 满足 正则性条件 (Regularity Condition) ：存在常数 $c < 1$ 和足够大的 $n$，使得：

$$a f(n/b) \le c f(n)$$

那么，递归树根节点的工作量决定了总复杂度：

$$T(n) = \Theta(f(n))$$

#5 关键细节解析

必须强调以下两点：

1. 多项式差异 (Polynomially Larger/Smaller) ： 在情况 1 和情况 3 中，仅仅“大”或“小”是不够的（例如 $\log n$ 的差异），必须相差一个 $n^\epsilon$ 因子。

   • 错误示例：$n^{\log_b a} = n$，而 $f(n) = n \log n$。虽然 $f(n)$ 更大，但不是多项式地大（$\log n$ 小于任何 $n^\epsilon$）。因此不适用情况 3（也不适用情况 2）。

2. 正则性条件 ： 在情况 3 中，正则性条件通常在 $f(n)$ 是多项式函数时自然成立（如 $n^2, n^3$），不能是分段函数，不能是震荡函数。但在极少数数学构造的函数中可能失效。如果失效，主定理不适用。

#6. 实例分析

#示例 A：$T(n) = 9T(n/3) + n$

• $a=9, b=3, f(n)=n$
• 计算临界指数：$\log_b a = \log_3 9 = 2$
• 临界函数：$n^{\log_b a} = n^2$
• 比较：$f(n) = n^1$。显然 $n^1$ 比 $n^2$ 多项式地小（$\epsilon=1$）。
• 结论 (情况 1) ：$T(n) = \Theta(n^2)$

#示例 B：$T(n) = T(2n/3) + 1$

• $a=1, b=3/2, f(n)=1$
• 计算临界指数：$\log_{3/2} 1 = 0$
• 临界函数：$n^0 = 1$
• 比较：$f(n) = 1 = \Theta(n^0)$。两者相等。
• 结论 (情况 2, k=0) ：$T(n) = \Theta(n^0 \log n) = \Theta(\log n)$

#示例 C：$T(n) = 3T(n/4) + n \log n$

• $a=3, b=4, f(n) = n \log n$
• 计算临界指数：$\log_4 3 \approx 0.792$
• 临界函数：$n^{0.792}$
• 比较：$f(n) = n^1 \log n$。由于 $1 > 0.792$，且 $n \log n$ 比 $n^{0.792}$ 多项式地大（$\epsilon \approx 0.2$）。
• 检查正则性条件：$3(n/4 \log(n/4)) \le c(n \log n)$，即 $0.75 n \log n \le c n \log n$，取 $c=0.75$ 成立。
• 结论 (情况 3) ：$T(n) = \Theta(n \log n)$

#7. 主定理失效的场景 (Gaps)

主定理并未覆盖所有可能的情况。以下情况不能使用主定理：

1. 非多项式差异 ： $f(n)$ 处于 $n^{\log_b a}$ 和 $n^{\log_b a \pm \epsilon}$ 之间。 例如：$T(n) = 2T(n/2) + n \log n$。 这里 $\log_b a = 1$，临界函数是 $n$。$f(n) = n \log n$ 比 $n$ 大，但并非多项式地大（只差 $\log n$）。这落入了情况 2 和情况 3 的缝隙中。 注：对于这种特定情况，可以使用扩展主定理求解，结果为 $O(n \log^2 n)$。

2. 正则性条件不满足 ： $f(n)$ 虽然很大，但不是单调递增或波动剧烈（如涉及 $\sin n$ 等函数）。

3. $a$ 或 $b$ 不是常数 ： 例如 $T(n) = T(n-1) + n$ 或 $T(n) = \sqrt{n} T(\sqrt{n}) + n$。