哪种方法最好解决:T(n)=4T(n/5)+(log(n√n))^5

Question

我需要找到T(n)=4T。

我知道三种方法：

• 递归树
• 主方法
• 复发

哪种方法最简单？而且，我怎么能确定我得到了正确的答案？

Answer 1

对于渐近行为，您可以发现主定理(如果可以应用的话)很有用。尽管在主定理的证明中，它使用的是递归树，并且您编写的这些方法并不独立。

要使用主定理，首先简化非递归部分：

log(nsqrt(n)) = log(n) + log(sqrt(n)) = 3/2 log(n)

因此：

T(n) = 4T(n/5) + (3/2 log(n))^5

由主定理c_critic = log_5(4) = log(4)/log(5) ~ 0.86可知，(3/2 log(n))^5 = O(n^0.5)使得0.5 < c_critic。因此，T(n) = Theta(n^{log(4)/log(5)}) ~ Theta(n^0.86)。