algorithm - 我可以将大师定理用于这种递归关系吗？

Question

我解决了我的作业问题，我使用了递归树。

但是解决方案说这种递归关系可以通过大师定理来解决！

T(N) = 49T(N/25) + n^(3/2)log(n)

我解决了 n^(3/2) log^2(n)

但解决方案说 n^(3/2) log(n)

我不知道为什么这种情况可以使用大师定理并且是正确的。

Answer 1

我们可以看到a=49和b=25。注意那个log_b(a) ~ 1.2和那个3/2 = 1.5。因此，log_b(a) < 3/2。因此，我们可以看到，f(n) = n^{3/2}log(n) = Omega(n^{log_b(a) + epsilon})对于一些 epsilon，主定理的情况 3 适用。因此，运行时间为

T(n) = Theta(f(n)) = n^{3/2}log(n)

注意：您还必须检查

af(n/b) <= cf(n)

对于一些常数c。当然

49 (n/25)^{3/2} log(n/25) <= c n^{3/2}log(n)

可以通过将两边除以n^{3/2}然后c log(n)从两边减去来检查

(49/25^{3/2} - c) log n - 49/25^{3/2} log(25) <= 0

至少对于c > 49/25^{3/2}（没有必要弄得这么紧）来说，这肯定是正确的。