主定理法的证明

主定理（Master Theorem）是一种用于求解递归关系的工具，特别适用于形式为 \(T(n) = aT\left(\frac{n}{b}\right) + f(n)\) 的递归关系。主定理提供了一种方法，通过比较递归部分和非递归部分的增长率，来推断递归关系的渐近解。

主定理的陈述

设 \(T(n)\) 是由以下递归关系定义的函数：
\[ T(n) = aT\left(\frac{n}{b}\right) + f(n) \]
其中 \(a \geq 1\) 且 \(b > 1\) 是常数，\(f(n)\) 是一个给定的函数。那么，\(T(n)\) 的渐近行为可以由以下三种情况之一来描述：

1. 如果存在常数 \(\epsilon > 0\) 使得 \(f(n) = O(n^{\log_b a - \epsilon})\)，则 \(T(n) = \Theta(n^{\log_b a})\)。
2. 如果 \(f(n) = \Theta(n^{\log_b a})\)，则 \(T(n) = \Theta(n^{\log_b a} \log n)\)。
3. 如果存在常数 \(\epsilon > 0\) 使得 \(f(n) = \Omega(n^{\log_b a + \epsilon})\)，且对于某个常数 \(c < 1\) 和所有足够大的 \(n\)，满足 \(af\left(\frac{n}{b}\right) \leq cf(n)\)，则 \(T(n) = \Theta(f(n))\)。

主定理的证明

主定理的证明涉及对递归关系的逐层展开，并通过比较递归部分和非递归部分的增长率，来推断出递归关系的渐近解。以下是三种情况的证明思路：

情况1： \(f(n) = O(n^{\log_b a - \epsilon})\)

我们通过多次展开递归关系来证明：

\[ T(n) = aT\left(\frac{n}{b}\right) + f(n) \]

将 \(T\left(\frac{n}{b}\right)\) 继续展开：

\[ T\left(\frac{n}{b}\right) = aT\left(\frac{n}{b^2}\right) + f\left(\frac{n}{b}\right) \]

将其代入：

\[ T(n) = a \left(aT\left(\frac{n}{b^2}\right) + f\left(\frac{n}{b}\right)\right) + f(n) \]
\[ T(n) = a^2T\left(\frac{n}{b^2}\right) + af\left(\frac{n}{b}\right) + f(n) \]

继续展开 \(k\) 次：

\[ T(n) = a^kT\left(\frac{n}{b^k}\right) + \sum_{i=0}^{k-1} a^i f\left(\frac{n}{b^i}\right) \]

最终，当 \(k = \log_b n\) 时，\(\frac{n}{b^k} = 1\)，此时 \(T(1)\) 为常数：

\[ T(n) = a^{\logb n} T(1) + \sum{i=0}^{\log_b n - 1} a^i f\left(\frac{n}{b^i}\right) \]

因为 \(a^{\log_b n} = n^{\log_b a}\)：

\[ T(n) = n^{\logb a} T(1) + \sum{i=0}^{\log_b n - 1} a^i f\left(\frac{n}{b^i}\right) \]

由于 \(f(n) = O(n^{\logb a - \epsilon})\)，\(\sum{i=0}^{\logb n - 1} a^i f\left(\frac{n}{b^i}\right) = O(n^{\log_b a - \epsilon}) \times \sum{i=0}^{\log_b n - 1} (a/b^i) = O(n^{\log_b a - \epsilon})\)。

因此，\(\sum_{i=0}^{\log_b n - 1} a^i f\left(\frac{n}{b^i}\right) \leq n^{\log_b a}\)。

综上，\(T(n) = \Theta(n^{\log_b a})\)。

情况2： \(f(n) = \Theta(n^{\log_b a})\)

类似地，通过展开递归关系，我们可以得到：

\[ T(n) = a^kT\left(\frac{n}{b^k}\right) + \sum_{i=0}^{k-1} a^i f\left(\frac{n}{b^i}\right) \]

当 \(k = \log_b n\) 时：

\[ T(n) = n^{\logb a} T(1) + \sum{i=0}^{\logb n - 1} a^i \Theta\left(\left(\frac{n}{b^i}\right)^{\log_b a}\right) \]
\[ T(n) = n^{\log_b a} T(1) + \sum{i=0}^{\log_b n - 1} n^{\log_b a} \]

由于有 \(\log_b n\) 个项：

\[ T(n) = n^{\log_b a} \log n \]

因此，\(T(n) = \Theta(n^{\log_b a} \log n)\)。

情况3： \(f(n) = \Omega(n^{\log_b a + \epsilon})\)

在这种情况下，假设 \(f(n) = \Omega(n^{\log_b a + \epsilon})\)，且对于某个常数 \(c < 1\) 和所有足够大的 \(n\)，满足 \(af\left(\frac{n}{b}\right) \leq cf(n)\)。

展开递归关系：

\[ T(n) = a^kT\left(\frac{n}{b^k}\right) + \sum_{i=0}^{k-1} a^i f\left(\frac{n}{b^i}\right) \]

由于 \(af\left(\frac{n}{b}\right) \leq cf(n)\)，递归展开后：

\[ T(n) \leq f(n) \sum_{i=0}^{k-1} a^i c^i \]

当 \(k \rightarrow \infty\) 时，\(\sum_{i=0}^{\infty} (ac)^i = \frac{1}{1 - ac}\)：

\[ T(n) = \Theta(f(n)) \]

综上，证明了主定理的三种情况。通过主定理，可以快速求解许多常见递归关系的时间复杂度。