二维矩阵计算的复杂度

两个二维矩阵相乘

A矩阵大小为M*N，B矩阵大小为N*L，A*B的代码如下：

def multiply(A, B):

    C = np.zeros((M, L))

    for m in range(M):

        for l in range(L):

            for n in range(N):

                C[m][l] += A[m][n] * B[n][l]

三个for循环，可得复杂度为：O(MNL)

三个二维矩阵相乘

令C矩阵大小为L*N，则A*B*C的复杂度计算可分为两步：

A*B结果大小为M*L，复杂度为O(MNL)

(A*B)*C结果大小为M*N，复杂度为O(MLN)

因此最终的复杂为O(MNL)

ref:

https://liwt31.github.io/2018/10/12/mul-complexity/

https://www.zhihu.com/question/390206363/answer/1348007780