En el análisis de algoritmos , el teorema maestro para las recurrencias de divide y vencerás proporciona un análisis asintótico (usando la notación Big O ) para las relaciones de recurrencia de tipos que ocurren en el análisis de muchos algoritmos de divide y vencerás . El enfoque fue presentado por primera vez por Jon Bentley , Dorothea 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 Introducción a los algoritmos ampliamente utilizado porCormen , Leiserson , Rivest y Stein .
No todas las relaciones de recurrencia se pueden resolver con el uso de este teorema; sus generalizaciones incluyen el método Akra-Bazzi .
Introducción
Considere un problema que se puede resolver mediante un algoritmo recursivo como el siguiente:
procedimiento p (entrada x de tamaño n ): si nk : Resuelva x directamente sin recursividad más : Crear un subproblema de x , cada uno con un tamaño n / b Llamar al procedimiento p de forma recursiva en cada subproblema Combinar los resultados de los subproblemas
El algoritmo anterior divide el problema en varios subproblemas de forma recursiva, siendo cada subproblema de tamaño n / b . Su árbol de solución tiene un nodo para cada llamada recursiva, siendo los hijos de ese nodo las otras llamadas realizadas desde esa llamada. Las hojas del árbol son los casos base de la recursividad, los subproblemas (de tamaño menor que k ) que no se repiten. El ejemplo anterior tendría un niño nodos en cada nodo no 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.
El tiempo de ejecución de un algoritmo como la 'p' anterior en una entrada de tamaño 'n', generalmente denotado , se puede expresar mediante la relación de recurrencia
dónde es el momento de 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 de 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.
Forma genérica
El teorema maestro siempre produce límites asintóticamente ajustados a las recurrencias de los algoritmos de dividir y conquistar que dividen una entrada en subproblemas más pequeños de igual tamaño, resuelven los subproblemas de forma recursiva y luego combinan las soluciones de los subproblemas para dar una solución al problema original. El tiempo para tal algoritmo se puede expresar agregando el trabajo que realizan en el nivel superior de su recursividad (para dividir los problemas en subproblemas y luego combinar las soluciones del subproblema) junto con el tiempo realizado en las llamadas recursivas del algoritmo. Si denota el tiempo total para el algoritmo en una entrada de tamaño , y denota la cantidad de tiempo que se tarda en el nivel superior de la recurrencia, luego el tiempo se puede expresar mediante una relación de recurrencia que toma la forma:
Aquí es el tamaño de un problema de entrada, es el número de subproblemas en la recursividad, y es el factor por el cual se reduce el tamaño del subproblema en cada llamada recursiva. El teorema siguiente también asume que, como caso base para la recurrencia, Cuándo es menor que un límite , el tamaño de entrada más pequeño que dará lugar a una llamada recursiva.
Las recurrencias de esta forma a menudo satisfacen uno de los tres regímenes siguientes, en función de cómo se trabaja para dividir / recombinar el problema se relaciona con el exponente crítico . (La siguiente tabla usa la notación O grande estándar ).
Caso | Descripción | Condición en En relación a , es decir | Límite del teorema maestro | Ejemplos de notación |
---|---|---|---|---|
1 | El trabajo para dividir / recombinar un problema se ve eclipsado por los subproblemas. es decir, el árbol de recursividad tiene muchas hojas | Cuándo dónde (delimitado superior por un polinomio de exponente menor) | ... luego (El término de división no aparece; domina la estructura de árbol recursiva). | Si y , luego . |
2 | El trabajo para dividir / recombinar un problema es comparable a los subproblemas. | Cuándo para (rango limitado por el polinomio de exponente crítico, multiplicado por cero o más opcional s) | ... luego (El límite es el término de división, donde el registro aumenta con una sola potencia). | Si y , luego . Si y , luego . |
3 | El trabajo para dividir / recombinar un problema domina los subproblemas. es decir, el árbol de recursividad tiene muchas raíces. | Cuándo dónde (delimitado por un polinomio de mayor exponente) | ... esto no necesariamente produce nada. Además, si
entonces el total está dominado por el término de división : | Si y y la condición de regularidad se mantiene, entonces . |
Una extensión útil del Caso 2 maneja todos los valores de : [3]
Caso | Condición en En relación a , es decir | Límite del teorema maestro | Ejemplos de notación |
---|---|---|---|
2a | Cuándo para cualquier | ... luego (El límite es el término de división, donde el registro aumenta con una sola potencia). | Si y , luego . |
2b | Cuándo por | ... luego (El límite es el término de división, donde el recíproco del registro se reemplaza por un registro iterado). | Si y , luego . |
2c | Cuándo para cualquier | ... luego (El límite es el término de división, donde el registro desaparece). | Si y , luego . |
Ejemplos de
Ejemplo de caso 1
Como se puede ver en la fórmula anterior:
- , entonces
- , dónde
A continuación, vemos si cumplimos la condición del caso 1:
- .
Del primer caso del teorema maestro se deduce que
(Este resultado es confirmado por la solución exacta de la relación de recurrencia, que es , asumiendo ).
Ejemplo de caso 2
Como podemos ver en la fórmula anterior, las variables obtienen los siguientes valores:
- dónde
A continuación, vemos si cumplimos la condición del caso 2:
- , y por lo tanto,
Por tanto, se deduce del segundo caso del teorema maestro:
Por lo tanto, la relación de recurrencia dada T ( n ) estaba en Θ ( n log n ).
(Este resultado es confirmado por la solución exacta de la relación de recurrencia, que es , asumiendo .)
Ejemplo de caso 3
Como podemos ver en la fórmula anterior, las variables obtienen los siguientes valores:
- , dónde
A continuación, vemos si cumplimos la condición del caso 3:
- , y por tanto, sí,
La condición de regularidad también se cumple:
- , eligiendo
Entonces se sigue del tercer caso del teorema maestro:
Así, la relación de recurrencia dada estaba en , que cumpla con la de la fórmula original.
(Este resultado es confirmado por la solución exacta de la relación de recurrencia, que es , asumiendo .)
Ecuaciones inadmisibles
Las siguientes ecuaciones no se pueden resolver usando el teorema maestro: [4]
- a no es una constante; el número de subproblemas debe ser arreglado
- diferencia no polinomial entre y (ver más abajo; se aplica la versión extendida)
- no puede tener menos de un subproblema
- , que es el tiempo de combinación, no es positivo
- caso 3 pero violación de regularidad.
En el segundo ejemplo inadmisible anterior, la diferencia entre y se puede expresar con la relación . Está claro que para cualquier constante . Por lo tanto, la diferencia no es polinomial y no se aplica la forma básica del Teorema maestro. La forma extendida (caso 2b) se aplica, dando la solución.
Aplicación a algoritmos comunes
Algoritmo | Relación de recurrencia | Tiempo de ejecución | Comentario |
---|---|---|---|
Búsqueda binaria | Aplicar el caso del teorema maestro , dónde [5] | ||
Cruce de árbol binario | Aplicar el caso del teorema maestro dónde [5] | ||
Búsqueda de matriz ordenada óptima | Aplicar el teorema de Akra-Bazzi para y Llegar | ||
Combinar ordenación | Aplicar el caso del teorema maestro , dónde |
Ver también
Notas
- ^ 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
- ^ Universidad de Duke, "Big-Oh para funciones recursivas: relaciones de recurrencia", http://www.cs.duke.edu/~ola/ap/recurrence.html
- ^ Chee Yap, Una aproximación elemental real a la recurrencia maestra y 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.
- ^ Instituto de Tecnología de Massachusetts (MIT), "Teorema del maestro: problemas de práctica y soluciones", https://people.csail.mit.edu/thies/6.046-web/master.pdf
- ^ a b 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 (Prueba del teorema maestro), págs. 73–90.
- Michael T. Goodrich y Roberto Tamassia . Diseño de algoritmos: bases, análisis y ejemplos de Internet . 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.
enlaces externos
- Teorema Mestre e Exemplos Resolvidos (en portugués)