ejercicios resueltos análisis de algoritmos

ejercicios resueltos análisis de algoritmos

1. Universidad Andres Bello
Facultad de Ingeniera
Ingeniera en Computacion e Informatica
Dise~no de Algoritmos
Ejercicios Resueltos - Analisis
Prof. Catedra: Carlos Contreras Bolton Fecha:25 de Marzo de 2014
Profs. Laboratorio:Daniela Ubilla{Felipe Reyes
Ejercicio 1: Sumatoria
n
X
i=1
i= 1 + 2 + 3 +:::+ (n1) +n(1)
Si invertimos la suma tenemos:
n
X
i=1
i=n+ (n1) +:::+ 3 + 2 + (2)
Si sumamos componente a componente (1) y (2) tenemos:
2
n
X
i=1
i= (1 +n) + (2 + (n1)) + (3 + (n2)) +:::+ ((n1) + 2) + (n+ 1) (3)
Que es lo mismo que:
2
n
X
i=1
i= (n+ 1) + (n+ 1) + (n+ 1) +:::+ (n+ 1) + (n+ 1) (4)
La parte derecha esta compuesta pornsumas den+ 1:
2
n
X
i=1
i=n(n+ 1) (5)
Finalmente:
n
X
i=1
i=
n(n+ 1)
2

2. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 2: Resolver
Resolver:
T(n) =T(
p
n) +c;T(1) =d;T(2) =d;
Expandimos:
T(n) =T(
p
n) +c
=T(n
1
2) +c
=
h
T

n
1
2
2

+c
i
+c
=T

n
1
2
2

+ 2c
=
h
T

n
1
2
3

+c
i
+ 2c
=T

n
1
2
3

+ 3c
.
.
.
=T

n
1
2
k

+kc
Expandimos hastaT(2), entonces:
n
1
2
k
= 2
2
kp
n= 2
n= 2
2
k
2
k
= log
2n
k= log
2log
2n
Continuamos:
=T

n
1
2
k

+kc
=T(2) +kc
=d+clog
2log
2n
=O(log
2log
2n)
Carlos Contreras Bolton
2

3. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 3: Resolver
T(n) = 3
n
2
+n
2
n;T(1) = 1 (1)
Expandimos:
T(n) = 3T(
n
2
) +n
2
n
= 3

3T

n
4

+

n
2

2

n
2

+n
2
n= 9T

n
4

+ 3

n
2
4

n
2

+n
2
n
= 27T

n
8

+ 9

n
2
16

n
4

+ 3

n
2
4

n
2

+n
2
n
.
.
.
= 3
i
T

n
2
i

+n
2
i1
X
j=0
(
3
4
)
j
+n
i1
X
j=0
(
3
2
)
j
= 3
i
T

n
2
i

4n
2

3
4

i
+ 4n
2
2n

2
3

i
+ 2npor
n
X
i=0
a
i
=
a
n+1
1
a1
.
.
.
= 3
logn
T

n
2
logn

4n
2

3
4

logn
+ 4n
2
2n

2
3

logn
+ 2n
=n
log 3
T(1)4n
log 3
+ 4n
2
2n
log 3
+ 2n
= 4n
2
5n
log 3
+ 2n
=O(n
2
)
Carlos Contreras Bolton
3

4. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 4: Resolver
Usando el metodo de la sustitucion:
T(n) = 2T

n
2

+bnlogn
Adivinamos queO(nlogn).
ProbarT(n)cnlognpor induccion.
T(n) = 2T(
n
2
) +bnlogn
= 2

c

n
2

log
n
2

+bnlogn
=cn(lognlog 2) +bnlogn
=cnlogncn+bnlogn
=cnlogn(cnbnlogn)
No se cumple, puesto que no podemos hacer que esta ultima lnea sea menor quecnlogn
Entonces, adivinamos queO(nlog
2
n).
ProbarT(n)cnlog
2
npor induccion.
T(n) = 2T(
n
2
) +bnlogn
= 2

c

n
2

log
2n
2

+bnlogn
=cn(lognlog 2)
2
+bnlogn
=cnlog
2
n2cnlogn+cn+bnlogn
=cnlog
2
n(2cnlogncnbnlogn)
Sic > b. Por lo tanto,T(n) =nlog
2
n.
Carlos Contreras Bolton
4

5. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 5: Resolver
T(n) =
1
n
P
n1
i=0
T(i) +cn, con T(0)=0.
T(n) =
1
n
n1
X
i=0
T(i) +cn(1)
Multiplicar pornen (1):
nT(n) =
n1
X
i=0
T(i) +cn
2
(2)
Desplazando (2) enn1:
(n1)T(n1) =
n2
X
i=0
T(i) +c(n1)
2
(3)
Restando (2)-(3):
nT(n)(n1)T(n1) = (
n1
X
i=0
T(i)
n2
X
i=0
T(i)) + (cn
2
c(n1)
2
) (4)
nT(n)(n1)T(n1) = ((T(0)+:::+T(n2)+T(n1))(T(0)+:::+T(n2)))+(cn
2
c(n
2
2n+1)) (5)
nT(n)(n1)T(n1) =T(n1) + 2cnc(6)
nT(n) =nT(n1) + 2cnc(7)
Dividiendo (7) porn:
T(n) =T(n1) +
2cnc
n
(8)
Expandiendo:
T(n) =
2cnc
n
+T(n1)
=
2cnc
n
+
2c(n1)c
n1
+T(n2)
=
2cnc
n
+
2c(n1)c
n1
+
2c(n2)c
n2
+T(n3)
=
2cnc
n
+
2c(n1)c
n1
+
2c(n2)c
n2
+:::+
2c(1)c
1
+T(0)
=

2cn
n
+
2c(n1)
n1
+
2c(n2)
n2
+:::+
2c(1)
1



c
n
+
c
n1
+
c
n2
+:::+
c
1

= (2c+ 2c+ 2c+:::+ 2c)

c
n
X
i=1
1
i
!
= 2cn

c
n
X
i=1
1
i
!
= 2cncHn
<2cn
Por lo tanto,T(n) =O(n).
Carlos Contreras Bolton
5

6. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 6: Resolver
T(n) =n1 +
2
n
n1
X
i=1
T(i); n2: T(1) = 0 (1)
Re-escribir la recurrencia paran+ 1:
T(n+ 1) = (n+ 1)1 +
2
n+ 1
n
X
i=1
T(i) (2)
Multiplicar (1) porny (2) porn+ 1:
nT(n) =n(n1) + 2
n1
X
i=1
T(i) (3)
(n+ 1)T(n+ 1) = (n+ 1)n+ 2
n
X
i=1
T(i) (4)
Restar (4)-(3):
(n+ 1)T(n+ 1)nT(n) = (n+ 1)nn(n1) + 2(
n
X
i=1
T(i)
n1
X
i=1
T(i)) (5)
(n+1)T(n+1)nT(n) = 2n+2((T(0)+T(1)+:::+T(n1)+T(n))(T(0)+T(1)+:::+T(n1))) (6)
(n+ 1)T(n+ 1)nT(n) = 2n+ 2T(n) (7)
T(n+ 1) =
n+ 2
n+ 1
T(n) +
2n
n+ 1
(n2) (8)
Podemos simplicar 2n=(n+ 1) como cota inferior 2.
T(n+ 1)
n+ 2
n+ 1
T(n) + 2 (9)
T(n)
n+ 1
n
T(n1) + 2 (10)
Expandiendo (10):
T(n)2 +
n+ 1
n
T(n1)
= 2 +
n+ 1
n

2 +
n
n1
T(n2)

= 2 +
n+ 1
n

2 +
n
n1

2 +
n1
n2
T(n3)

= 2 +
n+ 1
n

2 +
n
n1

2 +
n1
n2

2 +
n2
n3
T(n4)

>Hasta donde llega la expansion? hasta llegar aT(3)
4
3
T(2)+2 = 2+
4
3
(
3
2
T(1)+2), comoT(1) = 0,
entoncesT(3)2 +
4
3
(2) (este es el motivo del 4/3 visto en el ejercicio en clases).
Continuando con la expansion:
Carlos Contreras Bolton
6

7. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
T(n)2 +
n+ 1
n

2 +
n
n1

2 +
n1
n2

2 +
n2
n3

::;2 +
4
3
(2)

= 2

1 +
n+ 1
n
+
n+ 1
n
n
n1
+
n+ 1
n
n
n1
n1
n2
+:::+
n+ 1
n
n
n1
n1
n2
:::
4
3

= 2

1 +
n+ 1
n
+
n+ 1
n1
+
n+ 1
n2
+:::+
n+ 1
3

= 2(n+ 1)

1
n+ 1
+
1
n
+
1
n1
+:::+
1
3

= 2(n+ 1)

1
n+ 1
+
1
n
+
1
n1
+:::+
1
3
+
1
2
+ 1

1
2
+ 1

= 2(n+ 1)(H(n+ 1)1;5)
Recuerden queH(n) = 1 + 1=2 + 1=3 +:::+ 1=nes la serie harmonica, la cual tiene una aproximacion
aH(n) = lnn++O(1=n), donde= 0;577::es la constante de Euler. Entonces la solucion aT(n) es:
T(n)2(n+ 1)(lnn+1;5) +O(1) =O(nlogn)
Carlos Contreras Bolton
7

8. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 7: Resolver
T(n) =
(
a ifn= 1;
2T(n=4) + lognifn >1:
T(n) = 2T

n
4

+ logn
= 2

2T

n
4
2

+ log

n
4

+ logn = 2
2
T

n
4
2

+ 2 log

n
4

+ logn
= 2

2

2T

n
4
3

+ log

n
4
2

+ log

n
4

+ logn= 2
3
T

n
4
3

+ 2
2
log

n
4
2

+ 2 log

n
4

+ logn
=:::
= 2
i
T

n
4
i

+
i1
X
k=0
log

n
4
k

= 2
i
T

n
4
i

+ logn
i1
X
k=0
2
k

i1
X
k=0
2
k
log 4
k
Considerandoncomo potencia de 4 y todos los logaritmos en base 4 (la base no importa tanto, lo
importante es que es logaritmo) tenemos:
T(n) = 2
i
T

n
4
i

+ log
4n
i1
X
k=0
2
k

i1
X
k=0
2
k
log
44
k
=:::
= 2
i
T(1) + log
4n
i1
X
k=0
2
k

i1
X
k=0
2
k
k
=a2
i
+ log
4n(2
i
1)(i2)2
i
2
Considerando quenes potencia de 4, entoncesn= 4
i
ei= log
4n. Tambien podemos obtener que
p
n= 2
i
.
T(n) =a2
i
+ log
4n(2
i
1)(i2)2
i
2
=a
p
n+ log
4n(
p
n1)(log
4n2)
p
n2
= (a+ 2)
p
nlog
4n2
Por lo tantoT(n) = (
p
n).
Carlos Contreras Bolton
8

9. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
Ejercicio 8: Resolver
T(n) =
(
1 n= 1
P
n1
i=1
T(i) +n
2
n2
Si restamosT(n1) aT(n) tenemos:
T(n)T(n1) =

n1
X
i=1
T(i) +n
2
!


n2
X
i=1
T(i) + (n1)
2
!
=

n2
X
i=1
T(i) +T(n1) +n
2
!


n2
X
i=1
T(i) +n
2
2n+ 1
!
=T(n1) + 2n1
Si despejamos tenemos:
T(n) = 2T(n1) + 2n1
Expandiendo la recurrencia:
T(n) = 2T(n1) + 2n1
= 2(2T(n2) + 2(n1)1) + 2n1
= 2
2
T(n2) + 2
2
(n1)2 + 2n1
= 2
2
(2T(n3) + 2(n2)1) + 2
2
(n1)2 + 2n1
= 2
3
T(n3) + 2
3
(n2)2
2
+ 2
2
(n1)2 + 2n1
= 2
3
T(n3) + (2
3
(n2) + 2
2
(n1) + 2n)(2
2
+ 2 + 1)
= 2
3
T(n3) + (2
3
(n2) + 2
2
(n1) + 2
1
(n0))(2
2
+ 2
1
+ 2
0
)
:::
= 2
i
T(ni) +
i1
X
j=0
2
j+1
(nj)
i1
X
j=0
2
j
= 2
i
T(ni) +n
i1
X
j=0
2
j+1

i1
X
j=0
j2
j+1

i1
X
j=0
2
j
= 2
i
T(ni) + 2n
i1
X
j=0
2
j
2
i1
X
j=0
j2
j

i1
X
j=0
2
j
:::
= 2
i
T(ni) + (2n1)
i1
X
j=0
2
j
2
i1
X
j=0
j2
j
Al caso base se llega cuandoni= 1, entoncesi=n1:
T(n) = 2
n1
T(1) + (2n1)
n2
X
j=0
2
j
2
n2
X
j=0
j2
j
Considerando que:
Carlos Contreras Bolton
9

10. Dise~no de Algoritmos Ejercicios Resueltos - Analisis
n2
X
j=0
2
j
= 2
n1
1
n2
X
j=0
j2
j
= (n3)2
n1
+ 2
Reemplazando en la recurrencia:
T(n) = 2
n1
+ (2n1)(2
n1
1)2((n3)2
n1
+ 2)
= (1 + 2n12n+ 6)2
n1
2n+ 14
= 62
n1
2n3
= 32
n
2n3
2(2
n
)
Carlos Contreras Bolton
10