M.C. Meliza Contreras González

1

Es normal que un algoritmo se base en procedimientos auxiliares, haga llamadas recursivas para tamaños menores o reduzca el tamaño del problema progresivamente.

En el análisis, T(n) se expresa en función del tiempo para T(n-1), T(n-2)... Ecuaciones de recurrencia.

2

Hanoi (origen,pivote,destino,discos)si discos=1

mover(origen,destino)en otro caso

Hanoi (origen,destino,pivote,discos-1)

mover (origen,destino)Hanoi

(pivote,origen,destino,discos-1)

T(n)=2T(n-1)+c3

En general, las ecuaciones de recurrencia tienen la forma:

t(n) = b Para 0 n n0

Casos baset(n) = f ( t(n-1), ..., t(n-k), n) en otro caso

4

La ecuación de recurrencia es de la forma:a0t(n) + a1t(n-1) + ... + akt(n-k) = 0; ai constante

Caso sencillo: t(n) = x·t(n-1); t(0)= 1. Solución: t(n) = x·t(n-1) = x·x·t(n-2) = x3 t(n-3) = ... = xn·t(0)

t(n) = xn

5

Teorema fundamental del Álgebra

Todo polinomio p(x) de grado k posee k raíces de tal modo quep(x) = i=1,k (x-ri) donde ri son las soluciones de p(x)=0como p(x)=0 y x=ri y tn=xn entonces ri

n es una solución de la recurrencia

Toda combinación lineal de soluciones es también una soluciónxn = tn = i=1,k ciri

n donde c1, c2, ... cn son constantes

6

Si la ecuación de recurrencia tiene k llamados la elección del grado será xk-1

Por ejemplo, T(n)=T(n-1) + 3T(n-2)+5T(n-3)

Por lo que T(n)=x3

7

Si todas las raíces son distintas, es decir rirj entonces la solución viene dada por la expresión:

Donde los coeficientes ci se determinan a partir de las condiciones iniciales

T(n)=c1r1n+c2r2

n+…+ckrkn=Σciri

n

8

T(n)=T(n-1)+T(n-2), n>=2 Condiciones iniciales T(0)=0, T(1)=1. Haciendo el cambio t(n)=x2

Se obtiene la ecuación característicax2=x+1

9

Esta ecuación de segundo grado se resuelve mediante la fórmula

Si el polinomio es de grado mayor a 2 las raíces se pueden obtener mediante división sintética

X=-bb2-4ac

2a

10

Quedando como raíces

Por tanto:22

r1=1+5

2

r1=1+5

2 22

5

2

r 2=1-

2

n

T(n)=c1 + c2

22

1+5

22 222

1-5

2

n

11

Para encontrar las constantes c1 y c2 se resuelve el sistema de ecuaciones planteado con las condiciones iniciales

T(0)=c1 + c2 =c1+c2=0

0

22

1+5

22 222

1-5

2

0

T(1)=c1 + c2 =1

1

22

1+5

22 222

1-5

2

1

12

Así c1=-c2=1/5 sustituyendo en la ecuación anterior resulta

T(0)= - (

n

22

1+5

22 222

1-5

2

n

1 5

1 5

n

13

• Una recurrencia es no homogénea cuando la combinación lineal no es igual a 0

• a0tn + a1tn-1 +...+ aktn-k = bn·p(n)Donde b es constante y p(n) es un polinomio de

grado d• Solución: reducir al caso homogéneo:

Aplicando el polinomio característico (tn=xn)(a0xk + a1xk-1 + ... + ak)·(x-b)d+1 donde d es el grado de

p(n)Las constantes se determinan con las condiciones iniciales y con la propia recurrencia

• Ejemplos: • tn – 2·tn-1 = 3n •

• T(n) =

0 si n=0

2t(n-1) + 1 en otro caso

14

T(n) =2t(n-1) + 1 T(0)=0, T(1)=1 En este caso b=1 y p(n)=1,

polinomio en n de grado 0. Se resuelve la ecuación

homogénea con el cambio T(n)=x resultando

X-2=0, agregando a este binomio el binomio (x-b)d+1

15

(x-2)(x-1)0+1=(x-2)(x-1), así T(n) =c12n+c21n O2n

16

Supongamos que alguna de las raíces tiene multiplicidad m>1 entonces la ecuación característica se escribe:

En este caso la ecuación de recurrencia viene dada por la expresión

(x-r1)m(x-r2)…(x-rk-m+1)

Σcirni-m+1

i=m+1T(n)=Σcini-1r1

n+ i=1

m k

17

• Ejemplo con raíces múltiples:tn = 2·tn-1 + n (a)Polinomio característico: (x-2)(x-1)2

Solución de la forma: tn = c12n + c21n + c3n1n (b)

Solución: (2n)

18

Método de cambio de variable Método maestro

19

T(n) término de una recurrencia original Ti término de un nueva recurrencia obtenida de la

original mediante cambio de variable• Ejemplo:

t(n) =

a) n = 2i i=log2 n ; para transformarla en algo conocido hacemos:

ti = t(2i)

ti = t(2i) = 3t(2i-1) + 2i ti – 3ti-1 = 2i (x-2)(x-3)

ti = c1·3i + c22i como i = log2 n y clog n=nlog c

ti = c1nlog 3 + c2nlog 2 t(n) O(nlog 3), log23=1.5849

1 si n=1

3t(n/2) + n si n es potencia de 2, n>1

20

Provee cotas para las recurrencias de la forma:

T(n)=aT(n/b)+f(n) a>=1,b>1 y f(n) positiva. Describe el tiempo que un algoritmo divide

un problema de tamaño n en a subproblemas cada uno de tamaño n/b.

El costo de dividir el problema y combinar los resultados se describe con f(n)

21

Si f(n)=O(n ) >0 T(N)=(n )

Si f(n)=(n ) T(N)=(n logn)

Si f(n)=Ώ(n ) >0 y af(n/b)<=cf(n)

T(N)=(f(n))

logba

logba-

logba

logba

logba+

22

T(n)=9T(n/3)+n a=9,b=3, f(n)=n, n =(n2)

f(n)=O(n ), =1, f(n)=O(n)T(n)=(n2)

Caso 1

log39

log39-

23

T(n)=T(2n/3)+1 a=1,b=3/2, f(n)=1,

n = n =n0=1,

f(n)= (n )=(1)

T(n)=(1logn)Caso 2

logba log3/21

logba

24

T(n)=3T(n/4)+nlogn a=3,b=4, f(n)=nlogn,

n = n =O(n0.793), f(n)= Ώ(n )=Ώ(n), =0.2 af(n/b)=3(n/4)log(n/4) <=(3/4)nlogn=cf(n), c=3/4 T(n)=(nlogn)

Caso 3

logba log43

Log43+

25