求解递推式$T(n) = 2T(n/4) + O(n^2 \log n)$的最紧时间复杂度上界

嘿，你的结论完全正确！$T(n)$的最紧上界确实是$O(n^2 \log n)$，我来一步步拆解验证过程，帮你彻底确认这个结果没问题。

首先我们用高级主定理来分析：
递推式符合主定理的标准形式$T(n) = aT(n/b) + f(n)$，其中：

• $a=2$（子问题的数量）
• $b=4$（每个子问题的规模为原问题的$1/4$）
• $f(n) = O(n^2 \log n)$（非递归部分的时间代价）

先计算$n^{\log_b a}$：$\log_4 2 = 1/2$，所以$n^{\log_b a} = n^{1/2}$。

接下来看主定理的第三种适用情况：
当$f(n) = \Omega(n^{\log_b a + c})$（其中$c>0$），且满足正则条件时，$T(n) = \Theta(f(n))$，对应的最紧上界就是$O(f(n))$。

这里$f(n)=n^2 \log n$，明显比$n^{1/2}$增长快得多，我们取$c=1.5$，就能满足$f(n) = \Omega(n^{1/2 + 1.5}) = \Omega(n^2)$，而$\log n$的存在不会影响这个渐进关系。

再验证正则条件：需要存在$0<k<1$，使得对于足够大的$n$，$a \cdot f(n/b) \leq k \cdot f(n)$。代入数值计算：
$$
2 \cdot f(n/4) = 2 \cdot \left( (n/4)^2 \log(n/4) \right) = 2 \cdot \frac{n^2}{16} (\log n - \log 4) = \frac{n^2}{8} (\log n - \log 4)
$$
当$n$足够大时，$\log n - \log 4 < 2\log n$，所以$\frac{n^2}{8} (\log n - \log 4) < \frac{n^2}{4} \log n$，取$k=1/4$就满足正则条件。

我们也可以用递归树来交叉验证：
递归树的每一层代价如下：

• 第0层（根节点）：$n^2 \log n$
• 第1层：$2 \cdot (n/4)^2 \log(n/4) = \frac{n^2}{8} (\log n - \log 4)$
• 第2层：$2^2 \cdot (n/4²⁾2 \log(n/4^2) = \frac{n^2}{64} (\log n - 2\log 4)$
• ...
• 第$k$层：$2^k \cdot (n/4^k)2 \log(n/4^k) = \frac{n^2}{2k} (\log n - k\log 4)$

把所有层的代价加起来：
$$
T(n) = n^2 \log n \sum_{k=0}^\infty \frac{1}{2^k} - n^2 \log 4 \sum_{k=0}^\infty \frac{k}{2^k}
$$
第一个求和是等比数列，和为$2$；第二个求和是经典级数，和为$2$。代入后得到：
$$
T(n) = 2n^2 \log n - 2n^2 \log 4
$$
显然主导项是$n^2 \log n$，所以$T(n) = O(n^2 \log n)$。

两种方法都得到了相同的结果，所以你的判断完全正确，这个就是最紧的上界啦！

备注：内容来源于stack exchange，提问作者user5500