3.3.2. Multiplicación rápida de matrices.
Supongamos el problema de multiplicar dos matrices cuadradas A, B de tamaños nxn.
C = AxB; C(i, j) = ? A(i, k)·B(k, j); Para todo i, j= 1..n
El método clásico de multiplicación de matrices requiere O(n3).
Aplicando divide y vencerás, cada matriz es dividida en cuatro submatrices de tamaño (n/2)x(n/2): Aij, Bij y Cij.
- Es necesario resolver 8 problemas de tamaño n/2. La combinación de los resultados requiere un tiempo de O(n2).
- Resolviéndolo obtenemos que t(n) es O(n3).
- Podemos obtener una mejora si hiciéramos 7 multiplicaciones (o menos).