Análisis de Complejidad de Tiempo | Torre de Hanoi (Recursión)

Tower of Hanoi es un rompecabezas matemático donde tenemos tres varillas y n discos. El objetivo del rompecabezas es mover toda la pila a otra barra, obedeciendo las siguientes reglas simples:
1) Solo se puede mover un disco a la vez.
2) Cada movimiento consiste en tomar el disco superior de una de las pilas y colocarlo encima de otra pila, es decir, un disco solo se puede mover si es el disco superior de una pila.
3) No se puede colocar ningún disco encima de un disco más pequeño.

Pseudocódigo

TOH(n, x, y, z)
{
   if (n >= 1)
   {
      // put (n-1) disk to z by using y
      TOH((n-1), x, z, y)
   
       // move larger disk to right place
       move:x-->y
     
      // put (n-1) disk to right place 
      TOH((n-1), z, y, x)
   }
}

Análisis de Recursión

Ecuación recursiva: $T(n) = 2T(n-1) + 1$ ——-ecuación-1

Resolviéndolo por Backsubstitution :
$T(n-1) = 2T(n-2) + 1$ ———–ecuación-2
$T(n-2) = 2T(n-3) + 1$ ———–ecuación-3

Pon el valor de T(n-2) en la ecuación–2 con ayuda de la ecuación-3
$T(n-1)= 2( 2T(n-3) + 1 ) + 1$ ——ecuación-4

Pon el valor de T(n-1) en la ecuación-1 con ayuda de la ecuación-4
$T(n)= 2( 2( 2T(n-3) + 1 ) + 1 ) + 1$
$T(n) = 2^3 T(n-3) + 2^2 + 2^1 + 1$

Después de la generalización:
$T(n)= 2^k T(n-k) + 2^{(k-1)} + 2^{(k-2)} + ............ +2^2 + 2^1 + 1$

Condición base T(1) =1
n – k = 1
k = n-1
puesto, k = n-1
$T(n) =2^{(n-1)}T(1) + + 2^{(n-2)} + ............ +2^2 +2^1 + 1$

Es una serie GP, y la suma es $2^n - 1$

$T(n)= O( 2^n - 1)$ , or you can say $O(2^n)$ which is exponential

para 5 discos, es decir, n=5 Tomará 2^5-1=31 movimientos.

Publicación traducida automáticamente

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

Deja una respuesta Cancelar la respuesta