How reduce O(n3) to almost O(n2)


  • 0
    W

    Matrix multiply formula [A]ij [B]jk = [C]ik
    cij = ai0 * b0j + ai1 * b1j + ai2 * b2j + ........ + aik * bkj, k belongs [0, j]
    So, the time complicity is O(n3).

    for(int i = 0; i < A.length; i++) {
        for(int j = 0; j < A[0].length; j++) {
            for(int k = 0; k < B[0].length; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    

    However, if A[i][j] is 0, it is not necessary to multiple A[i][k] * B[k][j] where k from 0 to j. The good idea is when A[i][j] is 0, just continue fetch the next A[i][j]. Let's modify the code as following:

        for(int j = 0; j < A[0].length; j++) {
            if(A[i][j] == 0) continue;
            for(int k = 0; k < B[0].length; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.