complexity-theory - 硕士的方法，哪种情况？

Question

我一直在观看麻省理工学院开放课件网站上的一些视频讲座，在第三节讲座视频中，讲师介绍了递归矩阵乘法，并提出时间复杂度为：

T(n) = Θ(n3)

对我来说很明显，我真的需要复习一些数学，但我真的看不出这个答案和主定理方法提到的任何一个案例之间的联系。我知道递归关系的形式是：
T(n) = a*T(n/b) + f(n)对于 n > 1。
使用这种递归关系：a = 8、b = 2和。f(n) = Θ(n2)

那么，他们是怎么得到的呢？Θ(n3)

他提到了，这是有道理的。但是，我只是无法确定示例递归关系对应于三种情况中的哪一种，使用. log28 = 3f(n)

因为，案例 2 是唯一的f(n) = Θ(anything)，那么我猜就是这样。然而，我想我的问题与对数或指数的属性有关。

如果那么你如何从一个for到一个用例 2？我可能在这里错过了什么？f(n) = Θ(nlog28 * (log2n)k+1)Θ(n3)f(n)Θ(n2)

Answer 1

查看有关 Master Theorem 的 Wiki 页面。

他们在讨论案例 1（不是案例 2）时讨论了这种非常精确的情况（a = 8, b=2, f(n) = O(n ^{2 )）。}请注意，如果 f(n) = Θ(n ² ) 则 f(n) = O(n ² )，因此可以应用案例 1。

希望有帮助。