El método principal para la repetición , a menudo llamado el teorema principal, calcula los recursos necesarios para llevar a cabo un algoritmo recursivo , como el tiempo de ejecución en un ordenador. El método maestro utiliza lo que se conoce como notación Big O para describir el comportamiento asintótico de las funciones , es decir, la rapidez con que crecen hacia su límite. Divide y vencerás

Un algoritmo recursivo se puede dividir en sub- problemas , a través del " divide y vencerás " de estrategia. Cada uno de estos sub- problemas bifurca del problema original y puede ser pensado como un nodo . Por el teorema de maestro , estos nodos se denominan n /b, donde n es el tamaño del problema original , y b es el número de piezas en el que se rompe , supone que son de igual tamaño . De cada uno de estos nodos , nodos hijos pueden ramificarse , que a su vez también se pueden abordar uno a la vez con la estrategia de divide y vencerás .
Maestro Teorema

el teorema maestro funciona para los algoritmos recursivos T ( n ) , donde T ( n ) = aT ( n /b ) + f ( n ) , y T ( 1 ) = c , de modo que hay un valor de partida para generar la recursividad. Un ejemplo es T ( n ) = 2T (n /4 ) + n ^ 2 . El teorema principal entonces el algoritmo clasifica en una categoría con otros algoritmos que toman la misma cantidad de trabajo .

Los casos no previstos

El teorema principal no puede ser utilizado si T ( n) es una monótona , tales como el pecado n . Tal función no experimenta crecimiento, que es por eso que se llama un tono monótono . f (n ) debe ser un polinomio , tal 2x ^ 3 + 3x + 4 , en oposición a las funciones como 2 ^ n . b debe ser de al menos 2, y debe ser de al menos 1 , y c debe ser positivo.
Ejemplo

T ( n) = 8T (n /2 1000N ) + ^ 2

T ( n) = theta (n ^ log_base_b ( a) )

a = 8

b = 2

T (n ) = theta (n ^ 3 )

esto nos dice que este algoritmo recursivo pertenece al tipo n ^ 3 , y tendrá el mismo tiempo de ejecución como otros algoritmos de esa categoría.
< br >