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.