algorithm - 击败 Strassen 算法的算法

Question

Caesar 教授希望开发一种矩阵乘法算法，该算法在渐近上比 Strassen 算法更快。他的算法将使用分而治之的方法，将每个矩阵分成大小为 n/4 xn/4 的块，并且分而治之的步骤将花费 Theta(n^2) 时间。

Answer 1

您并没有真正说明这里的问题是什么，但我想这是为了证明这个微不足道的算法比 Strassen 运行得更快。

假设您将矩阵划分为每个维度(n / k) X (n / k)的块（在您的问题中，k是 4）。那么每个矩阵会有k ²个块，并且会有k ^{3 个}块乘法（第一个矩阵中的每个块将乘以第二个矩阵中的k个块）。因此，复杂性递归是

T(n) = k ³ T(n / k) + Θ(n ² )。

根据Master 定理的情况 1，这意味着

T(n) = Θ(n ^{log _k (k 3 )} ) = Θ(n ³ )。

这与普通的矩阵乘法相同。显然，它没有击败施特拉森。