师父的方法，是哪种情况？
我一直在观看麻省理工学院开放课程网站上的一些视频讲座，在第三个讲座视频中，讲师介绍了递归矩阵乘法，并得出时间复杂度为：
T(n) = θ(n3 )
对我来说，显然我确实需要复习一些数学知识，但我真的看不出该答案与主定理方法提到的任何一种情况之间的联系。我知道递归关系的形式为：T(n) = a*T(n/b) + f(n) 对于 n > 1.
具有以下递归关系：a = 8、b = 2 和 f(n) = Θ(n2).
那么，他们是如何得到θ(n3)的呢？
他提到log28 = 3，这是有道理的。但是，我无法使用 f(n) 的值找出示例递归关系对应于三种情况中的哪一种。
由于情况 2 是唯一一个 f(n) = θ(anything) 的情况，那么我猜就是这样。然而，我想我的问题与对数或指数的属性有关。
如果f(n) = θ(nlog28 * (log2n)k+1 super>) 那么如何从 f(n) 的 θ(n3) 变为 >θ(n2) 使用案例 2？我在这里可能会错过什么？
I've been viewing some video lectures from MIT's opencourseware website, and on the third lecture video the lecturer goes over Recursive Matrix Multiplication and comes up with the time complexity being:
T(n) = Θ(n3)
It's obvious to me that I really need to review some of my math, but I really don't see the connection from that answer and any one of the cases mentioned for the Master Theorem Method. I know that the recursive relation is of the form:T(n) = a*T(n/b) + f(n) for n > 1.
With this recursive relation: a = 8, b = 2, and f(n) = Θ(n2).
So, how did they get Θ(n3)?
He mentioned that log28 = 3, which makes sense. But, I just can't figure out which of the three cases that the example recursive relation corresponds to, using the value of f(n).
Since, Case 2 is the only one where f(n) = Θ(anything), then I'm guessing that that's it. Yet, I guess my problem relates to properties of logarithms or exponents.
If f(n) = Θ(nlog28 * (log2n)k+1) then how do you go from having a Θ(n3) for f(n) to a Θ(n2) using case 2? What is it that I might be missing here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
查看有关主定理的 Wiki 页面。
他们在讨论情况 1 时讨论了这种非常精确的情况 (a = 8, b=2, f(n) = O(n2))。（不是情况 2）。请注意，如果 f(n) = θ(n2)，则 f(n) = O(n2)，因此可以应用情况 1。
希望有帮助。
Check out the Wiki page on the Master Theorem.
They discuss this very exact situation (a = 8, b=2, f(n) = O(n2)) when discussing case 1. (not case 2). Note that if f(n) = Θ(n2) then f(n) = O(n2), so case 1 can be applied.
Hope that helps.