java - 朴素矩阵乘法改进

Question

我的 CS 老师要求我们对此代码“添加一个小改动”，使其以 N³ - N² 的时间复杂度运行。 而不是正常的 N³。我一辈子都弄不明白，我想知道是否有人碰巧知道。我不认为他在谈论 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];
            }
        }
    }
}

Answer 1

您无法在 O(N²) 中实现矩阵乘法。但是，您可以从 O(N³) 提高复杂度。在线性代数中，有像 Strassen algorithm 这样的算法。通过将每个 2x2 子矩阵所需的乘法次数从 8 次减少到 7 次，将时间复杂度降低到 O(N^2.8074)。

Coppersmith–Winograd algorithm 的改进版本是已知最快的矩阵乘法算法，最佳时间复杂度为O(N^2.3729)。