algorithm - 对于大小为 k x k 的矩阵，Strassen 算法有多少浮点运算？

Question

我正在努力理解 this analysis of Strassen's algorithm用于乘以 k x k 矩阵。但是我仍然不太确定涉及多少操作。有人可以帮助澄清这一点吗？

Answer 1

执行的操作数按如下方式确定。首先，我们将矩阵分成四个大小为 k/2 的子矩阵，然后对这些矩阵执行七次递归乘法。然后我们对这些产品进行恒定数量的添加以获得我们想要的结果。这给了我们定义如下的递归关系:

T(1) = 1

T(k) = 7T(k/2) + ck²

请注意 lg 7 > 2，因为 lg 7 > lg 4 = 2。(这里，lg 是二进制对数)。因此，根据情况之一 Master theorem ，算法的渐近复杂度为O(k^{lg 7}) ≈ O(k^2.807)。

希望这对您有所帮助!