代入法 / Substitution method#

代入法 (Substitution method) 是使用数学归纳法去猜测递归式边界，并通过推导去证明。它的基本思路是：

1. 使用常数符号去猜测递归式 $T(n)$。
2. 使用数学归纳法求出解中的常数，并证明解的正确。

递归树法 / Recursion-tree method#

使用代入法正确猜测递归式的边界可能比较困难，但是递归树方法 (Recursion-tree method) 却可以解决这个问题。对于递归式求解问题，我们大多数都可以使用递归树方法计算做出猜测，最后使用代入法去验证。

在递归树中，每个结点表示一个单一子问题的代价（需要时间），子问题对应某次递归函数的调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次递归调用的总代价。

递归树方法 (Recursion-tree method) 的基本思路是：

1. 构建递归树: 将递归式转换成递归树。
2. 计算递归树中代价：计算递归树中每层的代价、树的高度。
3. 代价求和：将每层的代价求和，得到所有层代价的总和，即为递归函数的总运行时间。

我们通过一个例子来演示递归树法的过程：

$T(n) = 3T(n/4) + \Theta(n^2)$.

我们用 $cn^2$ 表示递归式中的 $\Theta(n^2)$，$c$ 为一个正的常数。我们可以使用 $T(n) = 3T(n/4) + cn^2$ 去构建递归树。

1. 构建递归树：根节点中的 $cn^2$ 表示递归调用顶层的代价，根的三个子树表示规模为 $n/4$ 的子问题所产生的代价。

因为我们递归有3个，故从 $T(n)$处可以分成三个分支：

$T(n/4)$ 又可以通过 $T(n) = 3T(n/4) + cn^2$得到，$T(n/4) = 3T(n/16) + cn^2$。故每个 $T(n/4)$ 又可以有三个分支：

同理我们可以继续分 $T(n/16)$，直到最后抵达不可递归的条件，此时递归树为：

2. 递归树中代价的计算：

观察递归树，我们可以计算每层 (用深度来表示以匹配指数, 根结点的深度为 0) 的代价:

• 第1层的代价：$c(n/4)^2 \times 3 = 3c(n/4)^2 = (3/4^2)\ cn^2$
• 第2层的代价：$c(n/16)^2 \times 9 = 9c(n/16)^2 = (3/4^2)^2\ cn^2$
• 第3层的代价：$c(n/64)^2 \times 27 = 27c(n/64)^2 = (3/4^2)^3\ cn^2$

可以推广到第i层的代价：$c(n/4^i)^2 \times 3^i = (3/4^2)^i\ cn^2$

这样的规律可以一直推广到第 h - 1 层，h 为递归树的总深度。而最后一层的代价则可以通过 最后一层的节点数量 $\times\ \Theta(1)$ 来计算。

接下来我们可以通过递归树中节点的规模来计算递归树的深度 $h$。

观察递归树可以知道，每个子结点规模为父结点的 $1/4$，那么可以推算子节点的规模：

• 第1层的子结点规模为 $(n/4)^2 = (n/4^1)^2$,
• 第2层的子结点规模为 $(n/16)^2 = (n/4^2)^2$
• 第3层的子结点规模为 $(n/64)^2 = (n/4^3)^2$

可以推广到第i层的子结点规模：$(n/4^i)^2$. 在最后一层，子节点不需要继续递归了，此时规模为 $1$.

于是，在最后一层拥有的子节点规模：

我们得到递归树的深度 $h = \log_4 n$。

有了深度的表达式后，可以得出第0层到第h - 1层的代价表达式。要计算总代价，我们还需要最后一层的节点数量才能计算最后一层的代价。

观察递归树每层的节点数量，可以发现：

• 第0层的节点数量：$1 = 3^0$
• 第1层的节点数量：$3 = 3^1$
• 第2层的节点数量：$9 = 3^2$
• 第3层的节点数量：$27 = 3^3$

在第 i 层，节点数量为 $3^i$。那么最后一层的节点数量为 $3^{h} = 3^{\log_4 n}$。

所以最后一层的代价为：$3^{\log_4 n} \times \Theta(1)$，于是我们可以计算总代价。

3. 代价求和：

我们可以发现，在第0层到第h - 1层，代价是一个等比数列：

• 第0层的代价：$(3/4^2)^0\ cn^2 = cn^2$
• 第1层的代价：$(3/4^2)^1\ cn^2$
• 第2层的代价：$(3/4^2)^2\ cn^2$
• 第3层的代价：$(3/4^2)^3\ cn^2$
• 第i层的代价: $(3/4^2)^i\ cn^2$
• 第h - 1层的代价: $(3/4^2)^{\log_4 n - 1} \ cn^2$

而最后一层代价根据换底公式：$3^{\log_4 n} \times \Theta(1) = n^{\log_4 3} \times \Theta(1) = \Theta(n^{\log_4 3})$

总代价为：

到这一步，我们已经成功使用参数去表示这个递归式。接下来的解需要使用微积分的知识，使用一个无穷范围以消除指数。

我们在实际情况中，可能还会遇到递归树节点参差不齐的情况，例如:

$T(n) = T(n/3) + T(2n/3) + n$.

这种情况下的递归树子节点的代价不一样，因为其节点的规模一个为父节点的 $1/3$, 一个是父节点的 $2/3$。我们按照之前的步骤，可以画出如下的递归树：

我们可以分别计算最浅节点和最深节点的深度：

• 节点规模为 $1/3$ 的节点的深度 $h_1$: $(\frac{1}{3})^{h_1}\ n = 1 \implies h_1 = \log_3 n$
• 节点规模为 $2/3$ 的节点的深度 $h_2$: $(\frac{2}{3})^{h_2}\ n = 1 \implies h_2 = \log_{\frac{3}{2}} n$

因为 $h_2 > h_1$，故规模为 $2/3$ 的节点的深度更深，图会往右下展开。

在计算每层代价的时候，我们可以发现，它应该是一个分段的函数：

• 当深度 $d \le h_1$ 时，代价为 $cn$.
• 当深度 $h_1 \lt d \le h_2$ 时，代价 $< cn$.

但是我们还是没法确定每层代价的表达式，只能估计一个模糊的边界。于是，我们假设两个在深度为 $h_1$ 和 $h_2$ 的满二叉树去估计该递归式的下界和上界。

1. 当一颗满二叉树的深度为 $h_1$ 时，最后一层节点全是 $\Theta(1)$。它是下界的理想情况。

   它最后一层的节点数量为 $2^{h_1} = 2^{\log_3 n}$，此时最后一层的代价为: $2^{\log_3 n} \times \Theta(1) = n^{\log_3 2} \times \Theta(1) = \Theta(n^{\log_3 2})$

   于是该满二叉树的总代价为：

   $$\begin{align*} &cn \times (\log_3 n - 1) + \Theta(n^{\log_3 2}) \\ &= cn\log_3 n + \Theta(n^{\log_3 2}) - cn \\ &= \Omega(n\log n) \end{align*}$$

2. 当一颗满二叉树的深度为 $h_2$ 时，最后一层节点数量为 $2^{h_2} = 2^{\log_{\frac{3}{2}} n}$，此时最后一层的代价为: $2^{\log_{\frac{3}{2}} n} \times \Theta(1) = n^{\log_{\frac{3}{2}}2} \times \Theta(1) = \Theta(n^{\log_{\frac{3}{2}}2})$

   于是该满二叉树的总代价为：

   $$\begin{align*} &cn \times (\log_{\frac{3}{2}} n - 1) + \Theta(n^{\log_{\frac{3}{2}}2}) \\ &= cn\log_{\frac{3}{2}} n + \Theta(n^{\log_{\frac{3}{2}}2}) - cn \\ &= O(n\log n) \end{align*}$$

所以综合起来，我们可以猜测递归式的解为：$T(n) = \Theta(n\log n)$

因为是一个粗略的边界，我们需要使用代入进行验证。即证明：$T(n)\le dn\ lgn$，$d>0$ 是个正的常数。用 $cn$ 代替 $\Theta(n)$，上界为：

同理，可以验证其下界，最后得到递归式解为：$T(n) = \Theta(n\log n)$

主方法 / Master method#

主方法主要来自于递归树法的总结，适用于求解下面格式的递归式：$T(n) = aT(n/b) + f(n)$，$a>0,\ b>1$.

$f(n)$ 称为 驱动函数（driving function），它是一个渐进非负函数。它是基础情况下的代价。

这个通式我们可以得到以下信息：

• 子问题数量: $a$
• 子问题规模: $1/b$
• 递归树的深度: $\frac{n}{b^h} = 1 \implies h = \log_b n$
• 递归树深度第i层的结点个数: $a^i$
• 递归树最后一层的结点个数: $a^h = a^{\log_b n} = n^{\log_b a}$

若最后一层结点都是 $\Theta(1)$，则递归树最后一层的代价为:

而其他层结点的代价为:

那么最终的代价可以表示为：

对于这样的递归式，它的边界由 $C_h$ 和 $C_{\text{other}}$ 中 $n$ 的 指数大 的那个决定。于是我们可以进行分类讨论，即主方法的定义:

Definition

Case 1: ($f(n) < n^{\log_b a}$) 若存在一个常数 $\epsilon > 0$ 使得 $f(n) = O(n^{\log_b a-\epsilon})$，则递归式的解为 $T(n) = Θ(n^{\log_b a})$。这种情况下代价主要来源于 叶子节点。

Case 2: ($f(n) \approx n^{\log_b a}$) 若存在一个常数 $k \ge 0$ 使得 $f(n) = \Theta(n^{\log_b a }\lg^k n)$，则递归式的解为 $T(n) = \Theta(n^{\log_b a }\lg^{k+1} n)$。这种情况下每一层的代价基本相等为 $\Theta(n^{\log_b a} \lg^k n)$，而其高度可以表示为 $\Theta(\lg n)$。

Case 3: ($f(n) > n^{\log_b a}$) 若存在一个常数 $\epsilon > 0$ 使得 $f(n) = \Omega(n^{\log_b a+\epsilon})$，且 $f(n)$ 在 $n$ 足够大时满足条件 $af(n/b) ≤ cf(n), c \lt 1$ 时，递归式的解为 $T(n) = \Theta(f(n))$。这种情况与情况一正好相反，代价主要来源于 根节点。

下面三个例题分别是对应了三种不同情况下的主方法的应用：

$T(n) = 2T(n/4) + 1$

分析可知：$f(n) = 1$， $n^{\log_b a} = n^{\log_4 2} = n^{1/2}$。很明显，$f(n) < n^{\log_b a}$，可以使用主方法中的情况1，得到 $T(n) = Θ(n^{1/2})$

$T(n) = 2T(n/4) + \sqrt{n}\lg^2 n$

分析可知：$f(n) = \sqrt{n}\lg^2 n$， $n^{\log_b a} = n^{\log_4 2} = n^{1/2}$。此时在增长率上，$f(n) = Θ(n^{1/2} \lg^2 n) = Θ(n^{\log_b a} \lg^2 n)$，它们增长率相当，适用于情况2，得到 $T(n) = Θ(n^{1/2} \lg^3 n)$。

$T(n) = 2T(n/4) + n^2$

分析可知：$f(n) = n^2$， $n^{\log_b a} = n^{\log_4 2} = n^{1/2}$。很明显，$f(n) > n^{\log_b a}$，且此时满足 $2f(n/4) = (1/8)n^2 ≤ cf(n)$，此时 $0<c<1$ 。可以使用主方法中的情况3，得到 $T(n) = Θ(n^2)$。

但是主方法并不能覆盖所有的递归式，它会出现空隙无法使用。

1. 当 $f(n)$ 与 $n^{\log_b a}$ 两个函数无法比较时。
2. 当 $f(n) = o(n^{\log_b a})$时，情况一和情况二之间会有一个间隙，$n^{\log_b a}$ 多项式的增长速率不大于 $f(n)$ 的多项式的增长速率。
3. 当 $f(n) = ω(n^{\log_b a})$ 时，情况二和情况三之间会有一个间隙，$n^{\log_b a}$ 多项式的增长速率不小于 $f(n)$ 的多项式的增长速率。

解决这类递归式可以尝试使用其他方法，或Akra-Bazzi 递归式，这里不在正文处涉及。

Exercises in Divide-and-Conquer#

下面我们通过一些练习，去加深对解递归式的三种方法的理解。

证明：$T(n) = T(n - 2) + n^2$ 的解为 $T(n) = \Theta(n^3)$

因为题目要求我们证明的是 $\Theta$，故需要分上下界进行讨论。

• 对于上界：

我们可以设存在常数 $c > 0$ 和 $n_0$, 对于所有 $n \ge n_0$，都有 $T(n) \le cn^3$.

假设对于所有的 $k < n$, $T(k) \le ck^3$ 成立，所以 $T(n - 2) \le c(n - 2)^3$

代入原递归式得到：

为了使这个不等式在 $n \ge n_0$, $n_0$ 足够大时成立，这个二次函数的开口需要向下，即：$1- 6c \lt 0 \implies c > \frac{1}{6}$

因此在 $c > \frac{1}{6}$ 时，$T(n) = O(n^3)$

• 对于下界：这一部分与上界基本一致。

设存在常数 $d > 0$ 和 $n_0$, 对于所有 $n \ge n_0$，都有 $T(n) \ge dn^3$.

假设对于所有的 $k < n$, $T(k) \ge dk^3$ 成立，所以 $T(n - 2) \ge d(n - 2)^3$

代入原递归式得到：

为了使这个不等式在 $n \ge n_0$, $n_0$ 足够大时成立，这个二次函数的开口需要向上或为一次函数，即：$1- 6d \ge 0 \implies 0 \lt d \le \frac{1}{6}$

所以当满足 $0 \lt d \le \frac{1}{6}$ 时，$T(n) = \Theta(n^3)$

综上，$T(n) = \Theta(n^3)$

对于递归式 $T(n) = 4T(n/3) + n$，使用递归树法，给出解的渐进边界。

将该递归式转化为递归树，如下图：

我们可以通过这个图计算出：

• 递归树的深度为: $n/3^d = 1 \implies d = \log_3 n$
• 递归树中第i层的结点数：$4^i$
• 最后一层的代价为：$4^d \times \Theta(1) = \Theta(n^{\log_3 4})$

观察到代价是一个等比数列，所以我们整理可以得到总代价：

因为 $\log_3 4 > 1 \implies n^{\log_3 4} > n$，所以 $T(n) = \Theta(n^{\log_3 4})$

对于递归式 $T(n) = T(n - 1) + T(n / 2) + n$，使用递归树法，给出解的渐进上界。

将该递归式转化为递归树，如下图：

这个递归图比较奇怪，左侧减的没有右侧加的到底快，我们只能估计它的边界。

本题需要我们求它的上界，即取最长的路径作为树的深度进行计算。可以得到：

• 递归树的深度 (最深的路径边数) 为: $d_1 = n - 1$
• 递归树中d_1层的结点数：$2^{d_1}$

观察到代价中n的系数是一个等比数列，后面跟着的是一个常数。我们可以忽略这个常数，得到总代价：

观察到代价由 $2n \times (3/2)^n$ 和 $\Theta(2^n)$ 中大的那个决定，因为 $(3/2) < 2$, 在 $n$ 足够大时, $\Theta(2^n) > 2n \times (3/2)^n$。所以 $T(n) = O(2^n)$

对于递归式 $T(n) = 2T(n/4) + \sqrt n$，使用主方法求出渐进边界。

我们对比分水岭函数 $n^{\log_b a}$ 和 驱动函数 $f(n)$ 的大小：

• $n^{\log_b a} = n^{\log_4 2} = n^{\frac{1}{2}}$
• $f(n) = \sqrt n = n ^ {\frac{1}{2}}$

可以发现 $n^{\log_b a} = f(n)$，说明递归树中每一层的代价都差不多。存在一个 $k = 0$, 使得 $f(n) = \Theta(n^{\log_b a} \lg^k n) = n^{\frac{1}{2}}$。

可以应用主方法的Case 2，得到 $T(n) = \Theta(n^{\log_b a} \lg n) = \Theta(\sqrt n \lg n)$

Master Method - Case 2

Case 2: ($f(n) \approx n^{\log_b a}$) 若存在一个常数 $k \ge 0$ 使得 $f(n) = \Theta(n^{\log_b a }\lg^k n)$，则递归式的解为 $T(n) = \Theta(n^{\log_b a }\lg^{k+1} n)$。这种情况下每一层的代价基本相等为 $\Theta(n^{\log_b a} \lg^k n)$，而其高度可以表示为 $\Theta(\lg n)$。

对于递归式 $T(n) = 4T(n/2) + n^2\lg n$，使用主方法求出渐进边界。

我们对比分水岭函数 $n^{\log_b a}$ 和 驱动函数 $f(n)$ 的大小：

• $n^{\log_b a} = n^{\log_2 4} = n^2$
• $f(n) = n^2\lg n$

可以发现两个函数之间相差了一个 $\lg n$，与Case 2相似：存在一个 $k = 1$, 使 $f(n) = \Theta(n^{\log_b a}\lg^k n) = n^2\lg n$

所以 $T(n) = \Theta(n^2\lg^2 n)$

对于递归式 $T(n) = 2T(n/4) + n$，使用主方法求出渐进边界。

我们对比分水岭函数 $n^{\log_b a}$ 和 驱动函数 $f(n)$ 的大小：

• $n^{\log_b a} = n^{\log_4 2} = n^{\frac{1}{2}}$
• $f(n) = n$

因为 $n^{\log_b a} \lt f(n)$，与Case 3相似。

进一步检测: $2\times \frac{n}{4} = \frac{n}{2} \le cn$，存在一个常数 $c,\ c\in [\frac{1}{2},1]$ 使得正则条件成立。

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

Master Method - Case 3

Case 3: ($f(n) > n^{\log_b a}$) 若存在一个常数 $\epsilon > 0$ 使得 $f(n) = \Omega(n^{\log_b a+\epsilon})$，且 $f(n)$ 在 $n$ 足够大时满足条件 $af(n/b) ≤ cf(n), c \lt 1$ 时，递归式的解为 $T(n) = \Theta(f(n))$。这种情况与情况一正好相反，代价主要来源于 根节点。

对于递归式 $T(n) = 7T(n/2) + n$，使用主方法求出渐进边界。

我们对比分水岭函数 $n^{\log_b a}$ 和 驱动函数 $f(n)$ 的大小：

• $n^{\log_b a} = n^{\lg 7}$
• $f(n) = n$

明显：$n^{\log_b a} \gt f(n)$，与Case 1相似。

存在一个常数 $\epsilon = 6 > 0$，使 $f(n) = O(n^{\log_b a-\epsilon}) = O(n^{\lg 7-6})$

所以 $T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\lg 7})$

Master Method - Case 1

Case 1: ($f(n) < n^{\log_b a}$) 若存在一个常数 $\epsilon > 0$ 使得 $f(n) = O(n^{\log_b a-\epsilon})$，则递归式的解为 $T(n) = Θ(n^{\log_b a})$。这种情况下代价主要来源于 叶子节点。

Summary#

总结一下本节内容：本节主要介绍了三种解递归式的方法 - 代入法、递归树法和主方法。

好的，以下是《算法导论》（第4版）第4章中三种求解递归式方法的总结：

• 代入法 (Substitution Method): 本质上是一种 数学归纳法。可以用来证明任何递归式的解，最大的难点在于需要 提前猜测 出解的正确形式。

解法步骤:

1. 猜测 (Guess): 凭借经验或使用递归树法，猜测解的渐近形式，例如 $T(n) = O(g(n))$。
2. 归纳假设 (Assume): 假设猜测对于所有小于 $n$ 的 $k$ 成立，即 $T(k) \le c \cdot g(k)$（对于 $O$ 界）。
3. 证明 (Prove): 将归纳假设代入原递归式，通过数学推导证明 $T(n) \le c \cdot g(n)$ 也成立。
4. 求解常数与边界: 在推导过程中，需要找到一个合适的常数 $c > 0$ 和 $n_0$，使得不等式对于所有 $n \ge n_0$ 成立，并确保解对边界条件也有效。
5. 配平: 有时为了使归纳成立，你需要从猜测中减去一个低阶项，例如猜测 $T(n) \le c n^2 - d n$ 而不是 $T(n) \le c n^2$。

• 递归树法 (Recursion-Tree Method): 它非常直观，将递归式的代价在树的各个层级上进行可视化展开。适用于分析分治算法的递归式，特别是 $T(n) = aT(n/b) + f(n)$ 形式。

解法步骤:

1. 构建树: 画出递归树。根节点代表 $f(n)$ 的代价，它有 $a$ 个子节点，每个子节点代表规模为 $n/b$ 的子问题，代价为 $f(n/b)$，依此类推。
2. 计算层代价: 计算树的第 $i$ 层的总代价（通常是 $a^i \cdot f(n/b^i)$）。
3. 计算树深度 (高度): 确定树的深度 $h$（通常是 $\log_b n$）。
4. 计算叶子代价: 确定叶子节点的总数（通常是 $a^h = n^{\log_b a}$）以及它们的总代价（通常是 $\Theta(n^{\log_b a})$）。
5. 求和: 将所有层（从根到叶子之前的所有内部节点）的代价与叶子层的总代价相加。
6. 分析总和: 分析这个总和的渐近界，从而得出 $T(n)$ 的猜测。

• 主方法 (Master Method): 本质上是递归树法中三种常见情况（代价由叶子主导、由根主导、或均匀分布）的数学归纳总结。仅 适用于 $T(n) = aT(n/b) + f(n)$ 形式的递归式，其中 $a \ge 1, b > 1$，$f(n)$ 是渐近正函数。

解法步骤:

1. 确定参数: 找出 $a$, $b$, 和 $f(n)$。
2. 计算关键函数: 计算 $g(n) = n^{\log_b a}$。
3. 比较 $f(n)$ 和 $g(n)$:
   • Case 1 (叶子主导): 如果 $f(n) = O(n^{\log_b a - \epsilon})$ 对于某个 $\epsilon > 0$ 成立（即 $g(n)$ 在多项式意义上大于 $f(n)$），则 $T(n) = \Theta(n^{\log_b a})$。
   • Case 2 (代价均衡): 如果 $f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ 对于某个 $k \ge 0$ 成立（即 $f(n)$ 和 $g(n)$ 渐近相等，或只差一个 $\log$ 因子），则 $T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$。
     • (最常见的子情况 $k=0$：若 $f(n) = \Theta(n^{\log_b a})$，则 $T(n) = \Theta(n^{\log_b a} \log n)$)。
   • Case 3 (根代价主导): 如果 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 对于某个 $\epsilon > 0$ 成立（即 $f(n)$ 在多项式意义上大于 $g(n)$），并且 满足 正则条件 (regularity condition)（即 $a f(n/b) \le c f(n)$ 对于某个 $c < 1$ 和足够大的 $n$ 成立），则 $T(n) = \Theta(f(n))$。
4. 注意: 如果 $f(n)$ 和 $g(n)$ 的关系落入上述三种情况的“间隙”中（例如 $f(n)$ 比 $g(n)$ 大，但不是多项式意义上的大），则主方法失效，必须退回使用递归树法或代入法。