algorithm - 子问题大小 wrt Strassen 的矩阵乘法算法

Question

我最近观看了有关 Strassen 用于乘以 2 个 nxn 矩阵的递归算法的视频讲座。讲座还提出了计算该算法时间复杂度的Master Method。然而，在讨论系数 b 时——据我所知，它是指子问题大小减小的因素——它被分配了 2 的值。

我的问题是：既然 2 nxn 矩阵被递归地划分为 8 n/2 xn/2 矩阵，为什么 b 的值是 2 而不是 4？

提前致谢！

Answer 1

O(n 3 ⁾的复杂度表示法中的n与n×n中的 n相同，因此复杂度表示为矩阵一维大小的函数。由于每次递归都会减半，因此b为 2。

可以看到，朴素算法确实经过了三个大小为n（一行/列的长度）的嵌套循环，而不是n×n（整个矩阵的大小），所以这看起来是对的。