Tema 4 - Divide Y Vencerás

📖

La idea detrás de los algoritmos de Divide y Vencerás (DyV) consiste es que, para resolver un problema muy grande, podemos dividirlo en problemas más pequeños, y por lo tanto, más faciles de resolver

Ejemplo de uso de un algoritmo DyV

📝

Supongamos que queremos multiplicar dos números de

n

cifras utilizando un algoritmo de DyV

Siendo los números
$x$ → 12345678
$y$ → 24680135

Dividiremos ambos números según la expresión $\boxed{x_i\times 10^4 + x_d}$
Siendo $x_i$ los 4 primeros dígitos, y $x_d$ los 4 últimos
$x_i = 1234$ , $x_d = 5678$
$y_i = 2468$ , $y_d= 0135$
Y ahora expresaremos la multicación de $x$ y de $y$ como
$x\times y \\= (x_i\times 10^4+x_d)·(y_i\times 10 ^4 + y_d) \\= (x_iy_i)·10^8 + (x_iy_i + x_dy_d)·10^4 + (x_dy_d)$
De esta manera, hemos dividido el problema de un multiplicación grande, en 3 problemas más pequeños (separados por las sumas). Podemos observar que las multiplicaciones $x_iy_i$ y la $x_dy_d$ están repetidas, por lo que podemos calcularlas solo una vez

Repetiremos este proceso con cada problema de forma recursiva, hasta que lleguemos a un punto donde el problema sea tan pequeño que por fin podemos intentar resolverlo. A este paso se le llama conquistar

En nuestro ejemplo, esto puede ser el punto en el que los valores que vamos a multiplicar sean solo de 3 o 4 cifras, por ejemplo

Una vez hallamos resuelto el problema más pequeño (hemos conquistado) entoces podemos volver de la recursibidad para combinar los resultados obtenidos con los resultado de el resto de problemas pequeños.

En nuestro ejemplo esto consiste en realizar las sumas

El resultado lo obtendremos una vez hallamos vuelto de todas las llamadas recursivas

El pseudocódigo para este problema sería
funcion 

⚠️

Divide Y Vencerás no es un algoritmo concreto, sino un filosofía en la que se basan distintos algoritmos para resolver un problema

🧩

Complejidad algorítmica de los algoritmos de DyV

La complejidad algorítmica dependerá de los sub-problemas generados, el divisor del problema y la complejidad del método de combinación. En función de los datos mencionados, la complejidad será una de las siguientes

T(n) = \begin{cases} O(n^k) && a<b^k\\ O(n^k\log_bn && a = b^k\\ O(n^{\log_ba}) && a> b^k \end{cases}

Parámetros de la fórmula
$a$ → Número de subproblemas generados
Cuantos subproblemas se han generado
En el ejemplo de la multiplicación de números grandos, dividiamos el problema en cuatro sum problemas, por lo que: $a = 4$
$b$ → Divisor del problema
Con respecto al problema inicial, en cuando se ha reducido el problema de tamaño
En el ejemplo, cada sub problema es de la mitad del número original, por lo que en este caso $b = 2$
$k$ → Complejidad del método de combinación (exponente de la $n$ : $O(n^k)$ )
La complejidad algorítmica de el método usado para combinar las soluciones de los subproblemas

💡

Cuando

k=1

el esquema DyV pasa a llamarse reducción o simplificación

🔢

Fases de un algoritmo de DyV

💡

Estos algoritmos suelen implementarse de forma recursiva

🪓 Dividir

Consiste en cojer el problema principal, y dividirlo varios problemas más pequeños. Se suele definir un algoritmo recursivo donde se divida el problema y se combinen las soluciones (en una función aparte)

⚔️ Conquistar

Cuando ya no podemos dividir más el problema, es el momento de intentar resolverlo. Se suele definir una función que determine cuando hemos llegado a un problema lo suficientemente pequeño y un algoritmo específico para resolver el problema

🪆 Combinar

Una ver resuelto el subproblema, combinaremos el resultado con los resultados del resto de subproblemas. Podemos definir una función que realize este paso, si la operación de combinación es suficientemente compleja. Dicha función será llamada desde la función recursiva al volver de todos los subproblemas

🧠

La decisión de cuando determinar si un problema es suficientemente pequeño depende de la naturaleza del problema. La idea general es realizar este paso cuando el algoritmo de DyV empieza a ser ineficiente por su complejidad para problemas tan pequeños

El punto óptimo para dejar de dividir el problema es cuando vale el punto de corte de las rectas representadas (cruze de complejidad entre DyV y otros algoritmos) — *El punto óptimo para dejar de dividir el problema es cuando* *$n$* *vale el punto de corte de las rectas representadas (cruze de complejidad entre DyV y otros algoritmos)*

🚧

Restricciones de los algoritmos de DyV

Para que un problema pueda ser resuelto con un algoritmo de DyV, este deberá cumplir con los siguientes criterios

Debe ser posible descomponer el problema en subproblemas más pequeños

Se debe poder combinar los subproblemas de forma eficiente

Los subproblemas deben ser aproximadamente del mismo tamaño

⚠️

Algunos algoritmos de DyV pueden necesitar que el de un primer subproblema que esté resuelto antes de empezar el segundo subejemplar

Algoritmos

🪓

Algoritmo de busqueda binaria

El clásico algoritmo de búsqueda binaria donde, dado un array ordenado, nos piden encontrar un valor concreto

Complejidad algoritmica

Este algoritmo se puede plantear como un problema de DyV.
$a = 1$ → Generamos un único subproblema cada vez que dividimos
$b=2$ → El subproblema generado es la mitad de grande
$k=0$ → No hay paso de combinación
$a= b^k \rightarrow 1 = 2^0$
La complejidad algoritmica es $O(n^0 \log_2n)$

🔀

Mergesort

Este algoritmo consiste en dividir el array hasta que es suficientemente pequeño para ser ordenado de manera eficiente, una vez conquistado, se combinan los arrays de los subproblemas recorriendo todos ellos a la vez para construir un array ordenado y reemplazar dicho array por el problema principal

Complejidad algoritmica

El problema se divide en dos subproblemas de la mitad de tamaño
$a = 2$ → Generamos dos subproblemas
$b=2$ → Los subproblemas generados son la mitad de grandes
$k=1$ → El paso de combinar tiene complejidad $n^1$
La complejidad algoritmica es $O(n \log_2n)$

🏎️

Quicksort

Este algoritmo consiste en extraer el privote, un valor del array (el que queramos, típicamente el primero) y luego recorremos el array colocando en dos listas el resto de elementos del array, según si son menores o iguales o mayores que el número escogido como pivote. De esta manera tendremos dos listas, una con número menores que el pivote, y otro con número mayores. Ahora repetimos el algoritmo recursivamente para cada una de las sub-listas generadas hasta llegar a una lista vacía. Cuando se llega al caso base, solo tenemos que colocar los elementos de las listas de la izquierda antes que el pivote y los elemento de la nueva lista después, a la hora de añadirlos a las lista ordenada

Complejidad algoritmica

El problema se divide en dos subproblemas de la mitad de tamaño
$a = 2$ → Generamos dos subproblemas
$b=2$ → Los subproblemas generados son la mitad de grandes
$k=1$ → El paso de combinar tiene complejidad $n^1$
La complejidad algoritmica es $O(n \log_2n)$