我的CS老师要求我们在此代码中“添加一个小更改”，以使其与

Question

的时间复杂性一起运行，而不是正常的

N3。我一生无法弄清楚，我想知道是否有人知道。我认为他不是在谈论Strassens方法。 从我看着它时，也许它可以利用他只关心正方形（对角线）矩阵的事实。

void multiply(int n, int A[][], int B[][], int C[][]) {
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            C[i][j] = 0;
            for (int k = 0; k < n; k++)
            {
                C[i][j] += A[i][k]*B[k][j];
            }
        }
    }
}

^您无法在o（n2

）

中实现矩阵乘法。但是，您可以提高

o（n

Answer 1

）

的复杂性。在线性代数中，存在诸如strassen算法之类的算法，它通过减少每种2x2 sub-matrix所需的乘数数量来将时间复杂性降低到^o（N2.8074） coppersmith – Winograd算法的改进版本是已知最快的矩阵乘法算法，具有最佳的时间复杂性（N2.3729）。 他的意思是n^3-n^2，这与n^2

不同