Cómo encontrar los límites superior e inferior utilizando el teorema principal

El maestro teorema trata de algoritmos en forma recursiva. Un algoritmo de forma recursiva no tiene una solución que es fácilmente evidente a partir de la manipulación algebraica. El principal teorema que permite una solución a este problema mediante la comparación de un algoritmo recursivo a otros algoritmos, lo que le permite estimar superior e inferior límites de la solución. 

LÍMITES MAESTRO

Escribe el algoritmo en la forma necesaria para el teorema maestro. La forma es T (n) = aT (n / b) + f (n). Aquí, f (n) es una función de n. Por ejemplo, si el algoritmo que tiene es T (n) = e * T (n / e) + n * log (n), se puede saber que a = e, b = e y f (n) = n * log (n).

Comparar f (n) para n ^ log (a-ep, b). Aquí, ep refiere a épsilon, un valor arbitrariamente pequeño y el registro de la función (x, y) se refiere a un logaritmo de base y-evaluado en x. En el ejemplo, ya que a = b = e, comparar f (n), que es n * log (n) para n ^ log (e-EP, e). Use su conocimiento básico de funciones para ver que n * log (n) siempre será más grande que n ^ log (e-ep, e), ya que el término anterior es un producto de dos números grandes y el segundo es igual a n ^ ( 1 ep). Por lo tanto, concluir que n * log (n) n ^ log (e-ep, e).

Comparar f (n) para n ^ log (a + ep, b). Observe esto es similar a la comparación anterior, pero con el valor épsilon como un valor añadido, en lugar de una resta. Para el ejemplo, se compara f (n), que es n * log (n), para n ^ log (e + EP, e). Tenga en cuenta que este tiempo f (n) es el término más pequeño, ya que n ^ log (e + EP, e) es un producto de dos términos n mientras que f (n) es un producto de un término n y un log más pequeño (n) plazo. Por lo tanto, la conclusión de que f (n) n ^ log (e + EP, e).

Informe de los límites superior e inferior. Vuelva a colocar la parte f (n) del algoritmo con los valores que se acaba de encontrar eran más grandes y más pequeños, eliminando el término épsilon. Además, sustituir el término T (n) con el nuevo término correspondiente a si el límite es un límite superior o el límite inferior. Los algoritmos correspondientes son los límites superior e inferior. Para el ejemplo, el límite superior es entonces U (n) = e * U (n / e) + n * log (n) y el límite inferior es L (n) = e * L (n / e) + n.