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

Question

我想了解this analysis of Strassen's algorithm乘法k×k矩阵。但我仍然不太确定有多少操作被调用。有人可以帮助澄清这一点？

Answer 1

鉴于页面显示它大约为O（N^2.807 ...），我想这应该是浮点运算数的一个很好的近似值。所有循环/迭代都将使用整数运算。

Answer 2

执行的操作次数如下确定。首先，我们将矩阵分成四个大小为k/2的子小块，然后对这些矩阵执行7次递归乘法。然后，我们会不断增加这些产品以获得理想的结果。这给了我们所定义的递推关系如下：

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）。

希望这会有所帮助！