矩阵乘法的时间复杂度

Question

我在理解时间复杂度方面遇到了麻烦。有些人可以直接看算法并准确地说出它的时间复杂度，但我做不到这一点。

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

有人能用易懂的语言解释一下吗？我知道theta是什么，知道big O是什么，但我就是无法应用它们。

如果你能提供另一个类似上面的简单例子，那将不胜感激。

- rakamakafo

---

以非常广泛的方式来说，你需要运行两个for循环来遍历所有需要计算的C单元格，还需要一个for循环来进行计算 -> 3个for循环 -> O(n³)。 - Isac

第一个FOR循环：遍历A的行，第二个FOR循环：遍历B的列，第三个FOR循环是加法，对吧？你能即时理解吗？还是你必须快速编写算法以查看复杂度？ - rakamakafo

其实你需要将代码可视化才能看到它的复杂性。如果你已经熟记于心，那么你可以在脑海中想象出来。看一下这个带有Java矩阵乘法的SO答案，并查看其中的3个for循环。 - Isac

Answer 1

简单来说，您的矩阵C有n x n个单元格，需要进行n^2次操作才能处理所有单元格。计算每个单元格（如c11）需要n次操作。因此，总共需要O(n^3)的时间复杂度。

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

熟能生巧。多尝试更多的问题，您就会擅长它。此外，Facebook有一个名为codelab的面试准备工具，可帮助您提高相关技能。

希望这可以帮到您！

- Khang Vu

---

我们可以这样说吗？单元格C11需要n+(n-1)次操作，即O(n)，然后计算C的第一行是n*(2n-1)，即O(n2)。然后计算C的所有行需要nn(2n-1)，即O(n3)。这样说对吗？ - rakamakafo

@Sher：你的想法听起来不错，但我建议你不要过于深入地解释为什么单元格C11需要2n-1个操作。知道这一点很好，但是当你有更多的循环需要计算时，这可能会让你感到困惑，特别是在计算如此精确的答案时。此外，在许多情况下，如果你不假设它是最佳情况或最坏情况，你就无法计算出确切的值。例如，在线性搜索中，我们需要从1到n循环查找一个值k。如果k是第一个元素，则只需要1次操作。但如果k是最后一个元素，则需要n次操作。 - Khang Vu

@Sher：此外，这可能会有所帮助：https://dev59.com/enVD5IYBdhLWcg3wXaYd?answertab=votes#tab-top - Khang Vu