# Algoritmia/Divide y vencerás

El primer método algorítmico presentado en este libro es la técnica de divide y vencerás, también conocida como divide y conquista (del inglés divide and conquer). El método se basa en reducir un problema dado en dos o más subproblemas más pequeños y, sucesivamente, volver a aplicar el mismo método sobre los resultados obtenidos hasta alcanzar subproblemas de resolución trivial o casos base. De manera general, estos son los pasos a seguir a la hora de crear un algoritmo basado en el método divide y vencerás:
* Dado un problema, identificar los subproblemas del mismo tipo
* Resolver recursivamente cada subproblema
* Combinar las soluciones obtenidas en una única solución al problema inicial

## Ejemplo: Mergesort

El pseudocódigo de la ordenación por fusión (en C Sharp)

## Problemas resueltos
### Subvector de suma máxima

* Enunciado del problema: "Dado un vector de longitud n, se desea encontrar el subvector de longitud m y suma máxima, con m ≤ n".
* Solución: Un primer acercamiento podría consistir en dividir el vector por la mitad y considerar los subvectores izquierdo y derecho. Sin embargo, esta solución no sería correcta al no considerarse los subvectores que atraviesan la mitad del vector. Por tanto, habrá que considerar los tres casos: subvector izquierdo, subvector derecho y subvector central.
   * Subvector izquierdo: Lo primero que se ha de hacer es comparar la longitud del vector con la del subvector; si la longitud del primero es mayor, se disminuye su tamaño a la mitad y se vuelve a aplicar el método, esta vez para calcular el subvector izquierdo. Por tanto, el coste de la llamada recursiva es $T({\frac {n}{2}})$, siendo n la longitud del vector. En el momento en que la longitud del vector sea menor que la del subvector, se suman todas las posiciones consecutivas hasta llegar al final y se asignan los límites del subvector (inicio y fin). Es posible que dicho subvector tenga menos longitud que la deseada; por ello, cuando acaba la llamada para el subvector izquierdo, es necesario aumentar su longitud por la derecha hasta llegar a la longitud pedida. Según se aumenta la longitud, también habrá que ir actualizando la suma total del subvector.
   * Subvector derecho: Inmediatamente después de haber calculado el subvector izquierdo, se hará exactamente lo mismo con el subvector derecho, ya que las anteriores llamadas han ido dividendo el vector en dos. El coste para la llamada del subvector derecho también es $T({\frac {n}{2}})$. Igual que antes, cuando se haya terminado de calcular el subvector derecho, es posible que este no tenga la longitud pedida, por lo cual se aumenta su longitud (esta vez por la izquierda) hasta llegar a la longitud pedida. Al finalizar el proceso, se actualiza su suma.
   * Subvector central: Lo primero que se hará será dividir el vector por la mitad. Acto seguido, se comprueba hasta dónde se puede calcular con la longitud que se está pidiendo, teniendo en cuenta que el subvector tiene que pasar por el punto medio del vector. Para ello se tienen dos marcadores, inicio y final, que van a indicar hasta que posiciones del vector hay que moverse para calcular un subvector con la longitud que se pide y que pase por el centro del vector. Puede darse el caso de que tanto inicio como final indiquen posiciones inexistentes en el vector si la longitud pedida supera la longitud de la mitad del vector. Por esta razón, si cualquiera de los dos se saliera del rango, ya sea inicio por abajo o final por arriba, se inicializarán como los extremos que les correspondan del vector: inicio = 0, final = n-1 (esta última no será necesaria).
       Si final se sale del rango, solo se podrán calcular n-l+1 (siendo l la longitud del subvector pedido) subvectores de longitud l, o lo que es lo mismo, solo se podrán calcular subvectores con inicio entre 0 y n-l. La forma de calcular los vectores máximos es mediante iteración. Cuando se acaba con un subvector, se compara su suma con la suma máxima para ver si hay que actualizar el vector óptimo.
       En caso de que final no se salga del rango se hace lo mismo que en el caso anterior, pero sin riesgo de evaluar un subvector inexistente.
* Algoritmo:

### Organización de un campeonato

El problema de la organización del calendario de un campeonato con Divide y Vencerás.

### Multiplicación de enteros grandes

* Enunciado del problema: las operaciones aritméticas entre números enteros suelen considerarse operaciones elementales siempre y cuando los números que intervienen no superen los límites de representación. Cuando esto ocurre, hay que acudir a otro tipo de representación, por ejemplo los arrays, y utilizar los algoritmos clásicos de las operaciones aritméticas. El problema planteado consiste en saber si existe alguna forma de reducir el coste en el caso de la multiplicación, ya que el algoritmo clásico de multiplicación es de orden cuadrático. Como alternativa, se podría utilizar el esquema de multiplicación por duplicación, pero no ofrece mejoras en cuanto a tiempo de ejecución.
* Solución: considérense dos números enteros, u y v, de n dígitos cada uno.
    1. Algoritmo básico: la idea a seguir es descomponer los dos números en la suma de otros dos. Más concretamente, sea S la parte entera de n/2, la descomposición consiste en dividir los números entre 10$^S$:
       u → w representa el cociente y x el resto → u = 10$^S$·w + x
       v → y representa el cociente y z el resto → v = 10$^S$·y + z
    Luego:
       u·v = (10$^S$·w + x)·(10$^S$·y + z) = 10$^{2S}$·w·y + 10$^S$·(w·z + x·y) + x·z
    A continuación, se calculan las suboperaciones w·y, w·z, x·y y x·z. Si los operandos (w, x, y, z) son:
       - “pequeños”, entonces se multiplican de la forma clásica.
       - “suficientemente grandes”, se aplica de nuevo el algoritmo y se calculan recursivamente las multiplicaciones de los respectivos sumandos.
    2. Algoritmo mejorado: al realizar cuatro multiplicaciones de tamaño mitad en cada llamada, el coste resultante es T(n) = 4·T(n/2) + g(n), donde g(n) es el tiempo invertido en sumas, desplazamientos y operaciones adicionales sencillas, por lo que el algoritmo sigue siendo de orden cuadrático.
    Dado que se necesitan realizar cuatro multiplicaciones de tamaño mitad, no se mejora el tiempo de ejecución respecto a los algoritmos clásicos. Para intentar reducirlo, es preciso evitar alguna de esas multiplicaciones. La clave de la mejora consiste en advertir que no es necesario calcular w·z y x·y, si no la suma de ambos. Así, se considera r = (w + x)·(y + z) = w·y + (w·z + x·y) + x·z , con los que las multiplicaciones a realizar son:
       p = w·y
       q = x·z
       r = (w + x)·(y + z)
    , hallando la suma de la siguiente forma:
       (w·z + x·y) = r – p - q
    Así, volviendo al producto anterior:
       u·v = (10S·w + x)·(10S·y + z) = 102S·w·y + 10S·(w·z + x·y) + x·z = 102S·p + 10S·(r – p - q) + q
    , teniendo que calcular las multiplicaciones p, q y r. Si sus operandos (w, x, y, z) son:
       - “pequeños”, entonces se multiplican de la forma clásica.
       - “suficientemente grandes” se aplica de nuevo la descomposición anterior, y calculamos recursivamente las multiplicaciones de los respectivos sumandos.
* Algoritmo básico:
* Algoritmo mejorado:
Con lo cual, el coste final e: T(n) = 3·T(n/2) + g(n), perteneciente al orden Θ(n$^{1,59}$).
* Otras consideraciones:
   * Si u y v son de distinta longitud (m y n respectivamente, con m < n), entonces:
       - si no difieren en más de un factor de 2, se rellena el operando más pequeño con ceros no significativos e igualar las longitudes.
       - si uno de los operandos es mucho mayor que el otro, se segmenta el operando más largo, v, en bloques de tamaño m y se utiliza el algoritmo para multiplicar cada uno de los bloques de v por u. De esta forma, se multiplican operandos de igual tamaño m. Finalmente, el producto definitivo, se halla con adiciones y desplazamientos sencillos.
   * Los números de longitud impar se multiplican de la misma forma que los pares. Para ello, se dividen del modo más equitativo posible: un número de n cifras (n impar), se divide en uno más significativo |n/2| cifras y otro menos significativo de |n/2|+1 cifras.