Encuentre la complejidad computacional
Cuando hablamos del tiempo de ejecución del algoritmo, es convencional dar la función más simple AsymptoticEqual ( grande) para la función de tiempo exacto de ejecución. Otra forma de establecer esta igualdad es que cada función sea tanto AsymptoticLessEqual (
grande) y AsymptoticGreaterEqual (
grande) que la otra. Estos conceptos son ilustrados en el contexto del algoritmo de Strassen, el primer algoritmo de multiplicación de matriz subcúbica encontrado.
El algoritmo consiste en cuatro pasos: dividiendo cada uno de las dos matrices en 4 submatrices, formando 14 combinaciones lineales de entre las 8 submatrices, multiplicando 7 pares de estos y sumando los 7 resultados. El tiempo
para hacer la multiplicación será entonces un tiempo constante
para dividir la matriz,
para formar combinaciones lineales en el segundo y cuarto paso y
para el tercer paso.
Resuelva la relación recurrente.
Aunque el resultado es complicado, .
De la misma forma, y
.
Note que , así que el algoritmo es subcúbico.
Compare la tasa de crecimiento del algoritmo cúbico ingenuo y el algoritmo de Strassen.