Teorema maestro avanzado para las recurrencias de divide y vencerás

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: 

Formula to calculate runtime of divide and conquer algorithms

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, 
 

  1. si a > b k , entonces T(n) = θ(n log b a )
  2. 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
     
  3. 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
    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
    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 – 
 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *