# TDA | Divide & Conquer # Dividir y Conquistar El método de Dividir y Conquistar (D&C) es una técnica fundamental en el diseño de algoritmos, que consiste en los siguientes pasos generales: 1. **Dividir** el problema en subproblemas más pequeños del mismo tipo. 2. **Conquistar** resolviendo estos subproblemas de manera recursiva. Si son suficientemente pequeños, se resuelven directamente. 3. **Combinar** las soluciones de los subproblemas para formar la solución al problema original. ## Forma general de D&C La forma general de un algoritmo D&C para un problema $X$ puede describirse como sigue: - Si $X$ es lo suficientemente pequeño, se resuelve directamente. - De lo contrario: - Dividir $X$ en subproblemas $X_1, X_2, \ldots, X_k$. - Para cada $i \leq k$, hacer $Y_i = F(X_i)$. - Combinar las soluciones $Y_i$ en una solución $Y$ para $X$. - Devolver $Y$. ## Análisis de la complejidad Para analizar la complejidad de un algoritmo D&C, utilizamos la recurrencia: $$T(n) = aT\left(\frac{n}{c}\right) + b'n^d$$ donde: - $a$ es el número de subproblemas en cada división. - $n/c$ es el tamaño máximo de cada subproblema, con $n/c > n_0$. - $b'$ es una constante que representa el costo de dividir y combinar los resultados de los subproblemas. - $d$ es una constante que indica el costo de la división y la combinación. La solución a esta recurrencia varía según los valores de $a$, $c$ y $d$, pero en general se puede expresar usando la notación $O$ para describir la complejidad del algoritmo en términos de $n$. ## Casos específicos - **Cuando $a = 1$ y $d = 0$:** El costo de combinar es constante y la complejidad es $O(\log_c n)$. - **Cuando $d = 1$:** - Si $a < c$, la complejidad es $O(n)$. - Si $a = c$, la complejidad es $O(n \log_c n)$. - Si $a > c$, utilizando la fórmula de la suma de una serie geométrica, la complejidad es $O(n^{\log_c a})$. Estos análisis nos permiten comprender cómo la eficiencia de un algoritmo D&C está influenciada por cómo se dividen los problemas, el número de subproblemas generados, y el costo de combinar sus soluciones. ### Ejemplo Práctico Un ejemplo clásico de D&C es el algoritmo de ordenamiento Merge Sort. Este algoritmo divide el arreglo a ordenar en dos mitades, ordena cada mitad recursivamente y luego combina las dos mitades ordenadas. El proceso de división es simple y el de combinación (merge) tiene un costo lineal respecto al tamaño del problema, $n$. ### Complejidad de Merge Sort Aplicando el análisis anterior, podemos ver que Merge Sort tiene una recurrencia de la forma: $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$$ donde el término $\Theta(n)$ representa el costo de combinar las dos mitades. Siguiendo el análisis de D&C: - Aquí, $a=2$, $c=2$ (ya que dividimos el problema en 2 partes iguales), y $d=1$ (porque el costo de combinar es lineal). - Aplicando nuestro análisis, vemos que cae en el caso en que $a = c$, lo cual da una complejidad de $O(n \log n)$. ### Conclusiones Los algoritmos de Dividir y Conquistar son una poderosa herramienta en el diseño de algoritmos, permitiendo soluciones eficientes a problemas que de otro modo serían intratables. La clave de su eficacia yace en cómo se divide el problema original y cómo se manejan los subproblemas para minimizar el trabajo redundante y maximizar la reutilización de las soluciones a subproblemas. A través de la correcta aplicación de este enfoque, se pueden alcanzar soluciones óptimas que son tanto elegantes como eficientes. # Algoritmo de Karatsuba El algoritmo de Karatsuba es una técnica eficiente para la multiplicación de números grandes, que se basa en el principio de Dividir y Conquistar. Fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y representa una mejora significativa sobre la multiplicación tradicional de columnas que se enseña en la escuela. ## Descripción Dado dos números grandes $x$ e $y$, que se pueden escribir como $x = 10^{n/2}a + b$ e $y = 10^{n/2}c + d$, donde $a$ y $c$ son la primera mitad de los dígitos de $x$ e $y$ respectivamente, y $b$ y $d$ son la segunda mitad. El algoritmo de Karatsuba permite calcular el producto $x \cdot y$ mediante la realización de solo tres multiplicaciones de números más pequeños, en lugar de cuatro. El producto se calcula como: $$x \cdot y = 10^n ac + 10^{n/2}(ad + bc) + bd$$ Pero en lugar de calcular $ad$ y $bc$ por separado, Karatsuba observó que se pueden obtener a partir de: $$ad + bc = (a + b)(c + d) - ac - bd$$ Así, las tres multiplicaciones que necesitamos son: 1. $ac$ 2. $bd$ 3. $(a + b) \cdot (c + d)$ ## Complejidad El algoritmo reduce la complejidad de la multiplicación de dos números de $n$ dígitos de $O(n^2)$, que es lo que se obtiene con el método tradicional, a aproximadamente $O(n^{1.585})$, utilizando el análisis de complejidad de Dividir y Conquistar. ## Conclusión El algoritmo de Karatsuba es un claro ejemplo de cómo la técnica de Dividir y Conquistar puede ser utilizada para desarrollar algoritmos más eficientes para problemas computacionales clásicos. Aunque para números pequeños el método tradicional puede ser más rápido debido a su simplicidad, para números grandes Karatsuba ofrece una mejora significativa en la eficiencia. # Teorema Maestro y Análisis Asintótico El Teorema Maestro proporciona una solución directa para las recurrencias que surgen al analizar algoritmos de Dividir y Conquistar, ofreciendo una manera de determinar la complejidad temporal de estos algoritmos de forma asintótica. ## Teorema Maestro El Teorema Maestro se aplica a recurrencias de la forma: $$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$ donde, - $n$ es el tamaño del problema, - $a \geq 1$ es el número de subproblemas en la recurrencia, - $b > 1$ es el factor por el que se divide el tamaño del problema, - $f(n)$ es una función que representa el costo de dividir el problema y combinar los resultados de los subproblemas. El teorema establece tres casos para determinar la complejidad temporal de $T(n)$: 1. **Si $f(n) = O(n^{\log_b a - \epsilon})$ para algún $\epsilon > 0$, entonces $T(n) = \Theta(n^{\log_b a})$.** 2. **Si $f(n) = \Theta(n^{\log_b a})$, entonces $T(n) = \Theta(n^{\log_b a} \log n)$.** 3. **Si $f(n) = \Omega(n^{\log_b a + \epsilon})$ para algún $\epsilon > 0$, y si $a f\left(\frac{n}{b}\right) \leq k f(n)$ para alguna constante $k < 1$ y suficientemente grande $n$, entonces $T(n) = \Theta(f(n))$.** # Análisis Asintótico y Otras Formas de Calcularlo ## Análisis General El análisis asintótico se centra en entender el comportamiento de los algoritmos cuando el tamaño del problema crece indefinidamente. A diferencia del Teorema Maestro, que proporciona una solución directa para recurrencias específicas, existen otros enfoques para calcular la complejidad de los algoritmos de Dividir y Conquistar. ## Análisis por Caso Una técnica importante es el análisis por caso, donde se evalúa la complejidad bajo diferentes supuestos sobre los parámetros del algoritmo, como el número de subproblemas (`a`), el tamaño relativo de cada subproblema (`c`), y el costo de dividir el problema y combinar sus soluciones (`d`). Este enfoque permite entender cómo estas variables influyen en la complejidad final del algoritmo. ### Ejemplos de Análisis por Caso 1. **Cuando `a = 1` y `d = 0`**, es decir, hay un solo subproblema y combinar tiene un costo constante, la complejidad es `O(logc n)`. 2. **Cuando `d = 1`**, lo que implica que la división y la unión tienen un costo lineal, y dependiendo de la relación entre `a` y `c`, la complejidad puede variar significativamente: - **Si `a < c`** ("pocos subproblemas"), la serie converge y la complejidad es `O(n)`. - **Si `a = c`**, la complejidad es `O(n logc n)`. - **Si `a > c`** ("muchos subproblemas"), se utiliza una fórmula específica para calcular la complejidad, que puede resultar en complejidades mayores. ## Conclusión Además del Teorema Maestro, el análisis asintótico de algoritmos de Dividir y Conquistar puede realizarse mediante el análisis detallado de casos específicos, considerando la cantidad de subproblemas generados, el costo de las operaciones de división y combinación, y cómo estos factores contribuyen a la complejidad total. Este enfoque proporciona una comprensión más matizada de la eficiencia del algoritmo bajo diferentes condiciones.