algorithm - 递推方程的复杂度类

Question

自从我的算法本科课程以来，我已经有一段时间了。你能帮我解决这个递归方程吗？

T(0)=14
T(n)=4*T(n/2)+n^2 for n>0

我对尽可能低的上限感兴趣。

标签： algorithmcomplexity-theoryrecurrence

Answer 1

这个方程的精确解很难计算，但根据主定理，它的渐近界是 Θ(n ² log n)

编辑1：

实际上可以计算出精确的解，它是（对于 n > 0）

n ² (228 log(2)+4 log (n)) / log(16)

（我通过在主定理解中添加常数并使用计算机代数应用求解 5 个方程的系统来获得此解）