击败斯特拉森算法的算法

Question

Caesar教授希望开发一种矩阵乘法算法渐近地比Strassen算法快。他的算法将使用分治法，将每个矩阵分成大小为n/4 x n/4的小块，并且将除法和合并步骤放在一起将花费Theta(n^2)时间。

Answer 1

你并没有明确指出这里的问题是什么，但我猜这是为了反驳这个微不足道的算法比Strassen运行得快。

假设你把你的矩阵分成维度(n/k) X (n/k)的块(在你的问题中，k是4)。那么每个矩阵将有k²块，并且将有k³块乘法(第一个矩阵中的每个块将乘以第二个矩阵中的k块)。因此，复杂度递归式为

T (n) = k <一口> 3 T (n/k) +θ;(n <一口> 2>

根据主定理的情形1，这意味着

T (n) =θ;(n <一口>日志<子> k (k <一口> 3> =θ;(n <一口> 3>

这和普通矩阵乘法是一样的。显然，它无法打败Strassen。