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

Question

我试图理解Strassen 的乘法 kxk 矩阵算法的分析。但我仍然不太确定涉及多少操作。有人可以帮助澄清这一点吗？

Answer 1

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

T(1) = 1

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

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

希望这可以帮助！

Answer 2

鉴于页面上说它大约是 O(N^2.807...) 我猜这将是浮点运算数量的一个很好的近似值。所有循环/迭代都将使用整数操作。