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

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 ${\displaystyle f(n)}$ 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:

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)}$.^[1]​

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

Forma genérica

El teorema maestro sirve para resolver relaciones recursivas de la 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.

Caso 1

Forma Genérica

Si ${\displaystyle f(n)=O\left(n^{c}\right)}$ donde ${\displaystyle c<\log _{b}a}$

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 ${\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\right)}$

entonces:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\lg 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\left({\frac {n^{2}}{4}}\right)\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)=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.

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