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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Algoritmo 1.14. Función de Ackermann

Para comprender mejor la complejidad del algoritmo se revisa la llamada recursiva A(4,x). Sabemos
que

A(0,x) = x+1

A(n,0) = A(n-1,1)

A(n, x) = A(n-1, A(n,x-1))

Por lo que

A(1,x)=A(0,A(1,x-1))=1+A(1,x-1))=1+A(0,A(1,x-2))=1+1+A(1,x-2)=1+1+1+A(0,A(1,x-3))
A(1,x)=1+1+1+… (x-1 veces uno) + A(0,A(1,0))=(x-1)+1+A(1,0)=x+A(0,1)=x+1+1=x+2

Apoyándose en el valor de A(1,x) se obtiene:

A(2,x)=A(1,A(2,x-1))=2+A(2,x-1)=2+2+A(2,x-2)=2+2+2+A(2,x-3)=2x+A(1,1) = 2x+3
Partiendo de estos dos valores se tratará de obtener A(3,x) y recordando que

A(n, x)=A(n-1, A(n,x-1)), se tiene:

A(3,x) = A(2, A(3, x-1)) = 3+2ª(3,X-1) = 3+2ª(2, A(3, x-2)) =3+2(3+2ª(3,X-2))

= 3+2(3+2(A(2,A(3,x-3)))

= 3+2(3+2(3+2(A(2,A(3,x-4))))

45