Teorema maestro

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

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 número 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 ${\displaystyle 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: ${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)}$ . Esta relación de recurrencia puede ser sucesivamente sustituida en sí 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

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

${\displaystyle 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 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.

Luego, es posible realizar una cota en notación Big O en los siguientes tres casos:

Caso 1

Forma Genérica

Si ${\displaystyle f(n)=O\left(n^{c}\right)}$  donde ${\displaystyle c<\log _{b}a}$  (usando Cota superior asintótica)

entonces:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}$ 

Ejemplo

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

Como puede verse en la fórmula de arriba:

${\displaystyle a=8,\,b=2,\,f(n)=1000n^{2}}$ , entonces

${\displaystyle f(n)=O\left(n^{c}\right)}$ , donde ${\displaystyle c=2}$ 

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

${\displaystyle \log _{b}a=\log _{2}8=3>c}$ .

Luego por el teorema maestro tenemos que

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)}$ 

Caso 2

Forma Genérica

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

${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$  donde ${\displaystyle c=\log _{b}a}$ 

Entonces:

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

Ejemplo

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

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

${\displaystyle a=2}$ 

${\displaystyle b=2}$ 

${\displaystyle c=1}$ 

${\displaystyle f(n)=10n}$ 

${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$  donde ${\displaystyle c=1,k=0}$ 

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

${\displaystyle \log _{b}a=\log _{2}2=1}$ ,luego, se cumple que ${\displaystyle c=\log _{b}a}$ 

Entonces por el segundo caso del teorema maestro:

${\displaystyle 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

Forma Genérica

Si es verdad que:

${\displaystyle f(n)=\Omega \left(n^{c}\right)}$  donde ${\displaystyle c>\log _{b}a}$ 

Y si es verdad además que:

${\displaystyle af\left({\frac {n}{b}}\right)\leq kf(n)}$  para alguna constante ${\displaystyle k<1}$  y suficientemente grande ${\displaystyle n}$ 

Entonces:

${\displaystyle T\left(n\right)=\Theta \left(f(n)\right)}$ 

Ejemplo

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

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

${\displaystyle a=2,\,b=2,\,f(n)=n^{2}}$ 

${\displaystyle f(n)=\Omega \left(n^{c}\right)}$ , donde ${\displaystyle c=2}$ 

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

${\displaystyle \log _{b}a=\log _{2}2=1}$ ,y por lo tanto se cumple que, ${\displaystyle c>\log _{b}a}$ 

La condición también se cumple:

${\displaystyle 2({\frac {n^{2}}{4}})\leq kn^{2}}$ , eligiendo ${\displaystyle k=1/2}$ 

Entonces por el tercer caso del teorema maestro:

${\displaystyle 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 Θ(n²).

Casos Irresolubles

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

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

  a no es una constante; el número de subproblemas debe ser fijo.

• ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}$ 

  f(n) debe ser polinomial.

• ${\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+n}$ 

  a<1 no puede darse el caso de que haya menos de un subproblema.

• ${\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n}$ 

  f(n) que es el tiempo de trabajo, no puede ser negativo.

• ${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)}$ 

  Caso 3 pero hay una violación de regularidad.

Bibliografía

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268-270.

Véase también

• Ecuación recurrente

Referencias

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).

•   Datos: Q922367