我很难理解时间复杂度。人们可以看算法,直接说它的时间复杂度是多少,但我做不到。
考虑两个 n * n
矩阵(A
和 B
)。它们的乘法结果是C
。
因此,C11
的值由 n 次乘法和 n-1 次加法组成。为什么它的时间复杂度是O(n^3)
?我会说 O(n^2)
。
谁能用通俗易懂的语言解释一下?我知道什么是 theta,我知道什么是大 O,但我就是无法实现这些东西。
如果您提供另一个与上述类似的简单示例,我们将不胜感激。
最佳答案
简单地说,您的矩阵 C 有 n x n
个单元格,这需要对所有单元格进行 n^2
操作。单独计算每个单元格(如 c11
)需要 n
操作。所以这总共需要 O(n^3)
时间复杂度。
你说在 C 中计算一个单元格(如 c11
)需要 n^2
是不正确的。计算 c11 需要从 1 循环到 n(将其写在纸上,您会看到),这是 O(n)
时间复杂度。
熟能生巧。只要尝试更多的问题,你就会很擅长。此外,Facebook 有一个名为 codelab 的面试准备工具。为您改进那些相关的东西。
希望这对您有所帮助!
关于algorithm - 矩阵乘法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46821492/