如何区分递推方程对应主定理（Master Theorem）的第一种和第二种情况

首先纠正你案例中的前提错误 #

你给出的递推式T(n)=4T(n/2)+n²√n中，f(n)=n²√n = n^2.5，既不属于O(n²)也不属于Θ(n²)，你对f(n)的量级判断有误，这是你产生混淆的核心原因。这个案例实际符合主定理的情况3，最终时间复杂度为Θ(n^2.5)。

主定理三类情况的互斥性说明 #

主定理的三类判定条件是严格互斥的，不会出现同时满足情况1和情况2的场景，核心原因是两类情况对f(n)和n^(log_b a)的量级关系要求完全不同：

• 情况1的要求不是简单的f(n)=O(n^(log_b a))，而是存在一个大于0的常数ε，使得f(n)=O(n^(log_b a - ε))：也就是要求f(n)比n^(log_b a)严格慢至少一个多项式级别的量级，不能是同阶。
• 情况2的要求是**f(n)=Θ(n^(log_b a) * log^k n)，其中k≥0**：也就是要求f(n)和n^(log_b a)属于同阶（允许差若干倍logn的幂次）。

如果f(n)满足情况2的条件，说明它和n^(log_b a)同阶，自然不可能找到一个ε>0让它属于n^(log_b a - ε)的上界范围，因此必然不满足情况1的要求，不存在选择冲突的问题。

正确示例验证 #

举两个无歧义的示例：

• 递推式为T(n)=4T(n/2)+n²：log_b a=2，f(n)=Θ(n²)，符合情况2，最终时间复杂度为Θ(n² logn)
• 递推式为T(n)=4T(n/2)+n logn：log_b a=2，存在ε=0.5使得f(n)=O(n^(2-0.5))=O(n^1.5)，符合情况1，最终时间复杂度为Θ(n²)

内容的提问来源于stack exchange，提问作者Amine Dakhli