什么是 T(N)=4T(N/2)+(N^2)/logN 的时间复杂度

Question

这个问题是在麻省理工学院关于算法分析的视频中给出的， 下面这道题用master方法做不了，可以用递归树求解。

能告诉我解决方法吗？

Answer 1

为什么您声称 masters theorem 无法做到这一点？这个定理只有a和b是常数和a >= 1和b > 1的一些约束。它适用于任何 f(n)，因此您可以在此处应用它。

如果您应用它，您会看到 a=4, b=2，因此 c = 2。 n^c 比您的 f(n) 增长得更快，因此复杂度为 O(n^2)。