Divide y vencerás

Qué cubre este capítulo

Merge sort, quicksort y búsqueda binaria eran la misma idea con distinto disfraz: partir un problema en versiones más pequeñas de sí mismo, resolverlas y combinar. Esa idea se llama divide y vencerás, y este capítulo le pone nombre, estudia qué la hace rápida y te da la herramienta para analizarla: el árbol de recursión y el Teorema Maestro. El vehículo es un problema donde el método obvio es cuadrático y una división inteligente lo vuelve subcuadrático: multiplicar números grandes. La multiplicación de primaria es O(n²); el algoritmo de Karatsuba de 1960 parte cada número a la mitad y —mediante un truco algebraico que convierte cuatro multiplicaciones de media longitud en tres— logra O(n^1.585). Ese único cambio, de cuatro subproblemas a tres, es una lección perfecta del paradigma: el paso de combinar, no el de dividir, es el que decide la complejidad de un divide y vencerás. Este capítulo construye Karatsuba, lo enfrenta contra la multiplicación escolar y anima el árbol de recursión que explica exactamente por qué tres le gana a cuatro.

Un poco de historia

Divide y vencerás es viejo —la búsqueda binaria aparece en el registro histórico siglos antes de las computadoras, y John von Neumann describió merge sort en 1945— pero la historia que mejor captura el poder del paradigma es la de Karatsuba. En 1960, Anatoly Karatsuba, de 23 años, asistió a un seminario donde Andrey Kolmogorov, uno de los grandes matemáticos del siglo, conjeturó que multiplicar dos números de n dígitos requería Ω(n²) operaciones, es decir, que la multiplicación de primaria era esencialmente óptima. En menos de una semana Karatsuba lo refutó, al encontrar el truco de las tres multiplicaciones que rompe la barrera cuadrática. Kolmogorov quedó tan impresionado que él mismo escribió el resultado (acreditando a Karatsuba, al inicio, casi como nota al pie). Fue la primera señal de que la multiplicación rápida era posible, y abrió una línea de investigación que llevó a los métodos basados en FFT (Schönhage-Strassen, y en 2019 un algoritmo O(n log n)) que hoy se usan para multiplicar los enormes números de la criptografía. La lección quedó grabada para siempre: los algoritmos cuadráticos "obvios" muchas veces no son óptimos, y una división inteligente puede ganarles.

La intuición

Divide y vencerás tiene tres pasos. Dividir el problema en subproblemas que sean instancias más pequeñas del mismo problema. Vencerlos por recursión (hasta que sean lo bastante chicos para resolverlos directo). Combinar las respuestas de los subproblemas en la respuesta del todo. Merge sort divide un array a la mitad, ordena recursivamente cada mitad y combina mezclando. La búsqueda binaria divide el intervalo de búsqueda a la mitad y recursa en un solo lado (el combinar es trivial). El poder del paradigma está en que un problema de tamaño n se reduce a unos cuantos problemas de tamaño n/2, y repetir eso colapsa n hacia 1 en apenas log n niveles.

Karatsuba muestra cuánto importa el paso de combinar. Para multiplicar dos números de n dígitos, parte cada uno en su mitad alta y su mitad baja: x = x_hi·B + x_lo y y = y_hi·B + y_lo, donde B es 10 elevado a la media longitud. El producto se expande a x_hi·y_hi·B² + (x_hi·y_lo + x_lo·y_hi)·B + x_lo·y_lo, que ingenuamente necesita cuatro multiplicaciones de media longitud (x_hi·y_hi, x_hi·y_lo, x_lo·y_hi, x_lo·y_lo). Cuatro subproblemas de la mitad de tamaño dan la recurrencia T(n) = 4T(n/2) + O(n), que sale en O(n²): ninguna mejora. La idea clave de Karatsuba es que el término de en medio no necesita dos de esos productos: x_hi·y_lo + x_lo·y_hi es igual a (x_hi + x_lo)(y_hi + y_lo) − x_hi·y_hi − x_lo·y_lo, y los dos productos que se restan son los que ya estás calculando. Así que bastan tres multiplicaciones de media longitud —x_hi·y_hi, x_lo·y_lo y el producto de las sumas— lo que da T(n) = 3T(n/2) + O(n) = O(n^log₂3) = O(n^1.585). La división es idéntica; solo cambió el combinar, y eso cambió la complejidad.

Complejidad: cómo escala

La recurrencia T(n) = a·T(n/b) + f(n) se lee con el Teorema Maestro, que compara el trabajo en las hojas del árbol de recursión, n^(log_b a), contra el trabajo f(n) que se hace al dividir y combinar. Para merge sort, a=2, b=2, f(n)=n: el trabajo en hojas es n^(log₂2) = n, igual a f(n), lo que da O(n log n). Para Karatsuba, a=3, b=2, f(n)=O(n): el trabajo en hojas es n^(log₂3) = n^1.585, que domina a f(n), y da O(n^1.585). Para la búsqueda binaria, a=1, b=2, f(n)=O(1): O(log n). El costo del paradigma está por completo en esa comparación de tres vías. El enfrentamiento lo muestra empíricamente: Karatsuba contra el método escolar conforme crecen los números:

En una gráfica log-log, una ley de potencias es una línea recta cuya pendiente es el exponente, y la línea del método escolar es más empinada (pendiente ≈ 2) que la de Karatsuba (pendiente ≈ 1.585): los algoritmos divergen conforme crecen los números. En 512 dígitos Karatsuba fue como 2.3 veces más rápido, y la brecha se ensancha con el tamaño, justo como lo predicen los exponentes. Fíjate, eso sí, que en tamaños chicos los dos van parejos y el método escolar hasta puede ganar: la recursión de Karatsuba trae overhead (las sumas, las llamadas recursivas) que solo se paga cuando n es lo bastante grande para que el mejor exponente domine. Por eso las implementaciones reales, incluida la multiplicación de enteros de CPython, usan el método escolar para números chicos y cambian a Karatsuba pasado cierto umbral: un patrón recurrente en divide y vencerás, volver al método ingenuo en el caso base, donde de hecho es más rápido.

En qué es buena y en qué no

Divide y vencerás es el enfoque correcto cuando un problema se descompone en subproblemas independientes del mismo tipo cuyas respuestas se combinan de forma limpia: ordenamiento, búsqueda, aritmética rápida (multiplicación con Karatsuba y FFT y su uso en procesamiento de señales), geometría computacional (par de puntos más cercano, envolvente convexa), multiplicación de matrices (el algoritmo de Strassen, otro truco de "menos subproblemas", 7 en vez de 8) y muchos más. También es la fuente natural de algoritmos paralelos: los subproblemas independientes corren en cores separados, y el árbol de recursión es un mapa del paralelismo. Y muchas veces convierte un método obvio cuadrático o exponencial en algo mucho más rápido, como hizo Karatsuba.

Donde es la herramienta equivocada es en problemas cuyos subproblemas se traslapan, o sea, donde la misma subinstancia se repite muchas veces, porque divide y vencerás a secas las vuelve a resolver de forma redundante, a veces exponencialmente (el Fibonacci recursivo ingenuo es el clásico cuento de advertencia). Esa es exactamente la situación que la programación dinámica (dos capítulos adelante) arregla al recordar las respuestas de los subproblemas. Divide y vencerás también carga con overhead de recursión que puede hacerlo más lento que un simple loop en entradas chicas —de ahí el corte en el caso base— y necesita un paso de combinar más barato que resolver desde cero, o no hay ganancia. Cuando los subproblemas son independientes y el combinar es barato, brilla; cuando se traslapan o el combinar es caro, busca en otro lado.

Los datos, o las entradas

El enfrentamiento multiplica pares de números aleatorios de tamaño creciente, cronometrando Karatsuba contra un multiplicador escolar O(n²) (ambos en Python, así que la comparación es entre los algoritmos, no entre lenguajes). La corrección se verifica con miles de pares aleatorios contra la multiplicación integrada de Python —la referencia confiable— más algunos casos de 400 dígitos para Karatsuba. La animación dibuja el árbol de recursión de Karatsuba para una multiplicación de 8 dígitos, revelándolo nivel por nivel y anotando el trabajo de cada uno: un problema de tamaño 8, luego 3 de tamaño 4, luego 9 de tamaño 2, luego 27 hojas de un dígito — con el trabajo por nivel creciendo 8, 12, 18, 27, así que dominan las hojas.

Constrúyelo, una función a la vez

Karatsuba, el divide y vencerás de las tres multiplicaciones:

def karatsuba(x, y):
    """Multiply two non-negative integers with three half-size multiplications instead of four.
    Split x = hi_x·B + lo_x and y = hi_y·B + lo_y at the midpoint B = 10^m. The product is
    hi_x·hi_y·B^2 + (hi_x·lo_y + lo_x·hi_y)·B + lo_x·lo_y. Karatsuba computes the middle term as
    (hi_x+lo_x)(hi_y+lo_y) − hi_x·hi_y − lo_x·lo_y, so only THREE products are recursed on:
    z2=hi·hi, z0=lo·lo, and z1=(sum)(sum). T(n)=3T(n/2)+O(n) = O(n^1.585)."""
    if x < 10 or y < 10:                         # base case: single-digit multiply is direct
        return x * y
    m = max(len(str(x)), len(str(y))) // 2       # split near the middle
    B = 10 ** m
    hi_x, lo_x = divmod(x, B)
    hi_y, lo_y = divmod(y, B)
    z2 = karatsuba(hi_x, hi_y)                    # high·high
    z0 = karatsuba(lo_x, lo_y)                    # low·low
    z1 = karatsuba(hi_x + lo_x, hi_y + lo_y) - z2 - z0   # the cross terms, from ONE more product
    return z2 * B * B + z1 * B + z0

Y el desglose del árbol de recursión que lee el Teorema Maestro:

def karatsuba_subproblems(n_digits, threshold=1):
    """How many single-multiplication leaves Karatsuba's recursion tree has for an n-digit input
    (each level triples the subproblem count while halving the size). Returns the per-level
    (count, size) breakdown — the shape the Master Theorem analyzes: work per level is
    count·size = n·(3/2)^level, a geometric series dominated by the leaves → O(n^log2(3))."""
    levels = []
    count, size = 1, n_digits
    while size > threshold:
        levels.append({"level": len(levels), "subproblems": count, "size": size,
                       "work": count * size})
        count *= 3
        size = (size + 1) // 2
    levels.append({"level": len(levels), "subproblems": count, "size": size, "work": count * size})
    return levels

Míralo funcionar

Aquí está el árbol de recursión de Karatsuba para multiplicar dos números de 8 dígitos, revelado un nivel a la vez. La raíz (arriba) es el único problema de tamaño 8. Se ramifica en tres subproblemas de tamaño 4 —tres, no cuatro, que es todo el truco—, cada uno de los cuales se ramifica en tres problemas de tamaño 2, y esos en tres hojas de un dígito. Observa la anotación conforme cada nivel se enciende: el nivel 0 hace 8 unidades de trabajo, el nivel 1 hace 12, el nivel 2 hace 18, el nivel 3 hace 27. El trabajo crece a la mitad otra vez en cada nivel hacia abajo, así que el fondo —las 27 hojas de un dígito— domina el total. Ese es el caso de "dominan las hojas" del Teorema Maestro hecho visual, y 27 ≈ 8^1.585 es exactamente el n^log₂3 que le da a Karatsuba su complejidad subcuadrática. Si cada nodo se hubiera ramificado en cuatro en vez de tres, las hojas serían 64 = 8², y estarías de vuelta en el método escolar:

El código completo

La pestaña de implementación desde cero es Karatsuba con su desglose de recurrencia; la pestaña de librería es el multiplicador escolar O(n²) contra el que se enfrentó, con una nota de que la propia multiplicación de int de Python cambia a Karatsuba pasados unos ~70 dígitos. Cambia entre ellas.

"""Divide and conquer — the paradigm that generated half the algorithms in this book. Break
a problem into smaller instances of the same problem, solve those recursively, and combine
their answers. Merge sort, quicksort, and binary search were all divide-and-conquer; this
chapter names the pattern and studies what makes it pay off, through a problem where the naive
method is quadratic and a clever DIVIDE makes it subquadratic: multiplying large numbers.

Multiplying two n-digit numbers the way you learned in school is O(n^2) — every digit of one
times every digit of the other. In 1960 Anatoly Karatsuba found something better. Split each
number into high and low halves; the product then needs four half-size multiplications
(high·high, high·low, low·high, low·low). That's still O(n^2) — four subproblems of half size
is no win. Karatsuba's trick is algebraic: those four products can be recovered from just
THREE half-size multiplications, because the cross terms high·low + low·high can be computed
from one extra product minus the two you already have. Three instead of four changes the
recurrence from T(n)=4T(n/2) (=n^2) to T(n)=3T(n/2), which is O(n^1.585) — subquadratic, and a
textbook lesson in how the COMBINE step decides a divide-and-conquer's complexity.
"""


# region: karatsuba
def karatsuba(x, y):
    """Multiply two non-negative integers with three half-size multiplications instead of four.
    Split x = hi_x·B + lo_x and y = hi_y·B + lo_y at the midpoint B = 10^m. The product is
    hi_x·hi_y·B^2 + (hi_x·lo_y + lo_x·hi_y)·B + lo_x·lo_y. Karatsuba computes the middle term as
    (hi_x+lo_x)(hi_y+lo_y) − hi_x·hi_y − lo_x·lo_y, so only THREE products are recursed on:
    z2=hi·hi, z0=lo·lo, and z1=(sum)(sum). T(n)=3T(n/2)+O(n) = O(n^1.585)."""
    if x < 10 or y < 10:                         # base case: single-digit multiply is direct
        return x * y
    m = max(len(str(x)), len(str(y))) // 2       # split near the middle
    B = 10 ** m
    hi_x, lo_x = divmod(x, B)
    hi_y, lo_y = divmod(y, B)
    z2 = karatsuba(hi_x, hi_y)                    # high·high
    z0 = karatsuba(lo_x, lo_y)                    # low·low
    z1 = karatsuba(hi_x + lo_x, hi_y + lo_y) - z2 - z0   # the cross terms, from ONE more product
    return z2 * B * B + z1 * B + z0
# endregion


# region: recurrence
def karatsuba_subproblems(n_digits, threshold=1):
    """How many single-multiplication leaves Karatsuba's recursion tree has for an n-digit input
    (each level triples the subproblem count while halving the size). Returns the per-level
    (count, size) breakdown — the shape the Master Theorem analyzes: work per level is
    count·size = n·(3/2)^level, a geometric series dominated by the leaves → O(n^log2(3))."""
    levels = []
    count, size = 1, n_digits
    while size > threshold:
        levels.append({"level": len(levels), "subproblems": count, "size": size,
                       "work": count * size})
        count *= 3
        size = (size + 1) // 2
    levels.append({"level": len(levels), "subproblems": count, "size": size, "work": count * size})
    return levels
# endregion

"""The library counterpart and the contrast. Python's built-in `int` multiplication IS a
divide-and-conquer algorithm: CPython switches from schoolbook to Karatsuba automatically once
the operands exceed ~70 digits, so `x * y` on big integers is already subquadratic. That built-in
is the correctness reference (`karatsuba(x, y)` must equal `x * y`).

The contrast that makes Karatsuba's point is SCHOOLBOOK multiplication — the O(n^2) grade-school
algorithm, four half-products' worth of digit-by-digit work. `schoolbook` below implements it on
digit lists so the trace generator can time quadratic against subquadratic as the numbers grow.
"""


# region: schoolbook
def schoolbook(x, y):
    """Grade-school multiplication: every digit of x times every digit of y, summed with carries.
    O(n^2) digit multiplications. The quadratic baseline Karatsuba's three-way split beats."""
    dx = [int(c) for c in str(x)][::-1]           # least-significant digit first
    dy = [int(c) for c in str(y)][::-1]
    acc = [0] * (len(dx) + len(dy))
    for i, a in enumerate(dx):
        for j, b in enumerate(dy):
            acc[i + j] += a * b                    # the O(n^2) core: every pair of digits
    # resolve carries
    carry = 0
    for i in range(len(acc)):
        acc[i] += carry
        acc[i], carry = acc[i] % 10, acc[i] // 10
    return int("".join(str(d) for d in acc[::-1]).lstrip("0") or "0")
# endregion

Desde cero vs librería

Karatsuba contra el método escolar es la tesis del paradigma en miniatura: mismo problema, misma forma de dividir, pero un combinar más inteligente baja la complejidad de n² a n^1.585 — y es el árbol de recursión, no la intuición, lo que te lo dice. Ese es el entregable de este capítulo: una forma de pensar más que un solo algoritmo. Todo divide y vencerás que hayas visto o que veas —merge sort, quicksort, búsqueda binaria, la multiplicación de matrices de Strassen, la FFT, el par más cercano— se analiza escribiendo su recurrencia y leyendo el Teorema Maestro, y se diseña preguntando "¿puedo reducir el número de subproblemas, o hacer el combinar más barato?". Es revelador que la propia multiplicación de enteros de Python sea exactamente esto: método escolar por debajo de un umbral, Karatsuba por arriba, el clásico corte en el caso base. Construir Karatsuba tú mismo es lo que convierte la recurrencia abstracta T(n) = 3T(n/2) + O(n) en un árbol que ya viste llenarse, y la idea de "tres le gana a cuatro" en algo que ya mediste.

Dónde te lo vas a encontrar

Divide y vencerás está por todas partes en los cimientos de la computación. Ordenar (merge sort, quicksort) y buscar (búsqueda binaria) son sus instancias más ejecutadas. La aritmética de números grandes en criptografía y álgebra computacional usa Karatsuba y sus sucesores basados en FFT (Python, el BigInteger de Java y GMP cambian a Karatsuba para operandos grandes). El procesamiento de señales e imágenes corre sobre la FFT, el divide y vencerás más famoso de todos. Los cálculos con matrices usan el algoritmo de Strassen y sus descendientes. La geometría computacional resuelve el par más cercano y la envolvente convexa dividiendo el espacio. Los sistemas paralelos y distribuidos lo usan como plantilla para repartir trabajo entre cores y máquinas (MapReduce es divide y vencerás a escala de datacenter). Y es el modelo mental de la recursión misma: cada vez que la respuesta de un problema se construye a partir de las respuestas a versiones más chicas de él, estás pensando en divide y vencerás.

Puntos clave

Divide y vencerás resuelve un problema partiéndolo en instancias más pequeñas de sí mismo, recursando y combinando, con su costo capturado por la recurrencia T(n) = a·T(n/b) + f(n) y leído con los tres casos del Teorema Maestro (dominan las hojas, balanceado, domina la raíz). La multiplicación de Karatsuba vuelve concreta la lección central del paradigma: dividir cada número a la mitad pero combinar con tres multiplicaciones de media longitud en vez de cuatro baja la complejidad de O(n²) a O(n^1.585) — el combinar, no la división, fija el exponente. El árbol de recursión, con el trabajo creciendo hacia las hojas, es la razón.

Los siguientes capítulos cubren los otros grandes paradigmas de diseño de algoritmos. Los algoritmos greedy (el que sigue) construyen una solución tomando la mejor decisión local en cada paso y —cuando el problema tiene la estructura adecuada— llegan a un óptimo global, como ya lo hicieron la codificación de Huffman, Dijkstra y los algoritmos de MST. Después, la programación dinámica ataca el caso de subproblemas traslapados que divide y vencerás no puede, recordando respuestas en vez de recalcularlas.