Análisis de Algoritmo | Conjunto 4 (Resolución de recurrencias)

En la publicación anterior, discutimos el análisis de bucles . Muchos algoritmos son recursivos. Cuando los analizamos, obtenemos una relación de recurrencia para la complejidad del tiempo. Obtenemos el tiempo de ejecución en una entrada de tamaño n en función de n y el tiempo de ejecución en entradas de tamaños más pequeños. Por ejemplo, en Merge Sort , para ordenar una array dada, la dividimos en dos mitades y repetimos recursivamente el proceso para las dos mitades. Finalmente, fusionamos los resultados. La complejidad temporal de Merge Sort se puede escribir como T(n) = 2T(n/2) + cn. Hay muchos otros algoritmos como Binary Search, Tower of Hanoi, etc. 

Existen principalmente tres formas de resolver las recurrencias. 

1) Método de sustitución : Adivinamos la solución y luego usamos la inducción matemática para demostrar que la suposición es correcta o incorrecta. 

For example consider the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = O(nLogn). Now we use induction
to prove our guess.

We need to prove that T(n) <= cnLogn. We can assume that it is true
for values smaller than n.

T(n) = 2T(n/2) + n
    <= 2cn/2Log(n/2) + n
    =  cnLogn - cnLog2 + n
    =  cnLogn - cn + n
    <= cnLogn

2) Método del árbol de recurrencia: en este método, dibujamos un árbol de recurrencia y calculamos el tiempo que tarda cada nivel del árbol. Finalmente, sumamos el trabajo realizado a todos los niveles. Para dibujar el árbol de recurrencia, comenzamos con la recurrencia dada y seguimos dibujando hasta encontrar un patrón entre niveles. El patrón es típicamente una serie aritmética o geométrica. 
 

For example, consider the recurrence relation 
T(n) = T(n/4) + T(n/2) + cn2

           cn2
         /      \
     T(n/4)     T(n/2)

If we further break down the expression T(n/4) and T(n/2), 
we get the following recursion tree.

                cn2
           /           \      
       c(n2)/16      c(n2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 
Breaking down further gives us following
                 cn2
            /            \      
       c(n2)/16          c(n2)/4
       /      \            /      \
c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16
 /    \      /    \    /    \       /    \  

To know the value of T(n), we need to calculate the sum of tree 
nodes level by level. If we sum the above tree level by level, 
we get the following series
T(n)  = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....
The above series is a geometrical progression with a ratio of 5/16.

To get an upper bound, we can sum the infinite series. 
We get the sum as (n2)/(1 - 5/16) which is O(n2)

3) Método 
Maestro: El Método Maestro es una forma directa de obtener la solución. El método maestro solo funciona para el siguiente tipo de recurrencias o para las recurrencias que se pueden transformar en el siguiente tipo. 
 

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

Existen los siguientes tres casos: 
1. Si f(n) = O(n ^c ) donde c < Log _b a entonces T(n) = Θ(n ^{Log _b a} ) 

2. Si f(n) = Θ(n ^c ) donde c = Log _b a entonces T(n) = Θ(n ^c Log n) 

3. Si f(n) = Ω(n ^c ) donde c > Log _b a entonces T(n) = Θ(f(n))

¿Como funciona esto?  
El método maestro se deriva principalmente del método del árbol de recurrencia. Si dibujamos el árbol de recurrencia de T(n) = aT(n/b) + f(n), podemos ver que el trabajo realizado en la raíz es f(n), y el trabajo realizado en todas las hojas es Θ(n ^c ) donde c es Log _b a. Y la altura del árbol de recurrencia es Log _b n 
 

En el método del árbol de recurrencia, calculamos el trabajo total realizado. Si el trabajo realizado en las hojas es polinomialmente mayor, entonces las hojas son la parte dominante y nuestro resultado se convierte en el trabajo realizado en las hojas (Caso 1). Si el trabajo realizado en las hojas y la raíz es asintóticamente el mismo, nuestro resultado se convierte en la altura multiplicada por el trabajo realizado en cualquier nivel (Caso 2). Si el trabajo realizado en la raíz es asintóticamente mayor, entonces nuestro resultado se convierte en trabajo realizado en la raíz (Caso 3). 

Ejemplos de algunos algoritmos estándar cuya complejidad temporal se puede evaluar utilizando el método maestro 
Merge Sort : T(n) = 2T(n/2) + Θ(n). Cae en el caso 2 ya que c es 1 y Log _b a] también es 1. Entonces la solución es Θ(n Logn) 

Búsqueda binaria : T(n) = T(n/2) + Θ(1). También cae en el caso 2 ya que c es 0 y Log _b a también es 0. Entonces la solución es Θ(Logn) 

Notas: 
1) No es necesario que una recurrencia de la forma T(n) = aT(n/b) + f(n) pueda resolverse usando el Teorema del Maestro. Los tres casos dados tienen algunas lagunas entre ellos. Por ejemplo, la recurrencia T(n) = 2T(n/2) + n/Logn no se puede resolver con el método maestro. 

2) El caso 2 se puede extender para f(n) = Θ(n ^c Log ^k n) 
Si f(n) = Θ(n ^c Log ^k n) para alguna constante k >= 0 y c = Log _b a, entonces T(n) = Θ(n ^c Log ^k+1 n) 

Para más detalles, consulte:
Diseño y Análisis de Algoritmos .

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