programacion - strassen algorithm
algoritmo de multiplicación de matriz complejidad de tiempo (4)
El algoritmo ingenuo, que es lo que tienes una vez que lo corrijas como se indica en los comentarios, es O (n ^ 3).
Existen algoritmos que reducen esto un poco, pero no es probable que encuentre una implementación O (n ^ 2). Creo que la cuestión de la implementación más eficiente todavía está abierta.
Vea este artículo de wikipedia sobre la multiplicación de matrices para más información.
Se me ocurrió este algoritmo para la multiplicación de matrices. Leí en alguna parte que la multiplicación de matrices tiene una complejidad temporal de o (n ^ 2). Pero creo que mi algoritmo me dará o (n ^ 3). No sé cómo calcular la complejidad del tiempo de los bucles anidados. Así que por favor corrígeme.
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]
En la multiplicación de matrices hay 3 para bucle, estamos usando ya que la ejecución de cada bucle for requiere complejidad de tiempo O(n) . Así que para tres bucles se convierte en O(n^3)
La manera estándar de multiplicar una matriz m por n por una matriz n por p tiene complejidad O (mnp). Si todos esos son "n" para usted, es O (n ^ 3), no O (n ^ 2). EDITAR: no será O (n ^ 2) en el caso general. Pero existen algoritmos más rápidos para determinados tipos de matrices: si sabe más, puede hacerlo mejor.
Usando el álgebra lineal, existen algoritmos que logran una mayor complejidad que el ingenuo O (n 3 ). El algoritmo de Solvay Strassen logra una complejidad de O (n 2.807 ) al reducir el número de multiplicaciones requeridas para cada sub-matriz de 2x2 de 8 a 7.
El algoritmo de multiplicación de matriz más rápido conocido es el algoritmo Coppersmith-Winograd con una complejidad de O (n 2.3737 ). A menos que la matriz sea enorme, estos algoritmos no producen una gran diferencia en el tiempo de cálculo. En la práctica, es más fácil y rápido utilizar algoritmos paralelos para la multiplicación de matrices.