DR. JOSÉ MARTÍNEZ CARRANZA
CIENCIAS COMPUTACIONALESINAOE
Análisis y Diseño de AlgoritmosRecurrencias
2
Introducción
Cuando un algoritmo se llama a sí mismo Su tiempo de ejecución se puede describir con una recurrencia
Recurrencia Ecuación o inigualdad que describe una función en términos
de su valor para entradas más pequeñas
Ejemplo de QuickSort
Cuya solución se es:
2
T (n)={Θ(1) if n = 1,2T (n/2 )+Θ (n ) if n > 1, }
T (n)=Θ (n lg n )
3
Introducción
Métodos para resolver recurrencias Substitución
Adivinar una cota, prueba con inducción matemática
Método de Iteración Expande, itera sobre la recurrencia y la expresa como sumatoria en
términos dependientes de n y las condiciones iniciales
Árboles de recursión Convierte la recurrencia en un árbol cuyos nodos representan los costos
de los dif. niveles de la recursión
Método maestro Provee fronteras (bounds) para recurrencias de la forma
Requiere memorizar tres casos
3
T (n)=aT (n/b )+f (n ), donde a ≥ 1, b ≥ 1, f ( n) es una función dada
4
Método de Substitución
Consta de 2 pasos Adivinar la forma de la solución Utilizar inducción matemática para encontrar las constantes y
mostrar que la solución funciona
Método poderoso Solo se aplica a casos en que es fácil adivinar la
forma de la respuesta Para establecer fronteras superiores o inferiores en
una recurrencia
4
5
Método de Substitución
Ejemplo: Adivinamos: Probamos que: para una constante c >0 Entonces: Substituimos en la recurrencia:
El último paso es cierto si c 1
5
Asumimos que lacota es cierta
para n/2
6
Método de Substitución
El método de inducción requiere probar que la solución escierta para las condiciones frontera Elegir c suficientemente grande para que funcione para
las condiciones de frontera Para notación asintótica requerimos probar que
nosotros elegimos n0
Evitamos condición frontera difícil para T(1) = 1 para la prueba de inducción
6
T (1)=1 ; La recurrencia no funciona para T (1) ; pero sí para T (2) y T (3 )T (2)=2T (1 )+2=4T (3)=2T (1)+3=5T (2) ≤ c 2lg2=2c, c ≥ 2T (3) ≤ c 3lg3=4 . 75c, c ≥ 2
7
Método de Substitución
Adivinando una buena primera aproximación No hay una buena manera general de adivinar soluciones
correctas a recurrencias Requiere experiencia y creatividad Algunas heurísticas
Usar árboles de recursión para generar buenos valores iniciales Si la recurrencia es similar a otra, usar una solución similar
7
Método de Iteración
No requiere adinivinar la respuesta Puede requerir más álgebra que el de substitución Expande (itera) la recurrencia y la expresa como sumatoria de términos
dependientes de n y las condiciones iniciales Después usa técnicas para evaluar sumatorias para dar cotas a la
solución Puede ser difícil resolver recurrencias con éste método
A veces al iterar la recurrencia, adivinamos una solución y seguimos con el método de substitución
8
Método de Iteración
Ejemplo, dada la recurrencia:
9
Método de Iteración
¿Qué tanto iteramos para llegar a la condición de frontera? El i’ésimo término en la serie es 3i n/4i La iteración llega a n = 1 cuando n/4i =1 ó cuando i excede
log4n Llevando la iteración a este punto y usando la frontera: n/4i n/4i , descubrimos que la sumatoria contiene una serie geométrica decreciente:
10
11
Método de Árbol de Recursión
Visualizar la iteración de una recurrencia Dibujar un árbol de recursión y obtener una buena solución
inicial Utilizamos método de sustitución para comprobar
Árbol de recursión Cada nodo representa el costo de un subproblema en el
conjunto de llamadas a funciones recursivas Sumamos costos por nivel y determinamos el costo total de
todos los niveles de recursión Útiles cuando la recurrencia describe tiempo de ejecución de
un algoritmo divide-y-conquista
11
12
Método de Árbol de Recursión
Para resolver la recurrencia Creamos árbol de recursión para Incluímos el coeficiente c > 0 Asumimos que n es una potencia exacta de 4
12
T (n)=3T ( ⌊n /4 ⌋)+Θ (n2 )
T (n)=3T (n /4 )+cn2
13
Método de Árbol de Recursión13
14
Método de Árbol de Recursión14
15
Método de Árbol de Recursión
El tamaño del problema decrece con la profundidad del árbol Eventualmente alcanzamos condición frontera
¿Qué tan lejos de la raíz llegamos? El tamaño del subproblema para un nodo en profundidad i es
n/4i
El tamaño llega a n = 1 cuando n/4i = 1, o i = log4n Entonces el árbol tiene log4n+1 niveles (0, 1, 2, …, log4n)
15
16
Método de Árbol de Recursión
Después determinamos el costo en cada nivel del árbol Cada nivel tiene tres veces más nodos que el nivel anterior El número de nodos a profundidad i es 3i
Cada nodo a profundidad i para i = 0, 1, 2, …, log4n-1 tiene costo de c(n/4i)2
Multiplicando, vemos que el costo de todos los nodos al nivel i para i = 0, 1, 2, …, log4n-1 es 3ic(n/4i)2 = (3/16)icn2
El último nivel a profundidad log4n tiene 3log4n = nlog4 3 nodos, cada uno con costo T(1), con costo total nlog4 3 T(1) con (nlog4 3 )
17
Método de Árbol de Recursión
Sumamos los costos de todos los niveles para obtener el costo de todo el árbol
17
18
Método de Árbol de Recursión
Podemos usar una serie geométrica infinita decreciente como cota superior, ecuación A.6
19
Método Maestro
Receta para recurrencias del tipo: a 1 y b > 1 son constantes y f(n) es una función
asintóticamente positiva
La recurrencia describe el tiempo de ejecución de un algoritmo que: Divide un problema de tamaño n en a subproblemas Cada subproblema de tamaño n/b a y b son constantes positivas Los a subproblemas se resuelven recursivamente
En tiempo T(n/b)
Costo de dividir el problema y combinar los resultados esta dado por f(n)
19
20
Método Maestro
Teorema maestro Sean a 1 y b 1 constantes
Sea f(n) una función
Sea T(n) definida por los enteros no-negativos por la recurrencia
n/b puede ser n/b ó n/b, entonces T(n) se puede acotar asintóticamente como sigue:
21
Método Maestro
En todos los casos compara f(n) con nlogba
La solución a la recurrencia la domina la mayor de las 2 funciones
Caso 1: nlogba es la mayor, la solución es T(n) = (nlogba) Caso 3: f(n) es mayor, la solución es T(n) = (f(n)) Caso 2: las dos funciones son del mismo tamaño,
multiplicamos por un factor logarítmico, T(n) = (nlogbalgn) = (f(n)lgn)
22
Método Maestro
Algunos aspectos técnicos… En el caso 1:
f(n) debe ser polinómicamente más pequeña que nlogba
Asintóticamente más pequeñaque nlogba por un factor de n para una constante > 0.
En el caso 3: f(n) debe ser polinómicamente mayor a nlogba
También debe satisfacer la condición de regularidad de af(n/b) cf(n) Esta condición se satisface por la mayoría de las funciones
polinómicamente acotadas que podemos encontrar. Esto quiere decir que los 3 casos no cubren todas las posibilidades de f(n).
22
23
Método Maestro
Ejemplo 1:
23
24
Método Maestro
Ejemplo 2:
24
25
Método Maestro
Ejemplo 3:
25
26
Método Maestro
Ejemplo 4:
26
Top Related