Teorema maestro (análisis de algoritmos)

Herramienta para analizar algoritmos de divide y vencerás

En el análisis de algoritmos , el teorema maestro para recurrencias de divide y vencerás proporciona un análisis asintótico para muchas relaciones de recurrencia que ocurren en el análisis de algoritmos de divide y vencerás . El enfoque fue presentado por primera vez por Jon Bentley , Dorothea Blostein (née Haken) y James B. Saxe en 1980, donde se describió como un "método unificador" para resolver tales recurrencias. ^[1] El nombre "teorema maestro" fue popularizado por el libro de texto de algoritmos ampliamente utilizado Introducción a los algoritmos de Cormen , Leiserson , Rivest y Stein .

No todas las relaciones de recurrencia pueden resolverse mediante este teorema; sus generalizaciones incluyen el método de Akra-Bazzi .

Introducción

Consideremos un problema que pueda resolverse utilizando un algoritmo recursivo como el siguiente:

procedimiento p(entrada x de tamaño n ): si  n < alguna constante k : Resuelva x directamente sin recursión , de lo contrario : Cree subproblemas de x , cada uno con un tamaño n / b. Llame al procedimiento p recursivamente en cada subproblema. Combine los resultados de los subproblemas

Árbol de soluciones.

El algoritmo anterior divide el problema en una serie de subproblemas de forma recursiva, siendo cada subproblema de tamaño n / b . Su árbol de soluciones tiene un nodo para cada llamada recursiva, siendo los hijos de ese nodo las otras llamadas realizadas a partir de esa llamada. Las hojas del árbol son los casos base de la recursión, los subproblemas (de tamaño menor que k ) que no recurren. El ejemplo anterior tendría un nodo hijo en cada nodo que no sea hoja. Cada nodo realiza una cantidad de trabajo que corresponde al tamaño del subproblema n pasado a esa instancia de la llamada recursiva y dado por . La cantidad total de trabajo realizado por todo el algoritmo es la suma del trabajo realizado por todos los nodos del árbol. ${\displaystyle f(n)}$

El tiempo de ejecución de un algoritmo como el p anterior en una entrada de tamaño n , generalmente denotado , se puede expresar mediante la relación de recurrencia ${\displaystyle T(n)}$

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n),}$

donde es el tiempo necesario para crear los subproblemas y combinar sus resultados en el procedimiento anterior. Esta ecuación puede sustituirse sucesivamente en sí misma y expandirse para obtener una expresión para la cantidad total de trabajo realizado. ^[2] El teorema maestro permite convertir muchas relaciones de recurrencia de esta forma a notación Θ directamente, sin hacer una expansión de la relación recursiva. ${\displaystyle f(n)}$

Forma genérica

El teorema maestro siempre produce límites asintóticamente ajustados para las recurrencias de algoritmos de dividir y vencer que dividen una entrada en subproblemas más pequeños de igual tamaño, resuelven los subproblemas recursivamente y luego combinan las soluciones de los subproblemas para dar una solución al problema original. El tiempo para un algoritmo de este tipo se puede expresar sumando el trabajo que realizan en el nivel superior de su recursión (para dividir los problemas en subproblemas y luego combinar las soluciones de los subproblemas) junto con el tiempo empleado en las llamadas recursivas del algoritmo. Si denota el tiempo total del algoritmo en una entrada de tamaño , y denota la cantidad de tiempo que se tarda en el nivel superior de la recurrencia, entonces el tiempo se puede expresar mediante una relación de recurrencia que toma la forma: ${\displaystyle T(n)}$ ${\displaystyle n}$ ${\displaystyle f(n)}$

${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}$

Aquí se muestra el tamaño de un problema de entrada, es el número de subproblemas en la recursión y es el factor por el cual se reduce el tamaño del subproblema en cada llamada recursiva ( ). Fundamentalmente, y no debe depender de . El teorema a continuación también supone que, como caso base para la recurrencia, cuando es menor que algún límite , el tamaño de entrada más pequeño que conducirá a una llamada recursiva. ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b>1}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle T(n)=\Theta (1)}$ ${\displaystyle n}$ ${\displaystyle \kappa >0}$

Las recurrencias de esta forma suelen satisfacer uno de los tres regímenes siguientes, en función de cómo se relaciona el trabajo de dividir/recombinar el problema con el exponente crítico . (La tabla siguiente utiliza la notación estándar O grande ). ${\displaystyle f(n)}$ ${\displaystyle c_{\operatorname {crit} }=\log _{b}a}$

${\displaystyle c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblems}})/\log({\text{relative subproblem size}})}$

Una extensión útil del Caso 2 maneja todos los valores de : ^[3] ${\displaystyle k}$

Ejemplos

Ejemplo de caso 1

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

Como se puede ver en la fórmula anterior:

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

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

A continuación, vemos si satisfacemos la condición del caso 1:

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

Del primer caso del teorema maestro se deduce que

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

(Este resultado se confirma mediante la solución exacta de la relación de recurrencia, que es , suponiendo ). ${\displaystyle T(n)=1001n^{3}-1000n^{2}}$ ${\displaystyle T(1)=1}$

Ejemplo de caso 2

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

Como podemos ver en la fórmula anterior las variables obtienen los siguientes valores:

${\displaystyle a=2,\,b=2,\,c=1,\,f(n)=10n}$

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

A continuación, vemos si satisfacemos la condición del caso 2:

${\displaystyle \log _{b}a=\log _{2}2=1}$, y por lo tanto, c y son iguales ${\displaystyle \log _{b}a}$

Así se deduce del 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)}$

Por lo tanto la relación de recurrencia dada estaba en . ${\displaystyle T(n)}$ ${\displaystyle \Theta (n\log n)}$

(Este resultado se confirma mediante la solución exacta de la relación de recurrencia, que es , suponiendo ). ${\displaystyle T(n)=n+10n\log _{2}n}$ ${\displaystyle T(1)=1}$

Ejemplo de caso 3

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

Como podemos ver en la fórmula anterior las variables obtienen los siguientes valores:

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

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

A continuación, vemos si satisfacemos la condición del caso 3:

${\displaystyle \log _{b}a=\log _{2}2=1}$, y por lo tanto, sí, ${\displaystyle c>\log _{b}a}$

La condición de regularidad también se cumple:

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

Así se desprende del tercer caso del teorema maestro:

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

Por lo tanto la relación de recurrencia dada estaba en , que cumple con la de la fórmula original. ${\displaystyle T(n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle f(n)}$

(Este resultado se confirma mediante la solución exacta de la relación de recurrencia, que es , suponiendo .) ${\displaystyle T(n)=2n^{2}-n}$ ${\displaystyle T(1)=1}$

Ecuaciones inadmisibles

Las siguientes ecuaciones no se pueden resolver utilizando el teorema maestro: ^[4]

• ${\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}}}$

  Diferencia no polinómica entre y (ver más abajo; se aplica la versión extendida) ${\displaystyle f(n)}$ ${\displaystyle n^{\log _{b}a}}$

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

  ${\displaystyle f(n)}$, que es el tiempo de combinación, no es positivo

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

  caso 3 pero violación de regularidad.

En el segundo ejemplo inadmisible anterior, la diferencia entre y se puede expresar con la razón . Es evidente que para cualquier constante . Por lo tanto, la diferencia no es polinómica y la forma básica del Teorema Maestro no se aplica. La forma extendida (caso 2b) sí se aplica, dando la solución . ${\displaystyle f(n)}$ ${\displaystyle n^{\log _{b}a}}$ ${\displaystyle {\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}}$ ${\displaystyle {\frac {1}{\log n}}<n^{\epsilon }}$ ${\displaystyle \epsilon >0}$ ${\displaystyle T(n)=\Theta (n\log \log n)}$

Aplicación a algoritmos comunes

Véase también

• Método Akra-Bazzi
• Complejidad asintótica

Notas

1. Bentley, Jon Louis ; Haken, Dorothea ; Saxe, James B. (septiembre de 1980), "Un método general para resolver recurrencias de divide y vencerás", ACM SIGACT News , 12 (3): 36–44, doi :10.1145/1008861.1008865, S2CID  40642274, archivado desde el original el 22 de septiembre de 2017
2. Duke University, "Gran regalo para las funciones recursivas: relaciones de recurrencia", http://www.cs.duke.edu/~ola/ap/recurrence.html
3. Chee Yap, Un enfoque elemental real para dominar la recurrencia y las generalizaciones, Actas de la octava conferencia anual sobre teoría y aplicaciones de modelos de computación (TAMC'11), páginas 14-26, 2011. Copia en línea.
4. Instituto Tecnológico de Massachusetts (MIT), "Teorema maestro: problemas prácticos y soluciones", https://people.csail.mit.edu/thies/6.046-web/master.pdf
5. Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

Referencias

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw–Hill, 2001. ISBN 0-262-03293-7 . Secciones 4.3 (El método maestro) y 4.4 (Demostración del teorema maestro), págs. 73–90. 
• Michael T. Goodrich y Roberto Tamassia . Algorithm Design: Foundation, Analysis, and Internet Examples . Wiley, 2002. ISBN 0-471-38365-1 . El teorema maestro (incluida la versión del Caso 2 incluida aquí, que es más sólida que la de CLRS) se encuentra en las páginas 268-270.