Teorema maestro

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En el análisis de algoritmos, el teorema maestro proporciona una solución sencilla en términos asintóticos (usando una Cota superior asintótica) para ecuaciones de recurrencia que ocurren en muchos algoritmos recursivos tales como en el Algoritmo divide y vencerás. Fue popularizado por el libro Introducción a los algoritmos por Cormen, Leiserson, Rivest, y Stein, en el cual fue tanto introducido como probado formalmente. No todas las ecuaciones de recurrencia pueden ser resueltas con el uso del teorema maestro.

Introducción[editar]

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

 procedimiento T( n : tamaño del problema ) definición:
   if n < 1 then exit

Hacer trabajo f(n)

T(n/b) T(n/b) ...repetir una cantidad de a veces... T(n/b) fin procedimiento

En el algoritmo mostrado arriba se divide el problema original en una cantidad menor de subproblemas de manera recursiva, cada uno de estos subproblemas siendo del tamaño de n/b. Esto podría ser visualizado como la construcción de un árbol de llamadas al problema, siendo cada nodo del árbol una instancia recursiva del mismo y sus hijos siendo instancias de las llamadas subsiguientes. En el ejemplo de arriba, cada nodo tendría un numero a de hijos. Cada nodo hará la cantidad de trabajo correspondiente al tamaño del subproblema n, pasado a esa instancia en particular, estando la cantidad de trabajo realizado determinado por f(n). 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.

Algoritmos como el descrito arriba pueden ser representados por una relación de recurrencia como la siguiente: T(n) = a \; T\left(\frac{n}{b}\right) + f(n). Esta relación de recurrencia puede ser sucesivamente sustituida en si misma y expandida hasta obtener una expresión que represente la cantidad total de trabajo.[1]

El teorema maestro nos permite fácilmente calcular el tiempo de ejecución de este tipo de algoritmos recursivos en notación de Cota superior asintótica, sin la necesidad de hacer la expansión de las distintas llamadas recursivas.

Forma genérica[editar]

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

T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)  \;\;\;\; \mbox{donde} \;\; a \geq 1 \mbox{, } b > 1

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 en numero 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.

Luego, es posible realizar una cota en notacion Big O en los siguientes tres casos:

Caso 1[editar]

Forma Genérica[editar]

Si f(n) = O\left( n^{c} \right) donde c < \log_b a (usando Cota superior asintótica)

entonces:

T(n) = \Theta\left( n^{\log_b a} \right)

Ejemplo[editar]

T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2

Como puede verse en la formula de arriba:

a = 8, \, b = 2, \, f(n) = 1000n^2, entonces
f(n) = O\left(n^c\right), donde c = 2

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

\log_b a = \log_2 8 = 3>c.

Luego por el teorema maestro tenemos que

T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)

Caso 2[editar]

Forma Genérica[editar]

Si es verdad que para alguna constante k ≥ 0, que:

f(n) = \Theta\left( n^{c} \log^{k} n \right) donde c = \log_b a

Entonces:

T(n) = \Theta\left( n^{c} \log^{k+1} n \right)

Ejemplo[editar]

T(n) = 2 T\left(\frac{n}{2}\right) + 10n

Como podemos ver en la formula de arriba, las variables tienen los siguientes valores:

a = 2
b = 2
c = 1
f(n) = 10n
f(n) = \Theta\left(n^{c} \log^{k} n\right) donde c = 1, k = 0

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

\log_b a = \log_2 2 = 1,luego, se cumple que c = \log_b a

Entonces por el segundo caso del teorema maestro:

T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)

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:

f(n) = \Omega\left( n^{c} \right) donde c > \log_b a

Y si es verdad además que:

a f\left( \frac{n}{b} \right) \le k f(n) para alguna constante k < 1 y suficientemente grande n

Entonces:

T\left(n \right) = \Theta\left(f(n) \right)

Ejemplo[editar]

T(n) = 2 T\left(\frac{n}{2}\right) + n^2

Como puede verse en la formula de arriba, las variables obtienen los siguientes valores:

a = 2, \, b = 2, \, f(n) = n^2
f(n) = \Omega\left(n^c\right), donde c = 2

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

\log_b a = \log_2 2 = 1,y por lo tanto se cumple que, c > \log_b a

La condición también se cumple:

 2 (\frac{n^2}{4}) \le k n^2 , eligiendo  k = 1/2

Entonces por el tercer caso del teorema maestro:

T \left(n \right) = \Theta\left(f(n)\right) = \Theta \left(n^2 \right).

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]

  • T(n) = 2^nT\left (\frac{n}{2}\right )+n^n
    a no es una constante; el numero de subproblemas debe ser fijo.
  • T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}
    f(n) debe ser polinomial.
  • T(n) = 0.5T\left (\frac{n}{2}\right )+n
    a<1 no puede darse el caso de que haya menos de un subproblema.
  • T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n
    f(n) que es el tiempo de trabajo, no puede ser negativo.
  • T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)
    Caso 3 pero hay una violación de regularidad.

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