algoritmo di moltiplicazione della matrice complessità del tempo

Question

Mi è venuto in mente questo algoritmo per la moltiplicazione della matrice. Ho letto da qualche parte che la moltiplicazione della matrice ha una complessità temporale di o (n^2). Ma penso che il mio algoritmo darà o (n^3). Non so come calcolare la complessità temporale degli anelli annidati. Quindi per favore correggimi.

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] 

Answer 1

L'algoritmo ingenuo, che è quello che hai quando lo correggi come indicato nei commenti, è O (n^3).

Esistono algoritmi che lo riducono, ma non è probabile che si trovi un'implementazione O (n^2). Credo che la questione dell'attuazione più efficiente sia ancora aperta.

Vedere questo articolo di Wikipedia su Matrix Multiplication per ulteriori informazioni.

Answer 2

Il metodo standard di moltiplicare una matrice m-by-n da una matrice n-by-p ha complessità O (MNP). Se tutti quelli sono "n" per te, è O (n^3), non O (n^2). EDIT: non sarà O (n^2) nel caso generale. Ma ci sono algoritmi più veloci per particolari tipi di matrici - se ne sai di più potresti essere in grado di fare meglio.

Answer 3

Utilizzando l'algebra lineare, esistono algoritmi che raggiungono una complessità migliore rispetto al naive O (n). Solvay Strassen algoritmo raggiunge una complessità di O (n ^2.807) riducendo il numero di moltiplicazioni richieste per ogni sub-matrice 2x2 da 8 a 7.

L'algoritmo di moltiplicazione matrice veloce noto è Coppersmith-Winograd algoritmo con una complessità di O (n ^2.3737). A meno che la matrice non sia enorme, questi algoritmi non comportano una grande differenza nel tempo di calcolo. In pratica, è più facile e veloce utilizzare algoritmi paralleli per la moltiplicazione della matrice.

Answer 4

Nella moltiplicazione di matrice ci sono 3 per il ciclo, che stiamo usando poiché l'esecuzione di ogni ciclo per richiede la complessità temporale O(n). Quindi per tre cicli diventa O(n^3)