2.3.3. Cambio de variable.

• t(n) = a·t(n/4) + b·t(n/8) + ....

• Cambio de variable: Convertir las ecuaciones anteriores en algo de la forma t’(k) = a·t’(k-c1)+b·t’(k-c2)

• Resolver el sistema en k.

• Deshacer el cambio, y obtener el resultado en n.

• Ejemplo 1. Resolver:

t(n) = a Si n=1

t(n) = 2 t(?n/2?) + b·n Si nɭ, con bɬ

• Ejemplo 2. Resolver:

t(n) = n Si n<b

t(n) = 3·t(n-b) + n2 + 1 En otro caso

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica