矩阵乘法算法时间复杂度

Question

我想出了一种矩阵乘法算法。我在某个地方读到过矩阵乘法的时间复杂度是o(n^2)。 但是我认为我的这个算法将会得到o(n^3)的时间复杂度。 我不知道如何计算嵌套循环的时间复杂度，所以请纠正我。

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

- zedai

---

那个b[i][k]看起来不对。我猜你想要在最后一行的右边加上类似于c[i][j] + a[i][k] * b[k][j]的东西。 - Mark Dickinson

这里的 c[i][j] 是结果矩阵。 - zedai

那么，在这种情况下，您肯定没有进行矩阵乘法运算！请注意，对于给定的 i，在每个 j 中计算的结果在 c[i][j] 中相同，因此在您的输出矩阵 c 中，所有列都将是相同的。您需要在最后一行中用 b[k][j] 替换 b[i][k]。 - Mark Dickinson

Answer 1

使用线性代数，存在比朴素的O(n³)算法更优的算法。Solvay Strassen算法通过将每个2x2子矩阵所需的乘法次数从8降低到7，实现了复杂度为O(n^2.807)的计算。Solvay Strassen算法被认为是最早的基于分治思想设计的快速矩阵乘法算法之一。

已知最快的矩阵乘法算法是Coppersmith-Winograd算法，它的复杂度为O(n^2.3737)。除非矩阵特别大，否则这些算法在计算时间上并没有太大差异。在实践中，使用并行算法进行矩阵乘法运算更加容易和快速。

- viswanathgs

---

根据Wikipedia的介绍，2014年出现了一种矩阵乘法算法，其时间复杂度为O(n^2.3729)，而此前最快的算法是Coppersmith-Winograd算法，该算法的记录一直持续到2010年。 - Garrett

Answer 2

这个朴素算法，即在评论中进行更正后得到的算法，时间复杂度为O(n^3)。

确实存在可以将时间复杂度降低的算法，但你不太可能找到一个O(n^2)的实现。我相信目前最有效的实现方法仍然有待研究。

有关更多信息，请参见维基百科关于矩阵乘法的文章。

- Don Roby

---

已经证明了 O(n^2) 是不可能实现的。 - downhand

请问能提供引用文献吗？我之前没有看到这个结果，我想读一下证据。 - Ken Goss

@downhand 我知道这篇帖子已经快一年了，但我非常有兴趣看到证明。 - Jordan Singer

我找到的最接近的是在 https://arxiv.org/abs/1204.1111 的介绍中。 - Mr. White

@ArunJoshla 这里的 n 是需要相乘的(方)矩阵的大小，每个矩阵的大小都是 (n,n)。 需要注意的是，由于必须读取两个矩阵中的每个数字才能进行乘法运算，所以时间复杂度最佳情况下为 O(n^2)。 - Joseph Budin

Answer 3

标准的m行n列矩阵和n行p列矩阵相乘的复杂度是O(mnp)。如果这些对你来说都是“n”，那它的复杂度是O(n^3)，而不是O(n^2)。编辑：在一般情况下，复杂度并非O(n^2)。但对于特定类型的矩阵，有更快的算法——如果你了解更多，可能会做得更好。

- Sean Owen

---

这是错误的。在一般情况下，有加速的可能。 - jwg

Strassen算法？当然可以。原帖要求O(n^2)，但通常情况下这是不可能的。这就是我想表达的意思。 - Sean Owen

Answer 4

在矩阵乘法中，由于每个循环的执行需要时间复杂度为O(n)，因此我们使用了三个循环。因此，对于三个循环，时间复杂度变为O(n^3)。

- user2024721

Answer 5

最近我在大学作业中遇到了一个矩阵乘法问题，以下是我如何用O(n^2)的时间复杂度解决它的方法。

import java.util.Scanner;

public class q10 {
public static int[][] multiplyMatrices(int[][] A, int[][] B) {
    int ra = A.length; // rows in A
    int ca = A[0].length; // columns in A

    int rb = B.length; // rows in B
    int cb = B[0].length; // columns in B

    // if columns of A is not equal to rows of B, then the two matrices,
    // cannot be multiplied.
    if (ca != rb) {
        System.out.println("Incorrect order, multiplication cannot be performed");
        return A;
    } else {
        // AB is the product of A and B, and it will have rows,
        // equal to rown in A and columns equal to columns in B
        int[][] AB = new int[ra][cb];

        int k = 0; // column number of matrix B, while multiplying

        int entry; // = Aij, value in ith row and at jth index

        for (int i = 0; i < A.length; i++) {
            entry = 0;
            k = 0;

            for (int j = 0; j < A[i].length; j++) {
                // to evaluate a new Aij, clear the earlier entry
                if (j == 0) {
                    entry = 0;
                }

                int currA = A[i][j]; // number selected in matrix A
                int currB = B[j][k]; // number selected in matrix B

                entry += currA * currB; // adding to the current entry

                // if we are done with all the columns for this entry,
                // reset the loop for next one.
                if (j + 1 == ca) {
                    j = -1;
                    // put the evaluated value at its position
                    AB[i][k] = entry;

                    // increase the column number of matrix B as we are done with this one
                    k++;
                }

                // if this row is done break this loop,
                // move to next row.
                if (k == cb) {
                    j = A[i].length;
                }
            }
        }
        return AB;
    }

}

@SuppressWarnings({ "resource" })
public static void main(String[] args) {
    Scanner ip = new Scanner(System.in);

    System.out.println("Input order of first matrix (r x c):");
    int ra = ip.nextInt();
    int ca = ip.nextInt();

    System.out.println("Input order of second matrix (r x c):");
    int rb = ip.nextInt();
    int cb = ip.nextInt();

    int[][] A = new int[ra][ca];
    int[][] B = new int[rb][cb];

    System.out.println("Enter values in first matrix:");
    for (int i = 0; i < ra; i++) {
        for (int j = 0; j < ca; j++) {
            A[i][j] = ip.nextInt();
        }
    }

    System.out.println("Enter values in second matrix:");
    for (int i = 0; i < rb; i++) {
        for (int j = 0; j < cb; j++) {
            B[i][j] = ip.nextInt();
        }
    }

    int[][] AB = multiplyMatrices(A, B);

    System.out.println("The product of first and second matrix is:");
    for (int i = 0; i < AB.length; i++) {
        for (int j = 0; j < AB[i].length; j++) {
            System.out.print(AB[i][j] + " ");
        }
        System.out.println();
    }
}

}

- Aadi Kumawat

---

这不是O(n^2)。你在每个条目完成后通过重置j计数器，悄悄地添加了第三个嵌套的循环。外层循环是O(n)，内层循环是O(n^2)。 - Sean Owen

希望你的教授也没有被欺骗。 - General Grievance