El teorema maestro se utiliza para determinar el tiempo de ejecución de los algoritmos (algoritmos de divide y vencerás) en términos de notaciones asintóticas.
Considere un problema que se resuelva usando recursividad.
function f(input x size n) if(n < k) solve x directly and return else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems
El algoritmo anterior divide el problema en subproblemas , cada uno de tamaño n/b y los resuelve recursivamente para calcular el problema y el trabajo adicional realizado para el problema viene dado por f(n), es decir, el tiempo para crear los subproblemas y combinar sus da como resultado el procedimiento anterior.
Entonces, según el teorema maestro, el tiempo de ejecución del algoritmo anterior se puede expresar como:
T(n) = aT(n/b) + f(n)
donde n = tamaño del problema
a = número de subproblemas en la recursividad y a >= 1
n/b = tamaño de cada subproblema
f(n) = costo del trabajo realizado fuera de las llamadas recursivas como dividir en subproblemas y costo de combinarlos para obtener la solución.
No todas las relaciones de recurrencia se pueden resolver con el uso del teorema maestro, es decir, si
- T(n) no es monótono, ej: T(n) = sen n
- f(n) no es un polinomio, ej: T(n) = 2T(n/2) + 2 n
Este teorema es una versión avanzada del teorema maestro que se puede utilizar para determinar el tiempo de ejecución de los algoritmos divide y vencerás si la recurrencia es de la siguiente forma:
donde n = tamaño del problema
a = número de subproblemas en la recursividad ya >= 1
n/b = tamaño de cada subproblema
b > 1, k >= 0 y p es un número real.
Después,
- si a > b k , entonces T(n) = θ(n log b a )
- si a = b k , entonces
(a) si p > -1, entonces T(n) = θ(n log b a log p+1 n)
(b) si p = -1, entonces T(n) = θ (n log b a loglogn)
(c) si p < -1, entonces T(n) = θ(n log b a )
- si a < b k , entonces
(a) si p >= 0, entonces T(n) = θ(n k log p n)
(b) si p < 0, entonces T(n) = θ(n k )
Análisis de Complejidad de Tiempo –
- Ejemplo-1: Búsqueda binaria – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 y p = 0
b k = 1. Entonces, a = b k y p > -1 [Caso 2.(a)]
T(n) = θ(n log b a log p+1 n)
T(n) = θ(logn) - Ejemplo 2: Ordenación por fusión: T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b k = 2. Entonces, a = b k y p > -1 [Caso 2.(a)]
T(n) = θ(n log b a log p+1 n)
T(n) = θ(nlogn) - Ejemplo-3: T(n) = 3T(n/2) + n 2
a = 3, b = 2, k = 2, p = 0
b k = 4. Entonces, a < b k y p = 0 [Caso 3.(a)]
T(n) = θ(n k log p n)
T(n) = θ(n 2 ) - Ejemplo-4: T(n) = 3T(n/2) + log 2 n
a = 3, b = 2, k = 0, p = 2
b k = 1. Entonces, a > b k [Caso 1]
T (n) = θ(n log b a )
T(n) = θ(n log 2 3 ) - Ejemplo-5: T(n) = 2T(n/2) + nlog 2 n
a = 2, b = 2, k = 1, p = 2
b k = 2. Entonces, a = b k [Caso 2.( a)]
T(n) = θ(n log b a log p+1 n )
T(n) = θ(n log 2 2 log 3 n)
T(n) = θ(nlog 3 n) - Ejemplo-6: T(n) = 2 n T(n/2) + n n
Esta recurrencia no se puede resolver usando el método anterior ya que la función no tiene la forma T(n) = aT(n/b) + θ( n k iniciar sesión p n)
GATE Preguntas de práctica –