子问题大小 w.r.t 斯特拉森矩阵乘法算法

Question

我最近看了一个视频讲座，讲的是Strassen的2n × n矩阵乘法递归算法。讲座还提出了计算该算法时间复杂度的主方法。然而，当讨论系数b时——根据我的理解，它指的是子问题大小减少的因素——它被赋值为2。

我的问题是:既然2n × n矩阵递归地分为8个n/2 × n/2矩阵，为什么b的值是2而不是4?

提前感谢!

Answer 1

复杂度符号O(n³)中的n与n×n中的n相同，因此复杂度表示为矩阵一维大小的函数。因为它在每次递归中减半，所以b等于2。

你可以看到，朴素算法实际上是通过三个嵌套循环的大小n(一行/列的长度)，而不是n×n(整个矩阵的大小)，所以这似乎是正确的。