为何主定理第三类情况不适用于T(n)=2T(n/2)+nlgn及多项式大小疑问

1. 为什么主定理第三类情况无法应用于递推式 T(n)=2T(n/2)+nlg n？ #

先把主定理第三类的核心条件掰碎了说，它专门针对形如 T(n) = aT(n/b) + f(n)（其中 a≥1，b>1）的递推式，必须同时满足两个硬条件：

• 条件1：f(n) = Ω(n^(log_b a + ε))，这里的 ε>0——直白点说，f(n) 的增长速度得比 n^(log_b a) 多项式级更快；
• 条件2：存在常数 c<1，对足够大的 n 能满足 a·f(n/b) ≤ c·f(n)（正则条件）。

回到这个递推式：a=2，b=2，所以 log_b a = log₂2 = 1，我们要对比的就是 f(n)=nlg n 和 n^1 = n 的增长关系。

先看条件1：我们需要找到一个 ε>0，让 nlg n 至少能追上 n^(1+ε) = n·n^ε 的增长速度（也就是渐近下界）。但这里有个关键的渐近规律：对数函数的增长速度比任何正多项式次幂都慢——当 n 趋向无穷大时，哪怕 ε 取0.0001，n^ε 都会把 lg n 远远甩在后面，用极限表示就是 lim(n→∞) lg n / n^ε = 0。这意味着根本找不到这样的 ε>0 能让 nlg n 满足 Ω(n^(1+ε))，条件1直接不成立，自然没法用第三类情况。

2. 关于“多项式更大”与 nlg n 的困惑 #

首先得纠正一个常见误区：你提到的 n^0.1 < lg n <n^0.4 只在有限范围内成立，放到渐近分析的无穷大场景下就不适用了。

我们说“f(n)是g(n)的多项式更大函数”，严格定义是：存在某个 ε>0，使得 f(n) = Ω(g(n)·n^ε)——也就是 f(n)/g(n) 的增长速度至少要达到某个正多项式次幂的级别。

对于 f(n)=nlg n 和 g(n)=n，它们的比值是 lg n。而渐近意义下，对任意的 ε>0，lg n = o(n^ε)（小o记号表示前者增长远慢于后者）。比如哪怕取 ε=0.001，当 n 足够大时，n^0.001 都会超过 lg n，并且差距会越来越大。这说明 lg n 根本没达到“多项式级增长”的要求，因此 nlg n 并不是 n 的多项式更大函数——它只是比 n 增长快，但增长速度是对数级的，远达不到多项式级的幅度。

这就是为什么哪怕你在某个区间看到 lg n 比 n^0.1 大，从渐近分析的角度看，它还是不够“大”到满足主定理第三类的条件，自然无法应用该情况。

内容的提问来源于stack exchange，提问作者Amisha Bansal