时间复杂度主定理

当我们在使用分治法时，有一个问题必须回答——分治算法的时间复杂度是如何计算的？

从分治到递推关系

分治法是将一个大规模问题分解为若干较小的子问题，再把子问题的解合并起来，得到原问题的解。递推关系是对这一过程的时间代价进行数学建模的方式。

从一个具体的例子入手更容易理解。以归并排序为例，设 $T(n)$ 表示原问题的时间复杂度，其中 $n$ 是输入数据的规模。第一次划分时，原始数据被分成两个相等的部分，每部分规模为 $n/2$。接着对这两部分递归调用归并排序，这部分的时间复杂度为 $2 T(n/2)$。最后，将两个已排序的子数组合并，需要 $\Theta(n)$ 的时间复杂度。

基于上述分析，可以写出归并排序的递推关系：

可以想象，对任意分治算法，其时间复杂度都可以表示成递推关系。递推关系的右端通常由两部分组成：分解出的子问题的总代价，以及分解与合并子问题的总代价。第一部分仍是 $T$ 的函数，第二部分则代表实际的渐近复杂度。

仅有递推关系还不足以确定算法的确切时间复杂度，我们需要进一步计算出实际解 $T(n)$。

代入法

求解递推关系的第一种方法称为代入法。我们需要先猜测解的形式，再用数学归纳法证明这个猜测是正确的。

对于方程 (1)，假设我们猜测的解为 $T(n) = O(n \log n)$。若去掉渐近记号，这个等式等价于 $T(n) \le c_1 n \log n$，其中 $c_1$ 是任意正常数。

按照数学归纳法，我们首先需要证明猜测对较小的 $n$ 成立。当 $n=1$ 时，由方程 (1) 得 $T(1) = \Theta(1) = d_1$，其中 $d_1$ 是某个大于 0 的常数。按照猜测，我们希望 $T(1) \le c_1 \log 1 = 0$，但无论怎样选取 $c_1$，这个不等式都不能成立，因为 $T(1) = d_1$ 恒大于 0。数学归纳法还没开始就失败了。

不过不必担心，这只是由 $\log 1 = 0$ 造成的特殊情况。我们可以把数学归纳的起始状态放在 $n>1$ 处，这不影响数学归纳法的结果。我们只关心 $n$ 足够大时 $T(n)$ 的渐近性质，而不关心初始阶段。

现在令 $n = 2$，则 $T(2) = 2T(1) + d_2 = 2d_1 + d_2$。我们希望 $T(2) \le c_1 \log 2$ 成立。化简得 $c_1 \ge d_1 + d_2/2$。由于 $d_1$、$d_2$ 都是常数，这样的 $c_1$ 一定存在，初始条件成立。

接下来，数学归纳法假设解在 $n/2$ 处成立，即 $T(n/2) \le c_1 \frac{n}{2} \log\frac{n}{2} = \frac{1}{2}c_1n(\log n - 1)$。然后证明 $T(n) \le c_1 n \log n$ 也成立。

把 $T(n/2)$ 代入方程 (1)，得

其中最后一行的不等式要求 $d_2 - c_1 < 0$，显然这样的 $c_1$ 存在，因此证明完毕。

这样，我们证明了 $T(n) = O(n \log n)$ 是递推关系 (1) 的解。然而这还不是结束，这个渐近记号不是紧界。我们能否进一步猜测 $T(n) = \Theta(n \log n)$ 成立呢？这确实是个好主意。于是，接下来只要能证明 $T(n) = \Omega(n \log n)$ 成立，就能得到上述紧界。去掉渐近记号后，这个等式等价于 $T(n) \ge c_2 n \log n$。再次使用数学归纳法，先确认它在初始阶段成立，然后假设解在 $n/2$ 处成立，即可推出解在 $n$ 处成立。因此证明完毕。由于证明步骤与刚才几乎相同，此处不再赘述，读者可以自己尝试。

代入法依赖于准确的猜测，而这往往不切实际。因此，实践中更常见的做法是先用其他方法得到一个猜测，再用代入法验证该猜测。接下来要介绍的递归树方法就提供了这种可能。

递归树

把递推关系逐层展开，会直接得到一个树状结构。例如，以 $T(n) = 3 T(n/4) + \Theta(n^2)$ 为例，看看如何画出它的递归树。

展开第一层，在根节点下画出三个子节点。

这里的 $cn^2$ 表示该层分解与合并的代价，对应递推关系中 $\Theta(n^2)$ 所表示的部分。

接下来，进一步展开到第二层。

这里，第一层每个节点的代价仍是 $c(\frac{n}{4})^2$，仍对应递推关系中 $\Theta(n^2)$ 所表示的部分，但数据规模已从 $n$ 变为 $n/4$。

照此继续展开，直到叶节点。

这样就得到一棵完整的递归树。每一层的数据规模都是上一层的四分之一，直到叶节点的数据规模为 1，因此总层数为 $\log_4 n$。图中最右侧计算了每一层所有节点的总代价，计算很简单：将单个节点的代价乘以该层的节点数。最后一层中，单个节点的代价是常数，节点数为 $3^{\log_4 n} = n^{\log_4 3}$，我们把总代价记为 $\Theta(n^{\log_4 3})$。

接下来，只需把所有节点的代价相加，即可得到递推关系的解。

这里，在第三行我们做了一次简化，把有限等比级数替换为无限等比级数。虽然总量变大了，但这个无限递减等比级数是有极限的，因此这种替换可以简化推导过程。第五行中的第二项相对于第一项是低阶项，因此被舍去，从而得到最终结果。

与前面类似，我们只证明了递推关系的上界。自然而然地，我们想试试能否也证明下界。在上述式子中，求和式的每一项都含有 $cn^2$，且每一项都是正的，因此 $T(n) = \Omega(n^2)$ 显然成立。所以，该递推关系的解为 $T(n) = \Theta(n^2)$。

在这个例子中，我们用递归树方法直接算出了递推关系的解。当然，也可以用代入法来验证这个解是否正确。有些情况下，用递归树方法算出精确解会稍显困难，但这并不妨碍我们做出合理的猜测，然后再用代入法进一步验证该猜测。

主定理

代入法与递归树法各有弊端。前者需要准确的猜测，后者则要画出递归树并推导结果。推导多了，你可能会发现大多数递归解的形式似乎都差不多。从上面的推导过程可以看出，最终解完全取决于中间各层的代价之和，而与叶层无关，因为后者是低阶项。而在其他递归树中，最终解可能完全取决于叶层的代价，与中间各层无关。因此，我们或许可以对递归公式进行分类，并按照某些规则直接写出最终解。这就是主定理的思想。

当分治法每次均匀切分数据时，递推公式一般具有如下形式。

其中 $a$ 是正整数，表示每次划分产生的子问题个数；$b$ 是大于 1 的整数，表示每次问题规模的缩减倍数；$f(n)$ 是渐近正函数，表示分解与合并的代价。

为了求出适用于任意 $a$、$b$ 与 $f(n)$ 的统一解，我们仍需要用递归树计算所有中间节点与叶节点的代价，并尝试推出一个简洁的结果。

从图中可以看出，所有节点的总代价为 $T(n) = \Theta(n^{\log_b a}) + \sum_{j=0}^{\log_b n-1}{a^j f(n/b^j)}$。进一步的推导需要一个突破性的想法，我不清楚最初的研究者是如何发现下面这个规律的，但它确实很神奇。

研究者发现，$f(n)$ 与 $\Theta(n^{\log_b a})$ 的大小关系决定了 $\sum_{j=0}^{\log_b n-1}{a^j f(n/b^j)}$ 最终的简化形式。定义

现在分析三种情形。

1. 若 $\Theta(n^{\log_b a})$ 更大，可以假设存在常数 $\epsilon > 0$，使得 $f(n) = O(n^{\log_b a-\epsilon})$。把它代入求和公式，可化简为 $g(n) = O(n^{\log_b a})$。
2. 若两者同样大，直接代入方程 (3) 化简，可得 $g(n) = \Theta(n^{\log_b a} \log n)$。
3. 若 $f(n)$ 更大，且存在某个常数 $c < 1$，使得对所有足够大的 $n$，$a f(n/b) \le c f(n)$ 成立，那么可以推出 $g(n) = \Theta(f(n))$。

这里不给出完整的证明过程，一是因为不想让文章太长，二是觉得这些证明颇为繁琐，意义不大。感兴趣的同学可以参阅原书。

把三种情形下的函数 $g(n)$ 代入完整解，得到：

• 情形 1：$T(n) = \Theta(n^{\log_b a}) + O(n^{\log_b a}) = \Theta(n^{\log_b a})$
• 情形 2：$T(n) = \Theta(n^{\log_b a}) + \Theta(n^{\log_b a} \log n) = \Theta(n^{\log_b a} \log n)$
• 情形 3：$T(n) = \Theta(n^{\log_b a}) + \Theta(f(n)) = \Theta(f(n))$

现在，对任意递推公式，我们只需判断它属于哪种情形，然后直接代入对应的公式即可。为了便于理解，我们看几个例子。

示例 1：

$T(n) = 9 T(n/3) + n$

对于这个递推公式，$a = 9$，$b = 3$，$f(n) = n$。由于 $f(n) = n$ 渐近小于 $\Theta(n^2)$，适用于主定理的第一种情形，解为 $T(n) = \Theta(n^2)$。

示例 2：

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

对于这个公式，$a = 1$，$b = 3/2$，$f(n) = 1$。由于 $n^{\log_b a} = n^{\log_{3/2} 1} = n^0 = 1$，恰好等于 $f(n)$，适用于主定理的第二种情形，解为 $T(n) = \Theta(\log n)$。

示例 3：

$T(n) = 3T(n/4) + n\log n$

对于这个公式，$a = 3$，$b = 4$，$f(n) = n\log n$。由于 $n^{\log_b a} = n^{\log_4 3} = n^{0.793}$，而 $f(n) = n\log n$ 渐近大于 $n^{0.793}$，应考虑主定理的第三种情形。不过，我们需要检验附加条件是否成立：存在常数 $c < 1$，使得对所有足够大的 $n$，$a f(n/b) \le c f(n)$ 成立。把 $a$、$b$、$f(n)$ 代入该不等式，得

当 $c \ge \frac{3}{4}$ 时，该不等式恒成立，附加条件得到满足。因此，它适用于主定理的第三种情形，解为 $T(n) = \Theta(n\log n)$。

示例 4：

$T(n) = 2T(n/2) + n\log n$

对于这个公式，$a = 2$，$b = 2$，$f(n) = n\log n$。由于 $n^{\log_b a} = n^{\log_2 2} = n$，而 $f(n) = n\log n$ 渐近大于 $n$，应考虑主定理的第三种情形。把 $a$、$b$、$f(n)$ 代入该不等式，得

当 $c \ge 1$ 时，该不等式恒成立。然而附加条件要求 $c < 1$，因此这种情况不能套用主定理的第三种情形。也就是说，并非所有形如 $T(n) = a T(n/b) + f(n)$ 的递推公式都能用主定理求解；情形二与情形三之间存在缺口。遇到这种情况，我们只能使用递归树方法。同学们可以试一下，结果是 $T(n) = \Theta(n \log^2 n)$。

看完这四个例子，你掌握主定理了吗？如有疑问，欢迎留言，我会尽快回复。

算法的学习永无止境，而时间复杂度的计算是基本功，不可小觑。

细节

细心的读者可能会注意到，上面提到的第四种情形中，虽然 $nlgn$ 渐近增长快于 $n$，但它并不是多项式意义下的渐近更大，因为不存在 $\epsilon > 0$ 使得 $nlgn = \Omega \left( n^{1+\epsilon} \right)$ 成立。相反，对任意 $\epsilon > 0$，$nlgn = o \left( n^{1+\epsilon} \right)$ 成立。因此，事实上该情形无需判断正则条件即可提前得出结论。不过，前文中第三种情形我没有强调多项式意义下的渐近更大，并非因为忘了写，而是因为这个条件根本用不上。

对任何符合主定理格式的递推关系，若它满足情形三中的正则条件，则必然满足 $f\left(n\right) = \Omega \left( n^{log_b a + \epsilon} \right)$。具体的证明细节可参见 StackExchange 上的这个回答，此处不再详述。

虽然正则条件可以推出 $f\left(n\right) = \Omega \left( n^{log_b a + \epsilon} \right)$，但反过来并不成立。我们可以构造如下函数：

$T\left(n\right) = T\left(n/2\right) + n\left( 2 - \cos n \right)$

这里 $a=1$，$b=2$，且对任意 $\epsilon \le1$，$f\left(n\right) = n \left( 2 - \cos n \right) = \Omega \left( n^{log_2 1+ \epsilon} \right) = \Omega \left( n^\epsilon \right)$ 成立。然而，应用正则条件时：

$\begin{aligned} f\left(n / 2\right) &\le c f\left(n\right) \\ \frac{n}{2} \left(2 - \cos \frac{n}{2} \right) & \le c \left( 2 - \cos n \right) \end{aligned}$

对任意 $c \lt 1$，右端必须是 $c \left( 2 - \cos n \right) \lt 3$。然而，当 $n$ 足够大时，左端必定大于 $3$。因此这个不等式不能成立，正则条件不满足。

参考

这些情形出自维基百科的主定理词条。