Condición de regularidad en el teorema del maestro.

El teorema de Master es una forma directa de obtener la solución de una relación de recurrencia, siempre que sea del siguiente tipo:

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

El teorema consta de los siguientes tres casos:
1 .Si f(n) = $\theta$ ( $n^c$ ) donde c < $log_b a$ entonces T(n) = $\theta$ (n $log_b a$ )

2 .Si f(n) = $\theta$ ( $n^c$ ) donde c = $log_b a$ entonces T(n) = $\theta$ ( $n^c$ Log n)

3 .Si f(n) = $\theta$ ( $n^c$ ) donde c > $log_b a$ entonces T(n) = $\theta$ (f(n))

Imagina la recurrencia aT(n/b) + f(n) en forma de árbol.
El caso 1 cubre el caso en el que los Nodes secundarios realizan más trabajo que el Node principal.
Por ejemplo, la ecuación T(n)=2T(n/2)+1 cae en la categoría del caso 1 y podemos ver claramente en su árbol a continuación que en cada nivel los Nodes secundarios realizan el doble de trabajo que el Node principal.

                                     T(n)          ------(1)
                                    /    \
                                 T(n/2)  T(n/2)    ------(2)
                                  /   \   /   \

El caso 2 cubre el caso en que el Node secundario y el Node principal realizan la misma cantidad de trabajo.

Por ejemplo, la ecuación T(n)=2T(n/2)+n cae en la categoría del caso 2 y podemos ver claramente en su árbol a continuación que en cada nivel los Nodes secundarios realizan tanto trabajo como el Node principal.

                                     T(n)          ------(n)
                                    /    \
                                 T(n/2)  T(n/2)    ------(n)
                                  /   \   /   \

El caso 3 cubre el escenario en el que el Node principal hace más trabajo que los Nodes secundarios.
T(n)=T(n/2)+n es un ejemplo del caso 3 donde el padre realiza más trabajo que el hijo.

                                     T(n)          ------(n)
                                       |
                                     T(n/2)        ------(n/2)
                                       |

En el caso 1 y el caso 2, las condiciones del caso aseguran que el trabajo realizado por los niños sea mayor o igual al del padre, pero ese no es el caso del caso 3.
En el caso 3, aplicamos una condición reglamentaria para asegurarse de que el padre hace al menos tanto como los niños.

La condición regulatoria para el caso 3 es

af(n/b)<=cf(n).

Esto dice que f(n) (la cantidad de trabajo realizado en la raíz) debe ser al menos tan grande como la suma del trabajo realizado en los niveles inferiores.

La ecuación T(n) = T(n/2) + n(sin(n – $\pi$ /2) + 2) es un ejemplo donde la condición regulatoria hace una gran diferencia. La ecuación no satisface el caso 1 y el caso 2. En el caso 3, para valores grandes de n, nunca puede satisfacer la condición regulatoria. Por lo tanto, esta ecuación está más allá del alcance del teorema maestro.

Este artículo es una contribución de Vineet Joshi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta