Teorema maestro

(Redirigido desde «Teorema Maestro»)

En el análisis de algoritmos, el teorema maestro proporciona una cota superior asintótica para ecuaciones de recurrencia que ocurren en muchos algoritmos recursivos como en los divide y vencerás. Fue popularizado por el libro Introducción a los algoritmos, en el cual fue tanto introducido como probado formalmente.

No todas las ecuaciones de recurrencia pueden ser resueltas con el uso del teorema maestro, una generalización es el método Akra-Bazzi.

Introducción

editar

Considere un problema que puede ser resuelto a través de un algoritmo recursivo como el siguiente:

procedimiento p(entrada x de tamaño n):
   si n < constante k:
       Resolver x (sin recursión)
   sino:
       Dividir x en a subproblemas de tamaño n/b
   Llamar p recursivamente en cada subproblema
   Combinar los resultados de cada subproblema

Este algoritmo divide al problema original en subproblemas de forma recursiva, cada uno de estos subproblemas tienen tamaño n/b. Las llamadas recursivas podrían modelarse como un árbol de llamadas. En este caso, cada nodo tendría un número a de hijos. Cada nodo hará la cantidad de trabajo correspondiente al tamaño del subproblema   que recibe. El trabajo total realizado por todas las llamadas del árbol es la suma de los trabajos hechos por cada uno de los nodos del árbol. La relación de recurrencia resultante es la siguiente:

 .[1]

El teorema maestro nos permite acotar el tiempo de ejecución asintótico sin expandir la relación de arriba.

Forma genérica

editar

El teorema maestro sirve para resolver relaciones recursivas de la forma:

 

En la aplicación de análisis de algoritmos recursivos, las constantes y funciones toman los siguientes significados:

  • n es el tamaño del problema a resolver.
  • a es el número de subproblemas en la recursión.
  • n/b el tamaño de cada subproblema. (Aquí se asume que todos los subproblemas tienen el mismo tamaño)
  • f (n) es el costo del trabajo hecho fuera de las llamadas recursivas, que incluye el costo de la división del problema y el costo de unir las soluciones de los subproblemas.

Caso 1

editar

Forma Genérica

editar

Si   donde  

entonces:

 

Ejemplo

editar
 

Como puede verse en la fórmula de arriba:

 , entonces
 , donde  

Luego, vemos que se cumple la condición del caso 1:

 .

Luego por el teorema maestro tenemos que

 

Caso 2

editar

Forma Genérica

editar

Si  

entonces:

 

Ejemplo

editar

 

Como podemos ver en la fórmula de arriba, las variables tienen los siguientes valores:

 
 
 
 
  donde  

Luego, nos fijamos que cumpla la condición del caso 2:

 ,luego, se cumple que  

Entonces por el segundo caso del teorema maestro:

 

Dando de esa manera que la relación de recurrencia de T(n) es Θ(n log n).

Caso 3

editar

Forma Genérica

editar

Si es verdad que:

  donde  

Y si es verdad además que:

  para alguna constante   y suficientemente grande  

Entonces:

 

Ejemplo

editar
 

Como puede verse en la fórmula de arriba, las variables obtienen los siguientes valores:

 
 , donde  

Luego se comprueba que satisface la condición del caso 3:

 ,y por lo tanto se cumple que,  

La condición también se cumple:

 , eligiendo  

Entonces por el tercer caso del teorema maestro:

 

Por consiguiente la relación de recurrencia T(n) es in Θ(n2).

Casos Irresolubles

editar

Los siguientes casos no pueden ser resueltos a través de la utilización del teorema maestro:[2]

  •  
    a no es una constante; el número de subproblemas debe ser fijo.
  •  
    a<1 no puede darse el caso de que haya menos de un subproblema.
  •  
    f(n) que es el tiempo de trabajo, no puede ser negativo.

Bibliografía

editar

Véase también

editar

Referencias

editar
  1. Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
  2. Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).