¿Cómo se les ocurre la fórmula para la multiplicación de matrices de Strassen?

Answer 1

Para obtener la fórmula, vea ¿Cómo extrajo Strassen su algoritmo de multiplicación de matrices? Puede ser útil escribir las matrices de bloques como abcd en lugar de Aij.

Si la dimensión de la matriz no es una potencia de 2, redondea a una potencia de 2 rellenando la matriz con 0s para que la fórmula sea la misma. Al implementar, sería útil dividir y almacenar las matrices para que los 0 rellenados sean implícitos en lugar de asignar memoria para esos 0, lo que puede ahorrar algunos pasos en subproblemas más pequeños. Aún así, en el peor de los casos cuando N es simplemente mayor que una potencia de 2, la complejidad es aproximadamente O ((2N) ^ Log7), que sigue siendo O (N ^ Log7).

Probablemente no se le preguntarán problemas sobre operaciones matemáticas rápidas en entrevistas. Este problema demuestra la técnica de dividir y conquistar, pero es más probable que se le pida que aplique la técnica a las estructuras de datos.