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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

La recurrencia se comporta como en la última línea de la ecuación. Si se itera la ecuación hasta que
n = k y T (0)= (1) definimos ; la suma se puede ver que representa la suma de la sucesión de
números enteros positivos, por lo que esta se puede representar como un polinomio de segundo
grado, por lo tanto, Al sustituir en la ecuación, se tiene:

Método MaeStro

El método maestro es una “receta de cocina” para resolver, como se mencionó anteriormente, recu-
rrencias de la forma

donde, a > 1, b > 0 son constantes y f (n) es una función asintóticamente positiva. Una recurrencia
de esta forma describe el tiempo de ejecución de un algoritmo que divide un problema de tamaño
n en a subproblemas, cada uno de tamaño n/b. Los a subproblemas se resuelven recursivamente,
cada uno en tiempo T (n/b). La función f (n) comprende el costo de dividir el problema y combinar los
resultados de los subproblemas. El método maestro depende del teorema maestro:

Teorema maestro: Sean las constantes a > 1, b > 0 y , la función f (n) y T (n) definida en los enteros
no negativos por la recurrencia

donde se interpreta a n/b, ya sea como [n/b] o [n/b]. Entonces, T (n) tiene las siguientes cotas asin-
tóticas:

211