Algoritmos “Divide y Vencerás”
Algoritmos “Divide y Vencerás”
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
Algoritmos “Divide y Vencerás”
Algoritmos “Divide y Vencerás”
Ejemplo: Multiplicación de enteros grandes
Ejemplo: Multiplicación de enteros grandes
La técnica “divide y vencerás”
La técnica “divide y vencerás”
Características
Características
Método general “divide y vencerás”
Método general “divide y vencerás”
Eficiencia de los algoritmos “divide y vencerás”
Eficiencia de los algoritmos “divide y vencerás”
Eficiencia de los algoritmos “divide y vencerás”
Eficiencia de los algoritmos “divide y vencerás”
Aspectos de diseño
Aspectos de diseño
Determinación del umbral
Determinación del umbral
Aplicaciones
Aplicaciones
11
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo clásico
Algoritmo clásico
1234*5678 = 1234* (5*1000 + 6*100+7*10+8)
1234*5678 = 1234* (5*1000 + 6*100+7*10+8)
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
Operaciones básicas:
Operaciones básicas:
Multiplicaciones de dígitos: O(1)
Multiplicaciones de dígitos: O(1)
Sumas de dígitos: O(1)
Sumas de dígitos: O(1)
Desplazamientos: O(1)
Desplazamientos: O(1)
Eficiencia algoritmo: O(nO(n22))
Eficiencia algoritmo:
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple
1234 = 12*100 + 34
1234 = 12*100 + 34
5678 = 56*100 + 78
5678 = 56*100 + 78
5678 = 56*100 + 78
5678 = 56*100 + 78
1234*5678 = (12*100 + 34)*(56*100 + 78)
1234*5678 = (12*100 + 34)*(56*100 + 78)
= 12*56*10000 + (12*78+34*56)*100 + (34*78)
= 12*56*10000 + (12*78+34*56)*100 + (34*78)
Idea: Se reduce una multiplicación de 4 cifras
Idea: Se reduce una multiplicación de 4 cifras
a cuatro multiplicaciones de 2 cifras,
a cuatro multiplicaciones de 2 cifras,
más tres sumas y varios desplazamientos.
más tres sumas y varios desplazamientos.
22
33
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple
1.1. Dividir
Dividir
X = 12345678 = xi*1044 + + xdxd
X = 12345678 = xi*1044 + + xdxd
X = 12345678 = xi*10
X = 12345678 = xi*10
Y = 24680135 = yiyi*10*1044 + yd+ yd
Y = 24680135 =
xi=1234
xi=1234
xi=1234
xi=1234
yiyi=2468
=2468
xdxd=5678
xdxd=5678
=5678
=5678
yd=0135
yd=0135
2.2. Combinar
Combinar
X*Y X*Y = (xi*10
= (xi*1044 + + xdxd) * (
= xi*= xi*yiyi*10*1088 + (xi*+ (xi*yd+xd
) * (yiyi*10*1044 + yd)+ yd)
yd+xd**yiyi)*10
)*1044 + + xdxd*yd*yd
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple
En general:
En general:
X = xi*10n/2n/2 + + xdxd
X = xi*10
Y = Y = yiyi*10*10n/2n/2 + yd+ yd
X*Y X*Y = (xi*10
= (xi*10n/2n/2 + + xdxd) * (
= xi*= xi*yiyi*10*10nn + (xi*+ (xi*yd+xd
) * (yiyi*10*10n/2n/2 + yd)+ yd)
yd+xd**yiyi)*10
)*10n/2n/2 + + xdxd*yd*yd
44
55
Multiplicación de enteros
Multiplicación de enteros
función multiplica (
función multiplica (X,Y,n
{{
X,Y,n) )
(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;
} } else
else {{
Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
z1 = multiplica (xi,
z1 = multiplica (xi, yiyi, n/2);
z1 = multiplica (xi,
z1 = multiplica (xi, yiyi, n/2);
, n/2);
, n/2);
z2 = multiplica (xi, yd, n/2);
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xdxd, , yiyi, n/2);
z3 = multiplica (
, n/2);
z4 = multiplica (
z4 = multiplica (xdxd, yd, n/2);
, yd, n/2);
auxaux = suma(z2,z3);
= suma(z2,z3);
z1 =
z1 = desplaza_izq
auxaux = = desplaza_izq
z = suma(z1,aux);
z = suma(z1,aux);
z = suma(z,z4);
z = suma(z,z4);
return
return z;z;
desplaza_izq(z1,n);
(z1,n);
desplaza_izq((aux,n
aux,n/2);
/2);
// DIVIDIR
// DIVIDIR
// COMBINAR
// COMBINAR
}}
}}
Multiplicación de enteros
Multiplicación de enteros
función multiplica (
función multiplica (X,Y,n
{{
X,Y,n) )
(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;
} } else
else {{
Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
z1 = multiplica (xi, yiyi, n/2);
z1 = multiplica (xi,
z1 = multiplica (xi,
z1 = multiplica (xi, yiyi, n/2);
, n/2);
, n/2);
z2 = multiplica (xi, yd, n/2);
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xdxd, , yiyi, n/2);
z3 = multiplica (
, n/2);
z4 = multiplica (
z4 = multiplica (xdxd, yd, n/2);
, yd, n/2);
auxaux = suma(z2,z3);
= suma(z2,z3);
z1 =
z1 = desplaza_izq
auxaux = = desplaza_izq
z = suma(z1,aux);
z = suma(z1,aux);
z = suma(z,z4);
z = suma(z,z4);
return
return z;z;
desplaza_izq(z1,n);
(z1,n);
desplaza_izq((aux,n
aux,n/2);
/2);
}}
}}
Eficiencia
Eficiencia
O(1)
O(1)
O(1)
O(1)
O(n)
O(n)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O(1)
66
77
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple
T(n) = 4T(n/2) + n ∈∈ O(nO(n22))
T(n) = 4T(n/2) + n
El cuello de botella está en el número de
El cuello de botella está en el número de
multiplicaciones de tamaño n/2.
multiplicaciones de tamaño n/2.
Para mejorar la eficiencia debemos reducir el número
Para mejorar la eficiencia debemos reducir el número
de multiplicaciones necesario…
de multiplicaciones necesario…
88
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
xi+xd)*()*(yi+yd
yi+yd) = xi*
) = xi*yiyi + (xi*+ (xi*yd+xd
r = (
r = (xi+xd
p = xi*
p = xi*yiyi
p = xi*
p = xi*yiyi
q = q = xdxd*yd*yd
yd+xd**yiyi) +
) + xdxd*yd*yd
X*Y = p*10nn + (r+ (r--pp--q)*10
X*Y = p*10
q)*10n/2n/2 + q+ q
Luego podemos realizar una multiplicación de tamaño n
Luego podemos realizar una multiplicación de tamaño n
a partir de 3 multiplicaciones de tamaño n/2.
a partir de 3 multiplicaciones de tamaño n/2.
99
Multiplicación de enteros
Multiplicación de enteros
función
función multiplicaDV
{{
multiplicaDV ((X,Y,n
X,Y,n) )
(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;
} } else
else {{
xi,xd););
xi,xd););
yi,yd););
(xi, yiyi, n/2);
multiplicaDV (xi,
, n/2);
multiplicaDV ((xdxd, yd, n/2);
, yd, n/2);
multiplicaDV (s1, s2, n/2);
(s1, s2, n/2);
= suma(r,--p,p,--q);
q);
Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
s1 = suma(
s1 = suma(xi,xd
s1 = suma(
s1 = suma(xi,xd
s2 = suma(
s2 = suma(yi,yd
p =
p = multiplicaDV
q =
q = multiplicaDV
r =
r = multiplicaDV
auxaux = suma(r,
auxaux = = desplaza_izq
p =
p = desplaza_izq
z = suma(
z = suma(p,aux,q
return
return z;z;
desplaza_izq((p,np,n););
desplaza_izq((aux,n
aux,n/2);
/2);
p,aux,q););
// DIVIDIR
// DIVIDIR
// COMBINAR
// COMBINAR
}}
}}
Multiplicación de enteros
Multiplicación de enteros
función
función multiplicaDV
{{
multiplicaDV ((X,Y,n
X,Y,n) )
(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;
} } else
else {{
xi,xd););
xi,xd););
yi,yd););
(xi, yiyi, n/2);
multiplicaDV (xi,
, n/2);
multiplicaDV ((xdxd, yd, n/2);
, yd, n/2);
(s1, s2, n/2);
multiplicaDV (s1, s2, n/2);
= suma(r,--p,p,--q);
q);
Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
s1 = suma(
s1 = suma(xi,xd
s1 = suma(
s1 = suma(xi,xd
s2 = suma(
s2 = suma(yi,yd
p =
p = multiplicaDV
q =
q = multiplicaDV
r =
r = multiplicaDV
auxaux = suma(r,
auxaux = = desplaza_izq
p =
p = desplaza_izq
z = suma(
z = suma(p,aux,q
return
return z;z;
desplaza_izq((p,np,n););
desplaza_izq((aux,n
aux,n/2);
/2);
p,aux,q););
}}
}}
Eficiencia
Eficiencia
O(1)
O(1)
O(1)
O(1)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O(1)
1010
1111
Multiplicación de enteros
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
=
)(
nT
∈+
3T(n/2)
(O n
log 2
3
n
=
)
.1
nO
(
585
)
Implementación
Implementación
Operaciones
n = 10
n = 100
n = 1000
básica
n2
0.1 ms
10 ms
1 segundo
eficiente
n1.585
0.04 ms
1.48 ms
56.9 ms
n = 10000
100 segundos
2.19 segundos
La técnica “divide y vencerás”
La técnica “divide y vencerás”
La técnica “divide y vencerás” (DV) consiste en:
La técnica “divide y vencerás” (DV) consiste en:
Descomponer el problema que hay que resolver en
Descomponer el problema que hay que resolver en
cierto número de
subproblemas más pequeños del
más pequeños del
cierto número de subproblemas
mismo tipo.
mismo tipo.
mismo tipo.
mismo tipo.
Resolver de forma sucesiva e independiente todos
Resolver de forma sucesiva e independiente todos
estos subproblemas
estos
subproblemas..
Combinar las soluciones obtenidas para obtener la
Combinar las soluciones obtenidas para obtener la
solución del problema original.
solución del problema original.
1212
1313
La técnica “divide y vencerás”
La técnica “divide y vencerás”
Características de los problemas
Características de los problemas
resolubles utilizando “divide y vencerás”
resolubles utilizando “divide y vencerás”
El problema se puede descomponer en otros del mismo
El problema se puede descomponer en otros del mismo
tipo que el original y de tamaño más pequeño
tipo que el original y de tamaño más pequeño
tipo que el original y de tamaño más pequeño
t
Comentarios de: Análisis y Diseño de Algoritmos - Algoritmos "Divide y Vencerás" (0)
No hay comentarios