Divide y vencerás

Parte el problema en instancias más chicas del mismo problema, recursa, combina. El paradigma detrás de merge sort, quicksort y búsqueda binaria.

Los tres pasos + la recurrencia

• Divide en subproblemas de tamaño n/b
• Vence cada uno recursivamente
• Combina sus respuestas con f(n) trabajo
• Costo: T(n) = a·T(n/b) + f(n) → se lee con el Teorema Maestro

Karatsuba: 3 multiplicaciones, no 4

• Multiplicar números de n dígitos: parte cada uno en mitad alta/baja
• Ingenuo: 4 productos de media longitud → T(n)=4T(n/2) = O(n²)
• Truco: término de en medio = (hi+lo)(hi+lo) − hi·hi − lo·lo → solo 3 productos
• T(n)=3T(n/2)+O(n) = O(n^log₂3) = O(n^1.585)

Mira el árbol de recursión

Multiplicación de 8 dígitos: 1 → 3 → 9 → 27 subproblemas. Trabajo por nivel 8, 12, 18, 27. El trabajo CRECE hacia las hojas → dominan las hojas → n^1.585 (3 ramas, no 4).

Lo subcuadrático gana a escala

Pendiente log-log = exponente: escolar ~2, Karatsuba ~1.585. 512 dígitos → 2.3× más rápido (la brecha se ensancha).

Para llevar

El paso de COMBINAR fija el exponente, no cómo partes el problema. ¿Subproblemas traslapados? Divide y vencerás los vuelve a resolver → ese es trabajo de DP. Sigue: greedy — decisiones localmente óptimas que llegan a un óptimo global.