Dadas dos matrices dispersas A y B, devuelve el resultado de AB.
Puede suponer que el número de columna de A es igual al número de fila de B.
1. Método ingenuo
Podemos implementar Sum (A_ik * B_kj) -> C_ij como una solución ingenua.
public int[][] multiply(int[][] A, int[][] B) { //validity check int[][] C = new int[A.length][B[0].length]; for(int i=0; i<C.length; i++){ for(int j=0; j<C[0].length; j++){ int sum=0; for(int k=0; k<A[0].length; k++){ sum += A[i][k]*B[k][j]; } C[i][j] = sum; } } return C; } |
La complejidad del tiempo es O (n ^ 3).
2. Método optimizado
De la fórmula: Suma (A_ik * B_kj) -> C_ij
Podemos ver que cuando A_ik es 0, no es necesario calcular B_kj. Entonces cambiamos los dos bucles internos y agregamos una condición de verificación 0.
public int[][] multiply(int[][] A, int[][] B) { //validity check int[][] C = new int[A.length][B[0].length]; for(int i=0; i<C.length; i++){ for(int k=0; k<A[0].length; k++){ if(A[i][k]!=0){ for(int j=0; j<C[0].length; j++){ C[i][j] += A[i][k]*B[k][j]; } } } } return C; } |
Dado que la matriz es escasa, la complejidad del tiempo es ~ O (n ^ 2) que es mucho más rápido que O (n ^ 3).
