对于大小为 kxk 的矩阵，Strassen 算法需要进行多少次浮点运算？
我试图理解 对乘 kxk 矩阵的 Strassen 算法的分析。但我仍然不太清楚涉及多少操作。有人可以帮忙澄清一下吗？
I am trying to understand this analysis of Strassen's algorithm for multiply k x k matrices. But I am still not too sure how many operations are invovled. Can someone help clarify this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
执行的操作的数量确定如下。首先，我们将矩阵分成四个大小为 k/2 的子矩阵，然后对这些矩阵执行七次递归乘法。然后，我们不断添加这些产品以获得我们想要的结果。这给我们一个定义如下的递推关系：
T(1) = 1
T(k) = 7T(k/2) + ck2
注意 lg 7 > 2，因为lg 7 > lg 4 = 2。（这里，lg 是二进制对数）。因此，根据主定理之一，算法的渐近复杂度为 O(klg 7) ≈ O(k2.807)。
希望这有帮助！
The number of operations performed is determined as follows. First, we split the matrix up into four sub strives of size at k/2, and then perform seven recursive multiplications of those matrices. We then do a constant number of additions of those products to get our desired result. This gives us a recurrence relation defined as follows:
T(1) = 1
T(k) = 7T(k/2) + ck2
Note that lg 7 > 2, since lg 7 > lg 4 = 2. (Here, lg is the binary logarithm). Thus by case one of the Master theorem, the asymptotic complexity of the algorithm is O(klg 7) ≈ O(k2.807).
Hope this helps!
鉴于页面上说它大约是 O(N^2.807...) 我猜这将是浮点运算数量的一个很好的近似值。所有循环/迭代都将使用整数运算。
Given the page says it is approximately O(N^2.807...) I would guess that would be a good approximation of the number of floating-point operations. All the looping/iterating will be with integer operations.