如何求解分治算法递推式T(n)=a*T(n/4)+n²/log n+n²

首先对非递归项做渐近化简：分解开销O(n²/log n)是比合并开销O(n²)低阶的项，因此整个非递归部分的开销可以简化为Θ(n²)，原递推式可以归约为标准主定理适用形式：
T(n) = a*T(n/4) + Θ(n²)，其中递归终止条件为T(1)=Θ(1)。

基于主定理和递推树法，按参数a的取值分三种情况讨论，此处主定理分支参数b=4，临界指数为log_b a = log_4 a：

• 当a < 16时
  此时log_4 a < 2，非递归项n²的增长阶高于递归分支的临界阶n^{log_4 a}，满足主定理第三种情形。正则条件验证：a*f(n/4) = a*(n/4)² = (a/16)n²，因a<16，存在常数c=a/16 < 1满足正则要求，最终时间复杂度为T(n) = Θ(n²)。
• 当a = 16时
  此时log_4 a = 2，非递归项n²和递归分支临界阶同阶，满足主定理第二种情形。额外的低阶项n²/log n在递推树逐层求和时总贡献为Θ(n² log log n)，远低于主导项的求和结果，最终时间复杂度为T(n) = Θ(n² log n)。
• 当a > 16时
  此时log_4 a > 2，非递归项n²的增长阶低于递归分支的临界阶n^{log_4 a}，满足主定理第一种情形，复杂度由递归叶子节点的总开销主导，最终时间复杂度为T(n) = Θ(n^{log_4 a})。

上述结论可以通过递推树等比求和直接验证：递推树第k层共有a^k个规模为n/4^k的子问题，每层非递归开销总和为a^k * (n/4^k)² = n²*(a/16)^k，对所有层求和是公比为a/16的等比数列：公比小于1时和收敛到常数倍n²，公比等于1时和为n²乘以总层数log n，公比大于1时和由最后一层叶子节点总数量主导，和主定理结论完全一致。

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