math - 矩阵和乘法复杂度

Question

我无法理解问题解决方案的时间复杂度。

令 X、Y 和 Z 为 n × n 矩阵。假设我们要验证是否 XY = Z。通过计算 XY 直接解决问题的复杂度是多少？

正确答案是 O(n ³ )，但我不明白为什么。为什么会这样？

Answer 1

计算两个 n × n 矩阵的乘积的标准算法是利用乘积中位置 (i, j) 处的条目是第一个矩阵的第 i 行和第二个矩阵的第 j 列的内积这一事实矩阵。计算这一行和这一列的内积需要时间 Θ(n)，因为有 n 个条目需要成对相乘和相加。因此，结果矩阵的每个条目都需要时间 Θ(n)。由于矩阵中总共有 n ²个条目，因此使用朴素算法的总时间复杂度为 Θ(n ³ )。

有比这里描述的更快的矩阵乘法方法使用更复杂的算法。您可能想查找 Coppersmith-Winograd 算法或 Strassen 算法，它们比朴素算法渐进地快。

但是，有更好的随机算法来检查产品是否正确。查看Frievalds 的算法，了解 O(n ² ) 时间的随机算法，该算法很有可能检测乘法是否正确。

希望这可以帮助！