矩阵乘法的时间复杂度
Time complexity of matrix multiplication
我很难理解时间复杂度。人家看算法直接说时间复杂度是多少，我做不好
考虑两个 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 的面试准备工具，供您改进这些相关内容。
希望对您有所帮助！
我很难理解时间复杂度。人家看算法直接说时间复杂度是多少，我做不好
考虑两个 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 的面试准备工具，供您改进这些相关内容。
希望对您有所帮助！