algorithm - 求矩阵的立方的时间复杂度是多少？

Question

我知道直接将两个矩阵 AxB 相乘的复杂度是 O(n^3)。因此，即使我们试图找到矩阵的平方，这也适用，因为这本质上意味着 AxA。

当您试图找到矩阵的立方体时，复杂性是多少？

Answer 1

它是 O(n ³ )

为什么？

• 您可以使用两个矩阵乘法计算立方体。
• 对方阵进行矩阵乘法不会改变 n。
• 连续执行两个 O(n ³ ) 操作也是 O(n ³ )。

有关正式定义，请参见Wikipedia。