Teorema maestro

El Teorema Maestro es una forma de resolver unos casos particulares de ecuaciones de recurrencia. Ecuaciones como esta:

• t(n) = t(n/2) + 1

seria algo engorrosa de resolver, para resolverla mas rapidamente usariamos el Teorema Maestro.

Consideremos una funcion t(n) que no sea decreciente:

Archivo:Tmaestro.jpg

con a ≥ 1 y b ≥ 2. Y obtenemos d = $log_{b}a\,$ Importante: a y b han de ser constantes.

Archivo:Tmaestro1.jpg

Nota: θ(orden exacto), O(orden superior), Ω(orden inferior).

Ejemplos de casos no validos para el Teorema Maestro

• $T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$
  • Esta no es valida porque a = $2^{n}$ no es constante.

• $T(n)=0.5T\left({\frac {n}{2}}\right)+n$
  • En esta a = 0.5 no cumple la condicion a<1.

Ejemplo de resolución

Veamos ahora un ejemplo de resolucion de una recurrencia no lineal:

t(n) = 2·t(${\tfrac {n}{2}}$)

Utilizando el teorema maestro: -Obtenemos a=2, b=2, d = $log_{2}2$ =1 y f(n) = 0.

-Probamos la primera sentencia del teorema maestro: ¿∃ε > 0 tal que f(n) ∈ O[orden superior](n^(d - ε))? Se ve claramente que n^(d - ε) para ε > 0 es 0 igual que f(n).

Ya sabemos que la solución del orden exacto de $n^{d}$ = $n^{1}$ = n.

Ahora vamos a ver que ninguna de las otras sentencias puede ser verdadera:

-La 2ª sentencia no puede ser porque no existe ningun valor de k para el cual ($n^{d}$·$log^{k}$n)=0 -La 3ª sentencia no puede ser porque n^(d + ε) para d = 1, ya es mayor que 0.

-Ahora resolvamos la recurrencia (el resultado debe ser de orden n, como ya hemos calculado):

t(n) = 2·t(n/2)

m = $log_{2}2$

$2^{m}$ = n

>>1.Sustituimos n en la ecuacion recurrente:

t($2^{m}$) = 2·t($2^{m}$/2) -> t($2^{m}$) = 2·t($2^{m-1}$)

s(m) = t($2^{m}$)

>>2.Sustituimos t($2^{m}$) por s(m) y t($2^{m-1}$) por s(m-1)

s(m) = 2·s(m-1)

>>Resolvemos esta ecuacion recurrente

r - 2 = 0 -> r = 2

s(m) = z·$2^{m}$

>>Deshacemos el cambio 2:

t($2^{m}$) = 2·(z·$2^{m-1}$) -> t($2^{m}$) = z·$2^{m}$

>>Deshacemos el cambio 1:

t(n) = z·n

Nota: z la calculariamos con el caso base de la recurrenica inicial.

Observamos que t(n) = z·n es de orden n tal como habiamos calculado con el teorema maestro.

Vease también

• Ecuación recurrente