1 ELO3201 Análisis de Algoritmos (cont.) Agustín J. González ELO320 1º sem 2002

2 ELO3202 Estrategia: Dividir y Conquistar Muchos algoritmos naturalmente tienen una estructura recursiva. Su estructura general es: –Dividir el problema en un número de subproblemas –Conquistar el problema resolviéndolo recursivamente. Si el problema es pequeño se resuelve en forma directa. –Combinar las soluciones de los subproblemas. Ejemplo: merge-sort : ordenar n elementos –Pasos: Dividir la secuencia de n elementos en dos subsecuencias de tamaño n/2 Ordenar las subsecuencias recursivamente usando merge-sort Combinar las soluciones parciales.

3 ELO3203 Algoritmo Merge-sort Sea A un arreglo de n elementos y p, r índices del rango a ordenar. Merge-Sort(A, p, r) if ( p < r ) { q = parteEntera((p+r)/2); Merge-Sort(A, p, q); Merge-Sort(A, q+1,r); Merge(A, p, q, r); }

4 ELO3204 Sea A un arreglo de n elementos y p, r índices del rango a ordenar. Merge-Sort(A, p, r) if ( p < r ) { q = parteEntera((p+r)/2); Merge-Sort(A, p, q); Merge-Sort(A, q+1,r); Merge(A, p, q, r); } Algoritmo Merge-sort --> T(n) -->  (1) --> T(n/2) -->  (n) ¿Cuál es el costo de este algoritmo?

5 ELO3205 Costo Merge-Sort ¿Cómo se resuelve esta recurrencia?

6 ELO3206 Teorema Maestro (Master Theorem) Sea a  1 y b  1 constantes, sea f(n) una función y sea T(n)=aT(n/b) +f(n) donde n/b es  n/b  o  n/b . Entonces T(n) puede ser acotada asintóticamente por

7 ELO3207 1 Uso del teorema maestro

8 ELO3208 2 Uso del teorema maestro

9 ELO3209 3 Uso del teorema maestro