algorithm - 矩阵乘法的时间复杂度

Question

我很难理解时间复杂度。人们可以看算法，直接说它的时间复杂度是多少，但我做不到。

考虑两个 n * n 矩阵(A 和 B)。它们的乘法结果是C。因此，C11 的值由 n 次乘法和 n-1 次加法组成。为什么它的时间复杂度是O(n^3)？我会说 O(n^2)。

谁能用通俗易懂的语言解释一下？我知道什么是 theta，我知道什么是大 O，但我就是无法实现这些东西。

如果您提供另一个与上述类似的简单示例，我们将不胜感激。

Answer 1

简单地说，您的矩阵 C 有 n x n 个单元格，这需要对所有单元格进行 n^2 操作。单独计算每个单元格(如 c11)需要 n 操作。所以这总共需要 O(n^3) 时间复杂度。

你说在 C 中计算一个单元格(如 c11)需要 n^2 是不正确的。计算 c11 需要从 1 循环到 n(将其写在纸上，您会看到)，这是 O(n) 时间复杂度。

熟能生巧。只要尝试更多的问题，你就会很擅长。此外，Facebook 有一个名为 codelab 的面试准备工具。为您改进那些相关的东西。

希望这对您有所帮助!