2.3.1. Ecuaciones lineales homogéneas.

• Sean las soluciones x= (s1, s2, ..., sk), todas distintas.

• La solución será:

k

t(n) = c1·s1n + c2·s2n + ... + ck·skn = ? ci·sin

i=1

• Siendo ci constantes, cuyos valores dependen de las condiciones iniciales.

• Ejemplo. El tiempo de ejecución de un algoritmo es:

t(n) = 3·t(n-1) + 4·t(n-2) para nɭ, t(0)=0, t(1)=1

• Encontrar una fórmula explícita para t(n), y calcular el orden de complejidad del algoritmo.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica