我想出了一种矩阵乘法算法。我在某个地方读到过矩阵乘法的时间复杂度是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]
我想出了一种矩阵乘法算法。我在某个地方读到过矩阵乘法的时间复杂度是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]
这个朴素算法,即在评论中进行更正后得到的算法,时间复杂度为O(n^3)。
确实存在可以将时间复杂度降低的算法,但你不太可能找到一个O(n^2)的实现。我相信目前最有效的实现方法仍然有待研究。
有关更多信息,请参见维基百科关于矩阵乘法的文章。
n
是需要相乘的(方)矩阵的大小,每个矩阵的大小都是 (n,n)
。
需要注意的是,由于必须读取两个矩阵中的每个数字才能进行乘法运算,所以时间复杂度最佳情况下为 O(n^2)。 - Joseph Budin标准的m行n列矩阵和n行p列矩阵相乘的复杂度是O(mnp)。如果这些对你来说都是“n”,那它的复杂度是O(n^3),而不是O(n^2)。编辑:在一般情况下,复杂度并非O(n^2)。但对于特定类型的矩阵,有更快的算法——如果你了解更多,可能会做得更好。
在矩阵乘法中,由于每个循环的执行需要时间复杂度为O(n)
,因此我们使用了三个循环。因此,对于三个循环,时间复杂度变为O(n^3)
。
最近我在大学作业中遇到了一个矩阵乘法问题,以下是我如何用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();
}
}
}
b[i][k]
看起来不对。我猜你想要在最后一行的右边加上类似于c[i][j] + a[i][k] * b[k][j]
的东西。 - Mark Dickinsoni
,在每个j
中计算的结果在c[i][j]
中相同,因此在您的输出矩阵c
中,所有列都将是相同的。您需要在最后一行中用b[k][j]
替换b[i][k]
。 - Mark Dickinson