Recurrencias
Resolución de recurrencias,
por cambio de variable
Resolución de recurrencias mediante el
cambio de variable
T(n)  término de una recurrencia
original
Ti  término de un nueva recurrencia
obtenida de la original mediante cambio
de variable
Resolución de recurrencias mediante el
cambio de variable
Ejemplo 1:


1

t (n)  
 n
 3t    n
 2
si
n 1
si
n  1, potencia .de . 2
Cambio de variable: n = 2i  i = lg2 n
Resolución de recurrencias mediante el
cambio de variable
n = 2i  i = lg2 n para transformarla en
recurrencias ya conocidas, actuamos de la
forma:
Llamanos ti = t(2i)  La variable es i.
ti = t(2i) = 3t(2i-1) + 2i  ti – 3ti-1 = 2i
Rec. no homogénea de e.c. (x-3)(x-2)
ti=c1·3i + c22i  como i = lg2 n y clg n=nlg c
ti = c1nlg 3 + c2nlg 2  t(n)  O(nlg 3)
Para determinar orden exacto, calcular c1, c2.
Resolución de recurrencias mediante el
cambio de variable
Cálculo de las constantes:
Sustituyendo ti = c1nlg 3 + c2nlg 2 en la ec. de rec.
Calculamos t(n) en dos puntos, obteniendo dos ec.
t(n)=c1·nlog3+c2·n
Obteniendo T(n) en dos puntos
Para n=1  t(1)=1 condición inicial
Para n=2  t(2)=3·t(1)+2=3·1+2=5
Resolución de recurrencias mediante el
cambio de variable
Sustituyendo en la solución general
c1+c2=1  n=1
t(2)=c1·2log3+c2·2=3·c1+2·c2=5  n=2
Resolviendo el sistema de ecuaciones
c1=3; c2= -2;
t(n) = 3·nlog3 –2·n, con n potencia de 2
t(n) (nlg 3) siendo n potencia de 2
Resolución de recurrencias mediante el
cambio de variable
Ejemplo 2:
No se puede aplicar el caso general,
que veremos más adelante.
T(n) = 2·T(n/2)+n·lg n, con n potencia
de 2
Cambio de variable n = 2i  i = lg2 n
Resolución de recurrencias mediante el
cambio de variable
ti = T(2i) = 2·T(2i-1) + 2i ·i = 2·ti-1 + 2i ·i
Rec. no homogénea donde b=2, p(i)=i con grd 1
ti – 2ti-1 = 2i·i  (x-2)(x-2)2 = (x-2)3
Solución general ti = c1·2i + c2·i2i + c3·i2·2i
Deshaciendo el cambio  [ n = 2i  i = lg n ]
T(n) = c1n + c2nlg n + c3nlg2n
T(n) O(n·lg2n) siendo n potencia de 2
Para conocer el orden exacto, calcular las
constantes
Resolución de recurrencias mediante el
cambio de variable
Para obtener las constantes sustituimos en la
recurrencia original :
n·lgn = T(n)-2·T(n/2)
n·lgn=(c1·n+c2·lgn·n+c3·n·lg2n)2(c1·(n/2)+c2·lg(n/2)·(n/2)+c3·(n/2)·lg2(n/2))
n·lgn=c1·n+c2·lgn·n+c3·n·lg2·nc1·n-c2·n·lg(n/2)-c3·n·lg2(n/2)
Resolución de recurrencias mediante el
cambio de variable
n·lgn=c2·n·lgn+c3·n·lg2n-c2·n(lgn-lg2)-c3·n(lgn-lg2)2
n·lgn=c2·n·lgn+c3·n·lg2n-c2·n·lgn+c2·nc3·n(lg2n+lg22-2·lgn·lg2)
n·lgn=c2·n-c3·n+2·c3·n·lgn
n·lgn=(c2–c3)·n+2·c3·n·lg n
Igualando coeficientes : c2 – c3 = 0; 2·c3 = 1
Resolviendo c2=c3= ½
T(n)  (n·lg 2n)
Resolución de recurrencias mediante el
cambio de variable Caso General
n0  1; l 1;
b 2; k 0 enteros; c>0 real.
T:NR+ no decreciente
T(n) = l· T(n/b) + c·nk
n >n0 1 , n/n0 es potencia exacta de b, es decir,
n  {bn0, b2n0, b3n0, ...}
Resolución de recurrencias mediante el
cambio de variable Caso General
Cambio de variable adecuado: n = bi·n0
ti = T(bi·n0) = l· T(bi-1·n0) + c·(bi·n0)k = l·ti-1 + c·n0kbik
ti – l·ti-1 = c·n0k·(bk)i (x-l)(x-bk)d+1 [pol. caraterístico]
[r1=l , r2=bk]
Las soluciones son de la forma: ti = c1li + c2(bk)i
Aunque en general es falso porque no se
consideran las raíces múltiples
Resolución de recurrencias mediante el
cambio de variable Caso General
Como n=bin0  i=logb(n/n0)
Si deshacemos el cambio de i
T(n) = c1·llogb(n/n0) + c2·(bk)logb (n /n0)
T(n) = c1·llogbn – logbn0 + c2·( bk)logbn - logbn0
T(n)=c1·(llogbn/llogbn0)+c2·((bk)logbn/(bk)logbn0)
Teniendo en cuenta lgbbk=k y llgbn=nlgbl
Resolución de recurrencias mediante el
cambio de variable Caso General
T(n) = c1·(nlogbl / n0logbl ) + c2·(nlogbbk / n0
log bk
b
)
T(n) = ( c1 /n0logbl ) · nlogbl + ( c2 /n0k )· nk
Llamando:
c3= c1 /n0logbl
, c4= c2 /n0k
T(n) = c3·nlogbl + c4·nk
Para conocer las constantes, sustituimos esta en la
recurrencia original.
Resolución de recurrencias mediante el
cambio de variable Caso General
T(n) = c3·nlogbl + c4·nk  c·nk = T(n) – l·T(n/b)
c·nk = c3·nlogbl + c4·nk – l(c3(n/b)logbl + c4(n/b)k)
c·nk = c·nk = c3·nlogbl + c4·nk – l·c3 ( nlogbl / blogbl )
– l·c4 (nk / bk )
c·nk = c3·nlogbl + c4·nk – l·c3 ( nlogbl / llogbb) – l·c4 (nk / bk )
c·nk = c3·nlogbl + c4·nk – l·c3 ( nlogbl / l) – l·c4 (nk / bk )
Resolución de recurrencias mediante el
cambio de variable Caso General
c·nk = c4·nk – l·c4 (nk / bk )
c·nk = c4·nk (1- ( l/bk ))
Por tanto:
c4  cl
1
k
Para expresar T(n) en notación asintótica,
necesitamos saber el cuál es el término
dominante en T(n)=c3·nlogbl+c4·nk, tenemos 3
casos:
b
Resolución de recurrencias mediante el
cambio de variable Caso General
Si l<bk en
c4 
c
1
l
b
k
c4>0 y k>logbl  c4nk dominante
T(n)  (nk | n/n0 potencia exacta de b)
Notación asintótica condicional: condicionada a que n/n0
sea potencia exacta de b.
Como T(n) es no creciente  T(n)  (nk).
Matemáticamente, si tenemos una función condicionada
a potencias, logaritmos o polinomios y es creciente, se
puede eliminar la condición.
Resolución de recurrencias mediante el
cambio de variable Caso General
Si
l>bk
en
c4 
c
1
l
b
k
c4<0 y k< logbl  c3 >0  c3nlogbl dominante
T(n)  (nlogbl | n/n0 sea potencia de b)
Como T(n) es no decreciente T(n)  (nlogbl )
Resolución de recurrencias mediante el
cambio de variable Caso General
Si l=bk en
c4 
c
1
l
b
k
Problema en c4de división por 0
El polinomio característico tiene una raíz de grado de
multiplicidad 2
La solución general: ti = c5(bk)i + c6i(bk)i
Como i=logb(n/n0)
T(n) = c7nk + c8nklogb(n/n0) c8=c distinto de cero
Término dominante: cnklogbn  T(n) (nklogbn)
Resolución de recurrencias mediante el
cambio de variable Caso General
Resumiendo T(n) = l·T(n/b) +c·nk, se comporta
k
  (n k )
si l  b

k
k
T ( n )    ( n lg n ) si l  b
  ( n lg b l ) si l  b k

Observación: En la notación asintótica no es necesario
especificar la base del algoritmo por la propiedad:
logan = logab · logbn  O(logan) = O(logbn)
Recurrencias
Resolución de recurrencias,
mediante transformación de
intervalo.
Resolución de recurrencias mediante
transformación de intervalo.
El cambio de variable transforma el dominio de la
recurrencia.
Podemos transformar el intervalo para obtener
una recurrencia que se pueda resolver.
Se pueden utilizar ambas transformaciones.
Cuando la recurrencia no es lineal o los
coeficientes no son constantes, se debe manipular
para que lo sea.
Resolución de recurrencias mediante
transformación de intervalo.
Ejemplo

1

3

T (n)  

2  n 
nT



 2 

si
n 1
si
n  1
T(n) definida cuando n es potencia de 2
“ nT2 “ , n es coeficiente no constante y T2
es una recurrencia no lineal.
Resolución de recurrencias mediante
transformación de intervalo.
Cambio de variable: ti=T(2i), n=2i  i=lg n
ti = T(2i) = 2iT2(2i-1) = 2iti-12
donde, no lineal y 2i no cte
Transformar el intervalo o rango:
Creamos otra recurrencia ui=lg ti  ti=2ui
ui=lg ti = log (2iti-12 ) = log (2i) + log (ti-12 )
ui= i + 2lg ti-1; ui= i +2ui-1
Por tanto: ui – 2ui-1 = i
Cuyo pol. caract. es (x-2)(x-1)2
Resolución de recurrencias mediante
transformación de intervalo.
ui = c12i + c21i + c3i1i
obtengo las ctes (...) sustituyendo la sol.
general en la recurrencia para ui
i=ui – 2·ui-1
i=c1·2i + c2·1i + c3·i·1i –
2(c1·2i-1+c2·1i-1+c3(i-1)·1i-1)
i= c2+ c3·i – 2 c2 –2·c3(i-1)
i= - c2+ c3·(i – 2(i-1)) = -c2 + c3( -i +2)
i= 2·c3 – c2 – c3·i
Resolución de recurrencias mediante
transformación de intervalo.
Igualando coeficientes en i= 2·c3 – c2 – c3·i
1= - c3 y 0 = 2c3 – c2
Resolviendo c3 = -1 y c2 = 2c3 = - 2
De c1 no tenemos información
Por tanto: ui = c12i –i –2
Deshacemos
los
dos
cambios
para
determinar la complejidad de la recurrencia
Resolución de recurrencias mediante
transformación de intervalo.
Deshacer el 2º cambio:
ti  2
 2
ui
i
c1 2  2  i
Deshacer el 1er cambio: (i=log2n)
T ( n )  t lg n  2
T (n)  2
c1 2
lg n
c1 n  (lg n  2 )
 lg n  2

2
2
2
c1 n
lg 2
 lg n  2
c1 n
lg n  2
2

2
2
c1 n  lg n  2
c1
lg n
2
2

2
c1 n
4n
Resolución de recurrencias mediante
transformación de intervalo.
Como tenemos una condición inicial podemos
conocer la constante c1
T(1) =1/3; T(1)= 2c1·1 / (4·1) =1/3
Despejando c1=lg2 (4/3); c1 = lg 4 – lg3 = 2 - lg3
T (n) 
2
( 2  lg 3 )· n

4n
2
4n2
2
n lg 3
Despreciando el 4 (cte)

2
2n
4n3
n lg 2

2
2n
4n3
  4 n


 3
T (n)   
n










n
Descargar

Recurrencias