Diferentes tipos de relaciones de recurrencia y sus soluciones.

En este artículo, veremos cómo podemos resolver diferentes tipos de relaciones de recurrencia utilizando diferentes enfoques. Antes de comprender este artículo, debe tener una idea acerca de las relaciones de recurrencia y los diferentes métodos para resolverlas (Ver: Casos peores, promedio y mejores , Notaciones asintóticas , Análisis de bucles ).

Tipo 1: divide y vencerás relaciones de recurrencia:
a continuación se muestran algunos de los ejemplos de relaciones de recurrencia basadas en divide y vencerás.

T(n) = 2T(n/2) + cn
T(n) = 2T(n/2) + √n

Estos tipos de relaciones de recurrencia se pueden resolver fácilmente utilizando el método maestro .
Para la relación de recurrencia T(n) = 2T(n/2) + cn, los valores de a = 2, b = 2 yk =1. Aquí logb(a) = log2(2) = 1 = k. Por tanto, la complejidad será Θ(nlog2(n)).
De manera similar para la relación de recurrencia T(n) = 2T(n/2) + √n, los valores de a = 2, b = 2 y k =1/2. Aquí logb(a) = log2(2) = 1 > k. Por tanto, la complejidad será Θ(n).

Tipo 2: relaciones de recurrencia lineal:
a continuación se muestran algunos ejemplos de relaciones de recurrencia basadas en relaciones de recurrencia lineal.

T(n) = T(n-1) + n for n>0 and T(0) = 1

Estos tipos de relaciones de recurrencia se pueden resolver fácilmente mediante el método de sustitución .
Por ejemplo,

T(n) = T(n-1) + n
       = T(n-2) + (n-1) + n
       = T(n-k) + (n-(k-1))….. (n-1) + n

Sustituyendo k = n, obtenemos

T(n) = T(0) + 1 + 2+….. +n = n(n+1)/2 = O(n^2) 

Tipo 3: Sustitución de valores antes de resolver:
a veces, las relaciones de recurrencia no se pueden resolver directamente utilizando técnicas como la sustitución, el árbol de recurrencia o el método maestro. Por lo tanto, necesitamos convertir la relación de recurrencia a la forma apropiada antes de resolver. Por ejemplo,

T(n) = T(√n) + 1

Para resolver este tipo de recurrencia, sustituya n = 2^m como:

T(2^m) = T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = S(m/2) + 1 

Resolviendo por el método maestro, obtenemos

S(m) = Θ(logm)
As n = 2^m or m = log2(n),
T(n) = T(2^m) = S(m) = Θ(logm) = Θ(loglogn)

Discutamos algunas preguntas basadas en los enfoques discutidos.

Que – 1. ¿Cuál es la complejidad temporal del problema de la Torre de Hanoi?
(A) T(n) = O(raíz cuadrada(n))
(D) T(n) = O(n^2)
(C) T(n) = O(2^n)
(D) Ninguno

Solución: Para la Torre de Hanoi, T(n) = 2T(n-1) + c para n>1 y T(1) = 1. Resolviendo esto,

T(n) = 2T(n-1) + c
        = 2(2T(n-2)+ c) + c  = 2^2*T(n-2) + (c + 2c)
       = 2^k*T(n-k) + (c + 2c + .. kc)
Substituting k = (n-1), we get
T(n) = 2^(n-1)*T(1) + (c + 2c + (n-1)c) = O(2^n)

Que – 2. Considere la siguiente recurrencia:
T(n) = 2 * T(ceil (sqrt(n) ) ) + 1, T(1) = 1
¿Cuál de las siguientes es verdadera?
(A) T(n) = (loglogn)
(B) T(n) = (logn)
(C) T(n) = (raíz cuadrada(n))
(D) T(n) = (n)

Solución: Para resolver este tipo de recurrencia, sustituya n = 2^m como:

T(2^m) = 2T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = 2S(m/2) + 1 
Solving by master method, we get
S(m) = Θ(m)
As n = 2^m or m = log2n,
T(n) = T(2^m) = S(m) = Θ(m) = Θ(logn)