math - 使用大师方法

Question

在我的中期，我遇到了问题：

T(n) = 8T(n/2) + n^3

我应该使用大师或替代方法找到它的大 theta 符号。所以我所做的是

a = 8, b = 2 k = 3

日志₂ 8 = 3 = k

因此，T(n) 是大 theta n ³。我得了 1/3 分，所以我一定是错的。我做错什么了？

Answer 1

T(n) = aT(n/b) + f(n)

当 f(n) = O(n^(log_b(a) - e)) 对于某些 e > 0 时，您应用了该版本。

这很重要，对于某些 e > 0，您需要这样做。

对于 f(n) = n^3，b = 2 和 a = 8，

对于任何 e > 0，n^3 = O(n^(3-e))都不成立。

所以你选择了错误版本的主定理。

您需要应用不同版本的主定理：

如果 f(n) = Theta ((log n)^k * n^log_b(a)) 对于某些 k >= 0，

然后

T(n) = Theta((log n)^(k+1) * n^log_b(a))

在您的问题中，您可以应用这种情况，这给出了 T(n) = Theta(n^3 log n)。

---

解决问题的另一种方法是：

T(n) = 8 T(n/2) + n^3。

令 g(n) = T(n)/n^3。

然后

n^3 *g(n) = 8 * (n/2)^3 * g(n/2)+ n^3

即 g(n) = g(n/2) + 1。

这意味着 g(n) = Theta(logn)，因此 T(n) = Theta(n^3 logn)。