16-05-2022

<aside> 💡 La metodología consiste en

• dividir un problema en problemas similares pero más chicos
• resolver los problemas menores
• combinar las soluciones a los problemas menores para obtener la solución del problema original </aside>

Método general algorítmico

Algoritmo $\text{DC}(X)$

• Si $X$ es suficientemente chico/simple
  • $\text{ADHOC}(X)$
• En caso contrario
  • Descomponer $X$ en sub-instancias $X_1, X_2, ..., X_k$
  • Para $i$ desde $1$ hasta $k$
    • $Y_i \leftarrow DC(X_i)$
  • Combinar las soluciones $Y_i$ para construir la solución $Y$ para $X$

Ejemplos

• Merge Sort: Ordenamiento de un arreglo
• Algoritmo de Karatsuba: Multiplicar dos números enteros
• Algoritmo de Strassen: Multiplicar dos matrices de $n \times n$

Recurrencias típicas de D&C

Esquema D&C:

Dividir las instancias de tamaño mayor que cierto $n_0$ en subinstancias, resolverlas y luego combinar las soluciones para el problema inicial.

Situación típica:

Dividir en $a$ subproblemas, de tamaño máximo $\frac nc$. El costo de determinar subproblemas y unirlos es $b\cdot n^d$. Suponemos la base ($n = 1$) cuesta $b$.

Solución de la recurrencia típica

Costo (suponiendo $n = c^k$)

$$ \begin{aligned} T(n) &= a \cdot T(\frac nc) + b\cdot n^d \\ &= a\cdot T(c^{k-1}) + b\cdot n^d \\ &= a \cdot \big(a \cdot T(c^{k-2}) + b\cdot c^{d\cdot(k-1)}\big) + b\cdot c ^{k\cdot d} \\ &= a^2 \cdot T(c^{(k-2)}) + a\cdot b \cdot c^{d\cdot (k-1)} + b\cdot c ^{k\cdot d} \\ &\vdots \\ &= a^j \cdot T(c^{k-j}) + \sum_{i=0}^{j-1} a^i\cdot b \cdot c^{d \cdot (k-i)} \end{aligned} $$