Question

经典的矩阵乘法

问题：计算两个 n×n 的矩阵 A×B = C 的矩阵乘法的计算复杂度（大 O ）是多少？

你可以在 Codecademy 学习（或复习）大 O 。

它的样子是：

for i=1 to n
    {read row i of A into fast memory}
    for j=1 to n
        {read col j of B into fast memory}
        for k=1 to n
            C[i,j] += A[i,k] x B[k,j]
        {write C[i,j] back to slow memory}

问题：进行了多少次读写操作？

分块矩阵相乘

将 A ， B ， C 分成大小为 N/n × N/n 的 N×N 个块。

来源

它的样子是：

for i=1 to N
    for j=1 to N
        for k=1 to N
            {read block (i,k) of A}
            {read block (k,j) of B}
            block (i,j) of C += block of A times block of B
        {write block (i,j) of C back to slow memory}

问题 1：这个的大 O 是什么？

问题 2：进行了多少次读写操作？