递归方程求解与Master定理

1. 递归方程的定义

$$
T(n) =
\begin{cases}
O(1), & n = 1 \
k,T!\left(\frac{n}{m}\right) + f(n), & n > 1
\end{cases}
$$

$n$ 是问题规模。
当 $n=1$ 时，基本操作时间为常数 $O(1)$。
当 $n>1$ 时，算法将问题分解为 $k$ 个子问题，每个子问题规模为 $n/m$，然后加上合并子问题解的开销 $f(n)$。

这是一个典型的分治递归关系，类似主定理（Master Theorem）的形式。

2. 求解思路（代换法）

通常设 $n = m^t$（即 $t = \log_m n$），然后逐层展开：

当 $n = m$：
$T(m) = k,T(1) + f(m) = k\cdot O(1) + f(m)$。
当 $n = m^2$：
$T(m^2) = k,T(m) + f(m^2) = k^2 O(1) + k f(m) + f(m^2)$。
当 $n = m^3$：
$T(m^3) = kT(m^2) + f(m^3) = k^3 O(1) + k^2f(m) + kf(m^2)+f(m^3)$。
依此类推，可得通项：
$$
T(m^t) = k^t T(1) + \sum_{j=0}^{t-1} k^j f(m^{t-j})
$$
即
$$
T(n) = k^{\log_m n} \cdot O(1) + \sum_{j=0}^{\log_m n - 1} k^j f!\left(\frac{n}{m^j}\right)
$$

3.求解算法复杂度

要从递归方程的通项公式看出算法复杂度，关键是分析展开后的求和式，找出主导项。其中 $n^{\log_m k} = k^{\log_m n}$。

1）第一项的影响

第一项 $n^{\log_m k} \cdot O(1)$ 是递归树中所有叶节点的代价（每个叶节点对应一个规模为 1 的子问题）。它直接给出一个复杂度下界：$\Omega(n^{\log_m k})$。

2）第二项（求和项）的分析

第二项代表所有非叶节点的代价之和，即每一层合并（或分解）的代价 $f$ 乘上该层节点数。
令 $i = t-j$，则求和可写作：

$$
\sum_{i=1}^{t} k^{t-i} , f(m^i) = \sum_{i=1}^{t} k^{t-i} , f(m^i)
$$

为了方便，我们通常直接分析：

$$
S = \sum_{j=0}^{t-1} k^j , f!\left(\frac{n}{m^j}\right)
$$

现在，复杂度取决于 $f(n)$ 的增长速度与 $k$、$m$ 的关系。常见情况如下：

情况 1：$f(n) = O(n^{c})$ 且 $c < \log_m k$

此时 $f(n/m^j) = O!\left((n/m^j)^c\right) = O!\left(n^c , m^{-jc}\right)$。代入求和：

$$
S = O!\left( \sum_{j=0}^{t-1} k^j , n^c , m^{-jc} \right) = O!\left( n^c \sum_{j=0}^{t-1} \left( \frac{k}{m^c} \right)^j \right)
$$

因为 $\log_m k > c$，所以 $k > m^c$，即 $\frac{k}{m^c} > 1$。此时求和是一个几何级数，且公比大于 1，因此最后一项（$j=t-1$）占主导：

$$
\sum_{j=0}^{t-1} \left( \frac{k}{m^c} \right)^j = \Theta!\left( \left( \frac{k}{m^c} \right)^{t-1} \right)
$$

代入 $t = \log_m n$：

$$
\left( \frac{k}{m^c} \right)^{\log_m n} = \frac{k^{\log_m n}}{m^{c \log_m n}} = \frac{n^{\log_m k}}{n^{c}}
$$

因此 $S = O!\left( n^c \cdot \frac{n^{\log_m k}}{n^{c}} \right) = O!\left( n^{\log_m k} \right)$。
同时第一项已经是 $\Theta(n^{\log_m k})$，所以总复杂度为：

$$
T(n) = \Theta!\left( n^{\log_m k} \right)
$$

结论：当 $f(n)$ 增长慢于 $n^{\log_m k}$ 时，递归树中叶节点的代价（即第一项）主导。

情况 2：$f(n) = \Theta(n^{\log_m k})$

设 $f(n) = \Theta(n^{\log_m k})$，则 $f(n/m^j) = \Theta!\left( (n/m^j)^{\log_m k} \right) = \Theta!\left( n^{\log_m k} , m^{-j\log_m k} \right)$。代入求和：

$$
S = \Theta!\left( \sum_{j=0}^{t-1} k^j , n^{\log_m k} , m^{-j\log_m k} \right)
$$

由于 $k = m^{\log_m k}$，所以 $k^j = m^{j\log_m k}$，因此 $k^j \cdot m^{-j\log_m k} = 1$。于是：

$$
S = \Theta!\left( n^{\log_m k} \sum_{j=0}^{t-1} 1 \right) = \Theta!\left( n^{\log_m k} \cdot t \right) = \Theta!\left( n^{\log_m k} \log_m n \right)
$$

再加上第一项 $n^{\log_m k}$，最终：

$$
T(n) = \Theta!\left( n^{\log_m k} \log n \right)
$$

结论：当 $f(n)$ 与 $n^{\log_m k}$ 同阶时，每一层的代价相同，总代价多一个 $\log n$ 因子。

情况 3：$f(n) = \Omega(n^{c})$ 且 $c > \log_m k$（并满足正则条件）

此时 $k < m^c$，即 $\frac{k}{m^c} < 1$。求和中的公比小于 1，几何级数收敛，前几项（即 $j$ 较小，规模接近 $n$ 的层）占主导：

$$
S = \Theta!\left( f(n) \right) \quad \text{或} \quad S = O!\left( f(n) \right) \text{（若严格收敛）}
$$

具体地，由于 $f(n)$ 增长较快，递归树的根节点（即第一层）的代价 $f(n)$ 已经大于所有下层代价之和。所以总复杂度由 $f(n)$ 决定：

$$
T(n) = \Theta!\left( f(n) \right)
$$

结论：当合并代价增长快于子问题代价时，复杂度由合并代价主导。

4. 实例说明

归并排序：$k=2, m=2, f(n)=\Theta(n)$
$\log_m k = \log_2 2 = 1$，与 $f(n)$ 阶相同 → 情况 2：$T(n)=\Theta(n \log n)$。
二分查找：$k=1, m=2, f(n)=\Theta(1)$
$\log_m k = 0$，$f(n)=\Theta(1)$ 与 $n^0$ 同阶 → 情况 2：$T(n)=\Theta(\log n)$。
简单的分治求最大值：$k=2, m=2, f(n)=\Theta(1)$
$\log_m k = 1$，$f(n)$ 阶低于 $n^1$ → 情况 1：$T(n)=\Theta(n)$。
Strassen 矩阵乘法：$k=7, m=2, f(n)=\Theta(n^2)$
$\log_2 7 \approx 2.807$，$f(n)=n^2$ 小于 $n^{2.807}$ → 情况 1：$T(n)=\Theta(n^{\log_2 7})$。

5. 小结

从通项公式看出算法复杂度，本质就是比较两项的大小：

叶节点总代价：$n^{\log_m k}$
内节点总代价：$\sum k^j f(n/m^j)$

通过判断 $f(n)$ 与 $n^{\log_m k}$ 的相对增长速度，即可确定哪个是主导，以及是否需要乘以 $\log n$ 因子。这正是主定理（Master Theorem）背后的直观逻辑，也是递归算法分析的核心方法。