Divide Y Venceras

Algoritmos
Algoritmos “Divide y Vencerás”
Análisis y Diseño de Algoritmos

Algoritmos “Divide y Vencerás”
Ejemplo:
Ejemplo: Multiplicación de enteros grandes
La
La técnica “divide y vencerás”
Características
Características
Método
Método general “divide y vencerás”
Eficiencia
Eficiencia de los algoritmos “divide y vencerás”
Aspectos
Aspectos de diseño
DeterminaciónDeterminación del umbral
Aplicaciones
Aplicaciones

1

Multiplicación
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Algoritmo
Algoritmo clásico
1234*5678
1234*5678 = 1234* (5*1000 + 6*100+7*10+8)
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
1234*5*1000
Operaciones básicas:
Multiplicaciones
Multiplicaciones de dígitos: O(1)
Sumas
Sumas de dígitos: O(1)Desplazamientos:
Desplazamientos: O(1)
Eficiencia algoritmo: O(n2)
O(n

2

Multiplicación de enteros
Multiplicación de enteros de n cifras:
Algoritmo
Algoritmo “divide y vencerás” simple
1234 = 12*100 + 34
5678 = 56*100 + 78
1234*5678 = (12*100 + 34)*(56*100 + 78)
= 12*56*10000 + (12*78+34*56)*100 + (34*78)
Idea: Se reduce una multiplicación de 4 cifras
a cuatro multiplicaciones de 2 cifras,más tres sumas y varios desplazamientos.

3

Multiplicación
Multiplicación de enteros
Multiplicación de enteros de n cifras:
Algoritmo
Algoritmo “divide y vencerás” simple
1.

Dividir
X = 12345678 = xi*104 + xd
12345678
xd
Y = 24680135 = yi*104 + yd
yi*10

2.

xi=1234
yi=2468
yi=2468

xd=5678
yd=0135

Combinar
xd) (yi*10
X*Y = (xi*104 + xd) * (yi*104 + yd)(xi*yd+xd*yi)*10
xd*yd
= xi*yi*108 + (xi*yd+xd*yi)*104 + xd*yd
xi*yi*10
4

Multiplicación de enteros
Multiplicación de enteros de n cifras:
Algoritmo
Algoritmo “divide y vencerás” simple
En general:
X = xi*10n/2 + xd
Y = yi*10n/2 + yd
yi*10
xd) (yi*10
X*Y = (xi*10n/2 + xd) * (yi*10n/2 + yd)
(xi*yd+xd*yi)*10
xd*yd
= xi*yi*10n + (xi*yd+xd*yi)*10n/2 + xd*yd
xi*yi*10

5

MultiplicaciónMultiplicación de enteros
función multiplica (X,Y,n)
(X,Y,n)
{
if (P es pequeño) {
return X*Y;
} else {
Obtener xi, xd, yi, yd;
xd, yi,
z1 = multiplica (xi, yi, n/2);
yi
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xd, yi, n/2);
(xd, yi,
z4 = multiplica (xd, yd, n/2);
(xd,
aux = suma(z2,z3);
z1 = desplaza_izq(z1,n);
desplaza_izq(z1,n);
aux = desplaza_izq(aux,n/2);desplaza_izq(aux,n/2);
z
= suma(z1,aux);
z
= suma(z,z4);
return z;
}
}

// DIVIDIR

// COMBINAR

6

Multiplicación de enteros
función multiplica (X,Y,n)
(X,Y,n)
{
if (P es pequeño) {
return X*Y;
} else {
Obtener xi, xd, yi, yd;
xd, yi,
z1 = multiplica (xi, yi, n/2);
yi
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xd, yi, n/2);
(xd, yi,
z4 = multiplica (xd, yd, n/2);
(xd,aux = suma(z2,z3);
z1 = desplaza_izq(z1,n);
desplaza_izq(z1,n);
aux = desplaza_izq(aux,n/2);
desplaza_izq(aux,n/2);
z
= suma(z1,aux);
z
= suma(z,z4);
return z;
}
}

Eficiencia
Eficiencia
O(1)
O(1)
O(n)
O(n)
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(1)
7

Multiplicación
Multiplicación de enteros
Multiplicación de enteros de n cifras:
AlgoritmoAlgoritmo “divide y vencerás” simple
T(n) = 4T(n/2) + n ∈ O(n2)
El
El cuello de botella está en el número de
multiplicaciones de tamaño n/2.
Para
Para mejorar la eficiencia debemos reducir el número
de multiplicaciones necesario…
8

Multiplicación de enteros
Multiplicación de enteros de n cifras:
Algoritmo
Algoritmo “divide y vencerás”
r = (xi+xd)*(yi+yd) = xi*yi + (xi*yd+xd*yi) +xd*yd
(xi+xd)*(yi+yd) xi*yi (xi*yd+xd*yi) xd*yd
p = xi*yi
q = xd*yd
xd*yd
(rX*Y = p*10n + (r-p-q)*10n/2 + q
Luego
Luego podemos realizar una multiplicación de tamaño n
a partir de 3 multiplicaciones de tamaño n/2.
9

Multiplicación
Multiplicación de enteros
función multiplicaDV (X,Y,n)
X,Y,n)
{
if (P es pequeño) {
return X*Y;
} else {
Obtener xi, xd, yi, yd;
xd, yi,
s1 =...