Page 43 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

T(N) = 4(2(T(N-3) + 1) + 2 + 1

= 8T(N-3) + 4+ 2+ 1

Generalizando:

T(N) = 2 T(N-K) +
K
donde
T (1) =1 y K=N-1

sabiendo que

se tiene:

T(N) = 2 N-1 + 2 - 1
N-1
T(N) = 2 (1 + 1) -1 = 2 (2) – 1
N-1
N-1
T(N) = 2 - 1
N
De esta forma, la complejidad del algoritmo es (2 ).
N

Figura 1.6. Torres de Hanói

Si los monjes hicieran un movimiento por segundo, podrían pasar los 64 discos a la tercera espiga
en unos 5849 millones de años. De acuerdo con las teorías científicas más creíbles, la tierra tiene
aproximadamente 4400 millones de años, de ahí que reste muchísimo tiempo para disfrutar de las
cosas de la vida. Hasta la fecha, este juego no tiene forma de mejorar su complejidad.

37