algorithm - 如何用大师定理求解递推关系 T(n) = 8T(n/2) + 1000 n2

Question

如何通过大师定理求解递归关系 T(N) = 8T(N/2) + 100 N^2。

标签： algorithmrecurrence

Answer 1

首先，您分别在您的描述和问题中使用了100和。1000

本 注解：考虑100

 T(n) = 100 (nlog(2)(8))

因为，你应该知道 如果 a > b^k，那么 T(n) = θ (nlogba)

In you case a = 8, b = 2 and k=2
hence a>b^k