1 CC30A Algoritmos y Estructuras de DatosUniversidad de Chile Facultad de Ciencias Físicas y Matemáticas Escuela de Ingeniería y Ciencias CC30A Algoritmos y Estructuras de Datos Dividir para reinar Tabulación
2 Dividir para reinar Multiplicación de dos polinomiosProblema: multiplicar dos polinomios de grado n-1. A(x)=a0+a1x+a2x2+…+an-1xn-1 B(x)=b0+b1x+b2x2+…+bn-1xn-1 C=A(x)*B(x).
3 Dividir para reinar Multiplicación de dos polinomiosSolución trivial O(n2): float[] c=new float[2*n-1]; // inicializar c[k] en 0 for (i=0; i
4 Dividir para reinar Multiplicación de dos polinomiosAlgoritmo más eficiente: separar cada polinomio en 2 partes. Ejemplo:
5 Dividir para reinar Multiplicación de dos polinomiosEn general: El grado de cada polinomio de la suma es (n/2)-1.
6 Dividir para reinar Multiplicación de dos polinomiosPor lo tanto: Esto se puede implementar con 4 multiplicaciones de polinomios de tamaño n/2, más kn sumas (para algún k).
7 Dividir para reinar Multiplicación de dos polinomiosEl número total de operaciones T(n) se puede escribir como: ¿Qué complejidad temporal tiene el algoritmo?
8 Dividir para reinar Multiplicación de dos polinomiosSe resolverá la ecuación: “Desenrollando” la ecuación:
9 Dividir para reinar Multiplicación de dos polinomiosEn general: Si p>q (nuestro caso):
10 Dividir para reinar Multiplicación de dos polinomiosEscoger j tal que qj=n (o sea, j=logqn): Pero:
11 Dividir para reinar Multiplicación de dos polinomiosPor lo tanto, el algoritmo demora: Aplicando el resultado a nuestra ecuación, donde p=4 y q=2: El resultado no es muy interesante…
12 Dividir para reinar Multiplicación de dos polinomiosPERO si se calcula: Entonces: Requiere 3 multiplicaciones recursivas.
13 Dividir para reinar Multiplicación de dos polinomiosPor lo tanto: Ejercicio: demostrar T(n) en los casos: p p=q = (n log n)
14 Recursividad y tabulaciónNo siempre la recursividad es eficiente. Ejemplo: cálculo de números de Fibonacci.
15 Recursividad y tabulaciónTabla de valores:
16 Recursividad y tabulaciónSolución recursiva: int F(int n) { if (n<=1) return n; else return F(n-1)+F(n-2); }
17 Recursividad y tabulaciónEsto resulta muy ineficiente. Si T(n) representa el número de sumas ejecutadas para calcular fn, se tiene: T(0)=0 T(1)=0 T(n)=1+T(n-1)+T(n-2)
18 Recursividad y tabulaciónTabla de valores para T(n): ¿T(n)=fn-1? Si. (Ejercicio: demostrarlo).
19 Recursividad y tabulaciónLuego, el tiempo crece de manera exponencial (muy lento). El problema es que se está recalculando una y otra vez los mismos valores (ver dibujo en pizarra). Una forma de evitar esto es anotar los valores calculados en un arreglo.
20 Recursividad y tabulaciónEl arreglo debe llenarse de manera ordenada: int F(int n) { int fib[n+1]; fib[0]=0; fib[1]=1; for (i=2; i<=n; ++i) fib[i]=fib[i-1]+fib[i-2]; }
21 Recursividad y tabulaciónTiempo del nuevo algoritmo: O(n). Esta idea se llama programación dinámica cuando se usa para resolver problemas de optimización. ¿Es posible calcular fn más rápido que O(n)? Respuesta: Si.
22 Recursividad y tabulaciónSe tiene que: Se define una función auxiliar g tal que:
23 Recursividad y tabulaciónCon esto se plantea el siguiente sistema de ecuaciones:
24 Recursividad y tabulaciónAn-1 se puede calcular por el método eficiente => Tiempo: O(log n).