El método del árbol de recurrencia es una forma de resolver las relaciones de recurrencia . En este método, una relación de recurrencia se convierte en árboles recursivos. Cada Node representa el costo incurrido en varios niveles de recursividad. Para encontrar el costo total, se suman los costos de todos los niveles.
Pasos para resolver la relación de recurrencia utilizando el método del árbol de recursión:
- Dibuja un árbol recursivo para una relación de recurrencia dada
- Calcule el costo en cada nivel y cuente el número total de niveles en el árbol de recurrencia.
- Cuente el número total de Nodes en el último nivel y calcule el costo del último nivel
- Sume el costo de todos los niveles en el árbol recursivo
Veamos cómo resolver estas relaciones de recurrencia con la ayuda de algunos ejemplos:
Pregunta 1: T(n) = 2T(n/2) + c
Solución:
- Paso 1: Dibujar un árbol recursivo
Árbol de recursión
- Paso 2: Calcule el trabajo realizado o el costo en cada nivel y cuente el número total de niveles en el árbol de recursividad
Árbol recursivo con cada nivel de costo
Cuente el número total de niveles –
Elija la ruta más larga desde el Node raíz hasta el Node hoja
n/2 0 -→ n/2 1 -→ n/2 2 -→ ……… -→ n/2 k
Tamaño del problema en el último nivel = n/2 k
En el último nivel, el tamaño del problema se convierte en 1
n/2 k = 1
2 k = norte
k = registro 2 (n)
Número total de niveles en el árbol recursivo = k +1 = log 2 (n) + 1
- Paso 3: cuente el número total de Nodes en el último nivel y calcule el costo del último nivel
Nº de Nodes a nivel 0 = 2 0 = 1
No. de Nodes en el nivel 1 = 2 1 = 2
………………………………………………………………
No. de Nodes a nivel log 2 (n) = 2 log 2 (n) = n log 2 (2) = n
Costo de los subproblemas en el nivel log 2 (n) (último nivel) = nxT(1) = nx1 = n
- Paso 4: sumar el costo de todos los niveles en el árbol recursivo
T(n) = c + 2c + 4c + —- + (n° de niveles-1) veces + costo del último nivel
= c + 2c + 4c + —- + log 2 (n) veces + Θ(n)
= c(1 + 2 + 4 + —- + log 2 (n) veces) + Θ(n)
1 + 2 + 4 + —– + log 2 (n) veces –> 2 0 + 2 1 + 2 2 + —– + log2(n) veces –> Progresión geométrica (GP)
= c(n) + Θ(n)
Así, T(n) = Θ(n)
Pregunta 2: T(n) = T(n/10) + T(9n/10) + n
Solución:
- Paso 1: Dibujar un árbol recursivo
Árbol recursivo
- Paso 2: Calcule el trabajo realizado o el costo en cada nivel y cuente el número total de niveles en el árbol de recursividad
Árbol de recurrencia con cada nivel de costo
Cuente el número total de niveles –
Elija la ruta más larga desde el Node raíz hasta el Node hoja
(9/10) 0 norte –> (9/10) 1 norte –> (9/10) 2 norte –> ……… –> (9/10) k norte
Tamaño del problema en el último nivel = (9/10) k n
En el último nivel, el tamaño del problema se convierte en 1
(9/10) k norte = 1
(9/10) k = 1/n
k = registro 10/9 (n)
Número total de niveles en el árbol recursivo = k +1 = log 10/9 (n) + 1
- Paso 3: cuente el número total de Nodes en el último nivel y calcule el costo del último nivel
Nº de Nodes a nivel 0 = 2 0 = 1
No. de Nodes en el nivel 1 = 2 1 = 2
………………………………………………………………
No. de Nodes a nivel log 10/9 (n) = 2 log 10/9 (n) = n log 10/9 (2)
Costo de los subproblemas en el nivel log2(n) (último nivel) = n log 10/9 (2) x T(1) = n log 10/9 (2) x 1 = n log 10/9 (2)
- Paso 4: sumar el costo de todos los niveles en el árbol recursivo
T(n) = n + n + n + —- + (nº de niveles – 1) veces + costo del último nivel
= n + n + n + —- + log 10/9 (n) veces + Θ(n log 10/9 (2) )
= nlog 10/9 (n) + Θ(n log 10/9 (2) )
Así, T(n) = Θ( nlog 10/9 (n))
Publicación traducida automáticamente
Artículo escrito por ayushjain0747 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA