- Teorema maestro
-
El Teorema maestro es un método matemático que se usa para resolver ciertos casos particulares de ecuaciones de recurrencia como la siguiente:
.Consideremos una función t(n) que no sea decreciente:
con constantes a ≥ 1 y b ≥ 2. Obtenemos
Nota: θ(orden exacto), O (orden superior), Ω(orden inferior), según la notación de Landau.
Ejemplos de casos no válidos para el Teorema maestro
Esta no es válida porque a = 2n no es constante.
En esta a = 0.5 no cumple la condición a≥1.
Ejemplo de resolución
Veamos ahora un ejemplo de resolución de una recurrencia no lineal:
Utilizando el teorema maestro:
- Obtenemos a=2, b=2, d = log22 =1 y f (n) = 0.
- Probamos la primera sentencia del teorema maestro:
¿Existe ε > 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 nd = n1 = n.
Ahora vamos a ver que ninguna de las otras sentencias puede ser verdadera:
- La 2ª sentencia no puede ser porque no existe ningún valor de k para el cual (nd·logkn)=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 = log22
- 2m = n
>>1.Sustituimos n en la ecuación recurrente:
- t(2m) = 2·t(2m/2)
-> t(2m) = 2·t(2m − 1)
- s (m) = t(2m)
>>2.Sustituimos t(2m) por s (m) y t(2m − 1) por s (m-1)
- s (m) = 2·s (m-1)
>>Resolvemos esta ecuación recurrente
- r - 2 = 0 -> r = 2
- s (m) = z·2m
>>Deshacemos el cambio 2:
- t(2m) = 2·(z·2m − 1)
-> t(2m) = z·2m
>>Deshacemos el cambio 1:
- t (n) = z·n
Nota: z la calcularíamos con el caso base de la recurrencia inicial.
Observamos que t (n) = z·n es de orden n tal como habíamos calculado con el teorema maestro.
Véase también
Categoría:- Teoremas de matemáticas
Wikimedia foundation. 2010.
