Tema 3

Algoritmos divide y vencerás

 Tema 3
Algoritmos divide y vencerás
4.1 Características del método divide y vencerás.
4.2 Búsqueda binaria.
4.3 Multiplicación de grandes enteros.
4.4 Elaboración de un calendario deportivo.
4.5 Ordenación por mezcla (mergesort).
4.6 Ordenación rápida (quicksort).
4.7 Otros problemas.
3.1 Características del método divide y vencerás.

La técnica divide y vencerás consiste en:

 Descomponer el ejemplar a resolver en un cierto número de subejemplares más
pequeños (independientes) del mismo problema.
 Resolverlos independientemente volviendo a aplicar la técnica si es necesario
(recursividad).
 Combinar los resultados obtenidos para construir la solución del problema.
Para que el proceso recursivo termine, es necesario establecer el caso base.
3.1 Características del método divide y vencerás.
algoritmo divide y venceras (ENT x:problema; SAL z:resultado)
variables
y : problema
i, k : entero
principio {divide y vencerás}
si x pequeño entonces z ←solución simple (x)
si no
descomponer(x,x1,x2,…,xn)
para i = 1 a k hacer divide y vencerás (xi,yi) fin para
z ← combinar(y1,y2,…,yn)
fin si
fin {divide y vencerás}
3.1 Características del método divide y vencerás.
• Solución simple es el subalgoritmo usado para resolver ejemplares pequeños del
problema a los que llamaremos casos base.
• El número k de subejemplares debe ser pequeño e independiente del problema
concreto a resolver (es frecuente que sea una potencia de 2). Si k = 1 a la técnica se
le llama reducción o simplificación.
• Para que la técnica sea rentable:
 Los problemas deben ser independientes.
 La descomposición de x en subejemplares y la combinación de sus resultados
ha de ser eficiente.
 El tamaño de los subejemplares debe ser tan parecido como sea posible.
 Si es posible utilizar algoritmos iterativos en lugar de recursivos, se obtiene una
mejora drástica en el espacio de memoria.
3.1 Características del método divide y vencerás.
Como ya estudiamos, el tiempo de ejecución de los algoritmos divide y vencerás es:
c1nk si 1 ≤ n < b
t(n) =ቊ
aT(n/b)+c2nk si n ≥ b
donde c1, c2, a y k son números reales, n y b números naturales, y a > 0, c > 0, k ≥
0 , b > 1.
Entonces:
(nk) si a<bk
t(n) =ቐ(nklog n) si a=bk
(nlogba) si a>bk

La complejidad es polinómica o polilogarítmica, pero nunca exponencial.

3.2 Búsqueda binaria.
Dado un vector ordenado de números enteros no repetidos, queremos conocer si un
elemento x está en él y queremos conocer su posición.

3 5 8 10 13 14 29 34

 Si x=9, la respuesta es que no está

 Si x=10, está en la posición 4
3.2 Búsqueda binaria.
Dado un vector ordenado de números enteros no repetidos, queremos conocer si un
elemento x está en él y queremos conocer su posición.

3 5 8 10 13 14 29 34

 Primera solución: Recorrer el vector hasta localizar el elemento o hasta el final O(n)
 Búsqueda binaria.
3.2 Búsqueda binaria.
Dado un vector ordenado de números enteros, queremos conocer si un elemento x
está en él y queremos conocer su posición.
Encontrar un i tal que 0 ≤ i ≤ n que cumpla T[i] ≤ x < T[i+1], con el convenio implícito
de que T[0] = −∞ y T[n+1] =+∞.

3 5 8 10 13 14 29 34

 Búsqueda binaria
• Dividir el problema en subproblemas: 2 en este caso.
• Quedarnos con una de las mitades: Si el elemento a buscar es menor que el
central, buscar en la primera mitad y, si no, en la segunda (reducción).
• Caso base: Tabla con un elemento.
3.2 Búsqueda binaria.
x=13
3 5 8 10 13 14 29 34

3 5 8 10 13 14 29 34

3 5 8 10 13 14 29 34

3 5 8 10 13 14 29 34
3.2 Búsqueda binaria.
algoritmo búsqueda binaria (ENT T:tabla[1..n] de elementos, x:elemento; SAL i:entero)
variables j: entero
principio {búsqueda binaria}
i 1; j n
mientras i<j hacer
k (i + j)/2
si x < T[k] entonces j  k –1
sino si x = T[k] entonces i, j k
sino i k + 1
fin si
fin si
fin mientras
fin {búsqueda binaria}

 Complejidad: O(log2 n)
3.2 Búsqueda binaria.
algoritmo búsqueda binaria 2 (ENT T:tabla[1..n] de elementos, i, j:1..n, x:elemento; SAL
posición:1..n)
{Busca x en el subvector T[i..j]. Se verifica que T[i] ≤ x < T[j + 1] y i ≤ j}
variables j: entero
principio {búsqueda binaria 2}
si i=j entonces posición i
si no
k (i + j + 1) div 2
si x < T[k] entonces búsqueda binaria 2 (T, i, k - 1, x, posición)
si no búsqueda binaria 2 (T, k, j, x, posición)
fin si
fin si
fin {búsqueda binaria 2}
 Complejidad: O(log2 n)
3.3 Multiplicación de grandes enteros.
En algunas aplicaciones se necesita trabajar con enteros muy grandes y no es
recomendable representarlos en coma flotante ya que sólo se conservarían sus cifras
más representativas.
 Representaremos los números mediante vectores
Hasta este momento, siempre hemos dicho que la suma y la multiplicación de dos
enteros eran operaciones elementales cuyo tiempo de ejecución estaba acotado por
una constante.
 Los algoritmos de multiplicación clásicos utilizan un tiempo cuadrático O(n2).
3.3 Multiplicación de grandes enteros.
Vamos ahora a utilizar divide y vencerás:
 Dividimos cada número en dos mitades:
X = a10n/2 + b Y = c10n/2 + d
 Entonces: X.Y = ac10n + (ad + bc)10n/2 + bd
 Para calcular X.Y tendremos que calcular ac, ad+bc y bd, para lo que sólamente
serán necesarios tres productos: v = ac, u = (a + b)(c + d) y w = bd puesto que
ad + bc = u − v − w.

Entonces: T(n) = 3T(n/2)+kn, donde k es la constante que representa el coste de las

sumas y traslaciones. Además, el caso base será n=1 y T(1)=1.
Por tanto, O(nlog 3), aproximadamente O(n1,59), luego mejora el caso clásico para
valores de n grandes.
3.3 Multiplicación de grandes enteros.
Ejemplo: Queremos multiplicar los números 1963 y 3521.
Tendríamos que calcular:
 v = 19∗35
 v = 1 ∗ 3, w = 9 ∗ 5, u = 10 ∗ 8
por tanto, ad + bc =u − v − w = 32 y el producto 19 ∗ 35 valdrá 3 ∗ 102 + 32 ∗ 10 + 45 = 665.
 w = 63∗21
 v = 6 ∗ 2, w = 3 ∗ 1 y u = 9 ∗ 3
por tanto ad + bc =u − v − w = 12 y el producto 63 ∗ 21 valdrá 1323
 u = (19+63)∗(35+21)=82∗56
 v = 8 ∗ 5, w = 2 ∗ 6 y u = 10 ∗ 11
por tanto ad + bc = u − v − w = 58 y el producto 82 ∗ 56 será 4592.
Entoces, ad + bc = 4592 − 1323 − 665 = 2604
1963 ∗ 3521= 665 ∗ 104 + 2604 ∗ 102 + 1323 = 6911723.
3.3 Multiplicación de grandes enteros.
algoritmo multiplicar(ENT x,y:entero-grande, n:entero; SAL z:entero-grande)
{Calcula en z el producto de los enteros x e y de tamaño n}
variables a, b, c, d, u, v, w : entero-grande
principio {multiplicar}
si n =1 entonces z  x ∗ y
si no
a  x div 10n/2; b  x mod 10n/2
c  y div 10n/2; d  y mod 10n/2
multiplicar(a + b, c + d, n/2, u)
multiplicar(a, c, n/2, v)
multiplicar(b, d, n/2,w)
z  v ∗ 10n + (u − v − w) ∗ 10n/2 + w
fin si
fin {multiplicar}
3.4 Elaboración de un calendario deportivo.
Se tiene que elaborar un calendario deportivo para una serie de competiciones
donde cada participante debe competir exactamente una vez con cada uno de los
demás. Supondremos n=2k.
Asignaremos a cada participante un número entre 1 y n de forma que tendremos que
elaborar n − 1 partidos
días
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 1 4 3 8 5 6 7
participantes 3
4 1 2 7 8 5 6
4 3 2 1 6 7 8 5
5 6 7 8 1 2 3 4
6 5 8 7 4 1 2 3
7 8 5 6 3 4 1 2
8 7 6 5 2 3 4 1
3.4 Elaboración de un calendario deportivo.
 Primera solución: Crear una tabla n*(n-1) donde en las filas están los participantes
y en las columnas los días. Los números de cada fila y de cada columna deben ser
distintos. O(n!)
 Divide y vencerás:
 Dividir en problema en subproblemas
 Caso base: Dos competidores que se enfrentan en una única competición.
días
1 2 3 4 5 6 7 1 2 3
1 2 3 4 5 6 7 8 1 2 3 4
1 2
2 1 4 3 8 5 6 7 2 1 4 3
participantes 2 1
3 4 1 2 7 8 5 6 3 4 1 2
4 3 2 1 6 7 8 5 4 3 2 1
5 6 7 8 1 2 3 4
6 5 8 7 4 1 2 3
7 8 5 6 3 4 1 2
8 7 6 5 2 3 4 1
3.4 Elaboración de un calendario deportivo.
algoritmo calendario (ENT inf, sup: 1..n; ENT-SAL t: tabla [1..n][1..n-1])
variables
medio : 1..n
principio {calendario}
si inf= sup-1 entonces
t [inf, 1]  sup
t [sup, 1]  inf
si no
medio  ( inf+ sup) div 2
calendario ( inf, medio, t )
calendario ( medio + 1, sup, t )
completar (inf, medio, medio –inf+ 1, sup-inf, medio + 1, t )
completar ( medio + 1, sup, medio –inf+ 1, sup-inf, inf, t )
fin si
fin {calendario}
3.4 Elaboración de un calendario deportivo.
algoritmo completar(ENT equipoinf, equiposup, diainf, diasup, equipoini: 1..n;
ENT-SAL t: tabla [1..n][1..n-1])
variables i, j : 1..n
principio {completar}
para j=diainf a diasup hacer
t [equipoinf, j]  equipoini+ j -diainf
fin para
para i = equipoinf+ 1 a equiposup hacer
t[i, diainf]  t [i-1, diasup]
para j = diainf+ 1 a diasup hacer
t [i, j]  t [i –1, j –1]
fin para
fin para
fin {completar}
3.4 Elaboración de un calendario deportivo.

La ecuación en recurrencia es:

2t(n/2) + bn2, si n > 2

t(n) = ቊ
a, si n = 2

Y, por tanto, O(n2) debido al algoritmo completar.

3.5 Ordenación por mezcla (mergesort).
Ordenar un vector v de n elementos.

7 5 8 10 2 14 3 4

 Se divide el vector en dos subvectores de aproximadamente el mismo tamaño y se

ordenan llamando recursivamente a la función.

5 7 8 10 2 3 4 14

 Se utiliza un algoritmo de mezcla para obtener una única tabla a partir de las dos
ordenadas.
2 3 4 5 7 8 10 14

 Caso base: un elemento

3.5 Ordenación por mezcla (mergesort).
algoritmo mergesort(ENT i, j:1..n; ENT-SAL v:tabla[1..n])
variables
medio : 1..n
principio{mergesort}
si i < j entonces
medio  (i + j) div 2
mergesort(i,medio, v)
mergesort(medio + 1, j, v)
mezclar(i,medio, j, v)
fin si
fin{mergesort}
3.5 Ordenación por mezcla (mergesort).
algoritmo mezclar(ENT inf,med, sup:1..n; ENT-SAL v:tabla[1..n])
{El algoritmo mezclar ordenará los elementos de las subtablas v[inf..med] y v[med + 1..sup] ya ordenadas}
variables
vaux :tabla[1..n]
i1, j1, j, indice : 1..n
principio{mezclar}
i1  inf
i2  medio + 1
j  inf
mientras i1 ≤ medio y i2 ≤ sup hacer
si v[i1] ≤ v[i2] entonces
vaux[j]  v[i1]
i1  i1 + 1
si no
vaux[j]  v[i2]
i2  i2 + 1
fin si
jj+1
fin mientras
3.5 Ordenación por mezcla (mergesort).
si i2>sup;
para indice = i1 a medio hacer
vaux[j]  v[indice]
jj+1
fin para
Si no:
para indice = i2 a sup hacer
vaux[j]  v[indice]
jj+1
fin para
para indice = inf a sup hacer
v[indice]  vaux[indice]
fin para
fin{mezclar}
Mezclar necesita una gran capacidad de almacenamiento
La ecuación en recurrencia es:
2t(n/2) + bn, si n > 1
t(n) = ቊ Complejidad: O(log n)
a, si n = 1
3.6 Ordenación rápida de Hoare (quicksort).
Ordenar un vector v de n elementos.
7 5 8 10 2 14 3 4

 Se elige como pivote un elemento cualquiera de la tabla y se permutan el resto de

elementos de forma que los mayores que el pivote queden a su derecha y los
restantes a su izquierda.
Supongamos que el pivote es el primer elemento: 7
2 5 4 3 7 14 10 8

 Utilizando recursividad, se ordenan la parte izquierda y la derecha siguiendo el

mismo proceso.
 Si el pivote es la mediana las dos partes en las que dividimos el vector son de igual
tamaño.
3.6 Ordenación rápida de Hoare (quicksort).
Ordenar un vector v de n elementos.
7 5 8 10 2 14 3 4

se mueve hacia derecha se mueve hacia la izquierda

buscando los mayores que pivote buscando los menores o iguales que pivote

7 5 8 10 2 14 3 4

7 5 4 10 2 14 3 8
3.6 Ordenación rápida de Hoare (quicksort).

7 5 4 3 2 14 10 8

7 5 4 3 2 14 10 8

2 5 4 3 7 14 10 8

Repetir el proceso con cada subproblema

3.6 Ordenación rápida de Hoare (quicksort).
algoritmo pivote (ENT i, j:1..n; ENT-SAL v:tabla[1..n]; SAL l:1..n)
{El algoritmo pivote permuta los elementos de la tabla v[i..j] y proporciona un valor l
tal que, al final, i ≤ l ≤ j, v[k] ≤ p para todo i ≤ k < l, v[l] = p, y v[k] > p para todo l < k ≤ j,
con p el valor inicial de v[i]}
variables p, k, l : 1..n
principio {pivote}
p  v[i]; k  i; l  j + 1
repetir k  k + 1 hasta que v[k] > p o k ≥ j
repetir l  l − 1 hasta que v[l] ≤ p
mientras k < l hacer
intercambiar v[k] y v[l]
repetir k  k + 1 hasta que v[k] > p o k ≥ j
repetir l  l − 1 hasta que v[l] ≤ p
fin mientras
intercambiar v[i] y v[l]
fin {pivote}
3.6 Ordenación rápida de Hoare (quicksort).
algoritmo quicksort (ENT i, j:1..n; ENT-SAL v:tabla[1..n])
{El algoritmo quicksort ordena no decrecientemente los elementos de la
tabla v que están entre las posiciones i y j}
variables l : 1..n
principio {quicksort}
si j > i entonces
pivote(i, j, v, l)
si i < l − 1 entonces quicksort(i, l-1, v) fin si
si l + 1 < j entonces quicksort(l+1, j, v) fin si
fin si
fin {quicksort}

 Es poco eficiente cuando los subcasos están fuertemente desequilibrados. (n2)

 En el caso medio: O(nlog n)
3.7 Otros problemas.
• Multiplicación de matrices.
Mejorar la complejidad del algoritmo que multiplica dos matrices utilizando el
esquema divide y vencerás.
• Trasposición de una matriz cuadrada.
Construir la traspuesta de una matriz cuadrada M de tamaño potencia de dos.
• Mediana de dos vectores.
Dados X e Y dos vectores ordenados de tamaño n, implementar un algoritmo
para calcular la mediana de los 2n elementos que contienen X e Y.
• Buscar el elemento en su posición.
Dado A un vector ordenado, diseñar un algoritmo de complejidad O(log n) en el caso
peor, capaz de encontrar un índice i tal que A[i] = i, si tal índice existe.