使用大师方法
在我的期中考试中，我遇到了问题：
T(n) = 8T(n/2) + n^3
我应该使用大师或替代方法找到它的大θ符号。所以我所做的是
a = 8, b = 2 k = 3
log28 = 3 = k
因此，T(n) 是大 theta n3。我得了 1/3 分，所以我一定是错的。我做错了什么？
On my midterm I had the problem:
T(n) = 8T(n/2) + n^3
and I am supposed to find its big theta notation using either the masters or alternative method. So what I did was
a = 8, b = 2 k = 3
log28 = 3 = k
therefore, T(n) is big theta n3. I got 1/3 points so I must be wrong. What did I do wrong?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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 > ，n^3 = O(n^(3-e)) 不为真。 0.
所以你选择了错误版本的主定理。
您需要应用主定理的不同版本：
如果 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
即例如(n) = g(n/2) + 1。
这意味着 g( n) = Theta(logn)，因此 T(n) = Theta(n^3 logn)。
T(n) = aT(n/b) + f(n)
You applied the version when f(n) = O(n^(log_b(a) - e)) for some e > 0.
This is important, you need this to be true for some e > 0.
For f(n) = n^3, b = 2 and a = 8,
n^3 = O(n^(3-e)) is not true for any e > 0.
So your picked the wrong version of the Master theorem.
You need to apply a different version of Master theorem:
if f(n) = Theta ((log n)^k * n^log_b(a)) for some k >= 0,
then
T(n) = Theta((log n)^(k+1) * n^log_b(a))
In your problem, you can apply this case, and that gives T(n) = Theta(n^3 log n).
An alternative way to solve your problem would be:
T(n) = 8 T(n/2) + n^3.
Let g(n) = T(n)/n^3.
Then
n^3 *g(n) = 8 * (n/2)^3 * g(n/2)+ n^3
i.e g(n) = g(n/2) + 1.
This implies g(n) = Theta(logn) and so T(n) = Theta(n^3 logn).