[ALDE 0x05] 主方法

通常来讲，如果要去计算一个递归算法的复杂度，我们只能依靠递归树展开、代数方法、归纳证明，但这些方法都不方便，局限性很大。大多数的递归算法，其时间复杂度都可以写成以下形式：

$$T(n) = aT(n/b) + f(n) \quad (a \neq 0, b \neq 0)$$

其中，$a$ 是划分出的子问题的数量，$n/b$ 是每个子问题的规模，$f(n)$ 是分割子问题与合并子问题的开销，$T(n)$ 是我们要求解的目标，它是一个递归算法的真正时间复杂度，但我们不知道，因为它同时出现在了等式左右两边。

主方法（Master Method），或者说主定理，给出了求解这种形式的递归式的通用方法。下面是主方法的内容：

对于一个递归式 $T(n) = aT(n/b) + f(n)$，比较 $f(n)$ 和 $n^{\log_b a}$ 的大小：

1. 情况 1: 如果 $f(n) = O(n^{\log_b a - \epsilon})$ 对某些 $\epsilon > 0$ 成立, 那么 $T(n) = \Theta(n^{\log_b a})$。
2. 情况 2: 如果 $f(n) = \Theta(n^{\log_b a}\log^{k}a)$, 那么 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。
3. 情况 3: 如果 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 对某些 $\epsilon > 0$ 成立，并且 $af(n/b) \le cf(n)$ 对某些常数 $c < 1$ 成立，那么，$T(n) = \Theta(f(n))$。

本文档为了方便大家记忆主方法的公式，会以一种简单笼统的方式概述主方法的前因后果。毕竟，应用主方法不是什么难事，难的主要是记公式。不过由于比较笼统，部分概念的解释仅停留在直觉层面，要严谨的表述请移步。

递归树上的叶节点

下图展示了一棵递归树，$f(n)$ 是问题的初始规模，每一层，它将原问题拆解为 $a$ 个子问题，并且每次拆解，问题规模都会缩小 $b$ 倍，直到问题的规模不可再分为止，此时就来到了叶节点。

递归树肯定是一棵满 $a$ 叉树，除了最后一层叶节点，其他每一层的节点都代表一次问题的划分/合并。根据满多叉树的性质，对于第 $k$ 层，它将存在 $a^{k}$ 个节点，即划分出 $a^{k}$ 个子问题，每个问题的规模为 $n/b^{k}$。

叶节点是问题划分的终点，到这一层，问题不可再分，也就是说问题规模来到了常数级，我们令其为 $1$，则有：

$$\frac{n}{b^{k}}=1 \Rightarrow k = \log_{b} n$$

这说明递归树一共有 $\log_{b} n$ 层。再根据我们之前得出的结论，叶节点的数量为 $a^{\log_{b}n}$，应用对数恒等式，有 $a^{\log_{b}n} = n^{\log_{b}a}$（这里把底数换成 $n$ 是为了方便比较其与 $f(n)$ 的大小）。这就是主方法中 $n^{\log_{b}a}$ 的由来，它其实代表的就是叶节点的数量，也就是最终划分出的最小规模的子问题的数量，至于它的用处，我们继续往下看。

三种情况

主方法中，根据 $f(n)$ 和 $n^{\log_{b}a}$ 的大小关系，一共分为了三种情况，每种情况的具体含义为：

1. 叶节点占主导，时间开销的大头都在叶节点上。
2. 时间开销均匀分布在树的各个节点上。
3. 根节点占主导，时间开销的大头都在根节点上。

我们依次分析三种情况。

情况一：叶节点占主导

叶节点意味着，解决子问题（叶节点的活）比分割/合并子问题（中间节点的活）要累得多。

根据我们的定义，递归式中的 $f(n)$ 代表分割/合并子问题的时间复杂度；$n^{\log_{b}a}$ 代表子问题的个数，由于单个子问题的时间复杂度基本上为 $O(1)$，所以可以直接用 $n^{\log_{b}a}$ 代表子问题的时间复杂度。

那么要满足叶节点占主导的情况，自然就要有 $f(n)$ 的量级远小于 $n^{\log_{b}{a}}$，也就是 $f(n) = O(n^{\log_b a - \epsilon})$。你可能会问：$\epsilon$ 是哪冒出来的？其实很好理解，$O$ 代表的是上界，如果 $f(n)=O(g(n))$，它仅保证 $f(n)$ 增长得不会比 $g(n)$，那就有可能出现同阶的情况。而同阶在我们这个语境下的意思就是，中间节点干的活和叶节点干的活一样多，这样就引出了情况二。但是如果是 $f(n) = O(n^{\log_b a - \epsilon})$，由于 $n^{\log_{b}a} \gt n^{\log_{b}a-\epsilon}$，因此不会出现同阶，而是严格小于。

那么既然叶节点干活最多，那么整个递归式的时间复杂度肯定就全都压在这 $O(n^{\log_{b}a})$ 上了，自然就有 $T(n)=\Theta(n^{\log_{b}a})$。

情况三：根节点占主导

既然情况一是叶节点占主导，即最小子问题的处理开销最大，那么情况三的根节点占主导其实就是反一下，即子问题的处理开销很小，而根节点的开销很大。根节点干的活主要是把原始问题（规模为 $n$）分割成 $a$ 个子问题，以及合并所有子问题返回的结果，这部分开销用 $f(n)$ 表示。如果 $f(n)$ 特别大，那么自然整个递归式的时间复杂度最终就会趋近于 $f(n)$，所以自然有 $T(n)=\Theta(f(n))$。

但是注意，$f(n)$ 本身会参与递归，如果把递归式展开，后续会出现 $f(n/b),f(n/b^{2}),\dots,f(n/b^{k})$，这些部分加在一起，有反超 $f(n)$ 的风险，所以加了一个条件 $af(n/b) \le cf(n),c \lt 1$ 来限制递归结构的增长。

情况二：均匀分布

上面我们已经引出了情况二了，那就是时间开销被各部分平摊，不论是叶节点还是中间节点，都有同阶的复杂度，也就是情况二的条件提到的 $f(n) = \Theta(n^{\log_b a}\log^{k}n)$。为什么这里会出现一个 $\log^{k}n$？因为即使多乘上一个对数的幂，两者也仍然同阶，乘上一个对数对其增长速度没有什么太大影响。之所以要加上它，是因为 $f(n)$ 中可能出现它，为了保持形式统一，于是在 $n^{\log_{b}a}$ 后面乘上一个 $\log^{k}n$，如果 $f(n)$ 中不存在这个对数，那么 $k=0$。

情况二非常好讨论，既然都一样，那么把每层的开销都加起来不就好了。注意 $f(n)$ 代表的是一层的中间节点的开销，而 $n^{\log_{b}a}$ 是所有根节点的开销，现在两者同阶，那么总的开销就是：

$$T(n) \sim \sum_{i=0}^{\log_{b}n} n^{\log_{b}a} \log^{k} (n/b^{i})$$

这是一个累加求和，根据求和公式，最后需要多乘一项，这会导致升幂 $k \to k+1$，所以就有 $T(n) = \Theta(n^{\log_b a} \log ^{k+1}n)$。

应用题

$A.$ 应用主方法求 $T(n)=8T(n/2)+n^{3}$ 的渐进估计。

在此式中，$a=8$，$b=2$，$f(n)=n^{3}$。将 $f(n)$ 与 $n^{\log_{b}a}=n^{3}$ 进行比较，发现存在 $f(n)=\Theta(n^{3}\log^{k}n)$，其中 $k=0$，属于情况二。根据主方法，有 $T(n)=\Theta(n^{3}\log n)$。

---

$B.$ 应用主方法求 $T(n)=5T(n/3)+n(\lg n)^{3}$ 的渐进估计。

在此式中，$a=5$，$b=3$，$f(n)=n(\lg n)^{3}$。将 $f(n)$ 与 $n^{\log_{b}a}=n^{\log_{3}5}$ 进行比较，发现存在 $\epsilon \gt 0$，使得 $f(n)=O(n^{\log_{3}5-\epsilon})$ 成立，属于情况一。根据主方法，有 $T(n)=\Theta(n^{\log_{3}5})$。

---

$C.$ 应用主方法求 $T(n)=7T(n/2)+n^{2}$ 的渐进估计。

在此式中，$a=7$，$b=2$，$f(n)=n^{2}$。将 $f(n)$ 与 $n^{\log_{b}a}=n^{\log_{2}7}$ 进行比较，发现存在 $\epsilon \gt 0$，使得 $f(n)=O(n^{\log_{2}7-\epsilon})$ 成立，属于情况一。根据主方法，有 $T(n)=\Theta(n^{\log_{2}7})$。

---

$D.$ 应用主方法求 $T(n)=7T(n/3)+n^{2}$ 的渐进估计。

在此式中，$a=7$，$b=3$，$f(n)=n^{2}$。将 $f(n)$ 与 $n^{\log_{b}a}=n^{\log_{3}7}$ 进行比较，发现存在 $\epsilon \gt 0$，使得 $f(n)=\Omega(n^{\log_{3}7+\epsilon})$ 成立，并且还存在 $c \lt 1$，使得 $7f(n/3) \le c f(n)$ 成立，属于情况三。根据主方法，有 $T(n)=\Theta(n^{2})$。