Page 213 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

De cada par de funciones g (n) y f (n), indique qué relación hay entre g (n) con f (n):

recurreNcIaS

Las recurrencias van de la mano con el paradigma de divide y conquistarás, porque proporcionan
una manera natural de caracterizar los tiempos de ejecución de algoritmos que aplican este para-
digma. Una recurrencia es una ecuación o desigualdad que describe una función en términos de
su valor en entradas más pequeñas. Por ejemplo, como se observa en la sección 2.4, el tiempo de
ejecución del algoritmo de ordenamiento merge sort se describe por la siguiente recurrencia:

Las recurrencias pueden tomar muchas formas. Por ejemplo, un algoritmo puede dividir subpro-
blemas en tamaños desiguales, tales como 2/3 a 1/3. Si la división y combinación de pasos toma
tiempo lineal, tal algoritmo daría esta recurrencia:

Los subproblemas no son necesariamente restringidos al ser una fracción constante del tamaño
original del problema. Por ejemplo, una versión recursiva de búsqueda lineal crearía solo un subpro-
blema conteniendo solamente un elemento menos que el problema original. Cada llamada recursiva
tomaría tiempo constante más el tiempo para el llamado recursivo, dando esta recurrencia:

A continuación, veremos tres métodos para resolver recurrencias, en donde se obtengan soluciones
asintóticas 0 y/o :

1. El método de sustitución, en donde se propone una cota y se emplea induc-
ción matemática para comprobar la solución propuesta.

2. El método iterativo, en el cual —como su nombre lo indica— se itera la función
unas cuantas veces para facilitar dar una propuesta de solución. Comúnmente se
emplean técnicas de límites de sumas para resolver las recurrencias.

207