5.3.3. Multiplicación encadenada de matrices.

• Si n=1 ó n=2, T(n) = 1.

• Si nɮ, entonces podemos realizar la primera multiplicación por n-1 sitios distintos: (M1M2 ... Mi)(Mi+1Mi+2... Mn)

• T(n) = ? T(i)·T(n-i)

i=1..n-1

• El valor de T(n) está en ?(4n/n2)

• Para cada ordenación necesita un tiempo de ?(n).

• Esta solución requeriría un tiempo con una cota inferior de ?(4n/n).

Solución utilizando programación dinámica

Definimos NMulti (i, j): el número mínimo de productos escalares necesarios para realizar la multiplicación entre la matriz i y la j (con i ? j), es decir: Mi x Mi+1 x ... x Mj

• Suponemos que las dimensiones se almacenan en un array d[0..n], donde la matriz Mi será de dimensión d[i-1] x d[i].

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica