Cómo medimos el costo: Big-O y complejidad

Qué cubre este capítulo

Todos los demás capítulos de este libro comparan cosas: esta estructura contra aquella, la versión hecha a mano contra la de la librería. Para compararlas con honestidad necesitas una forma de decir qué tan caro es un algoritmo que no dependa de tu laptop, de tu lenguaje, ni del humor del sistema operativo esa tarde. Esa forma es Big-O. Mide cómo crece el trabajo conforme crece la entrada, y es la idea más útil de todo este campo. Entiéndela, y el resto del libro es una serie de aplicaciones. Por eso empezamos aquí, antes de cualquier estructura de datos, construyendo la vara con la que se mide todo lo demás.

Un poco de historia

La notación es más vieja que las computadoras. Paul Bachmann introdujo el símbolo big-O en 1894 en un libro de teoría de números, y Edmund Landau lo difundió por el análisis unos años después — por eso los matemáticos todavía la llaman notación de Landau. Durante décadas vivió en demostraciones sobre qué tan rápido se encogen los términos de error, nada que ver con programas.

Donald Knuth la arrastró a las ciencias de la computación. En una nota de 1976 titulada "Big Omicron and Big Omega and Big Theta" argumentó que esa misma notación era exactamente lo que los programadores necesitaban para hablar de tiempo de ejecución sin ahogarse en detalles de hardware, y estandarizó las O, Ω y Θ que usamos hoy. Para cuando el primer volumen de su Art of Computer Programming ya se leía por todos lados, "¿cuál es el Big-O de eso?" se había vuelto la manera normal de preguntar si un algoritmo sobreviviría el contacto con datos reales.

La intuición

Olvídate de los segundos por un momento. Cuenta operaciones, y cuéntalas como función del tamaño de la entrada, al que siempre llamamos n.

Si una función hace la misma cantidad fija de trabajo sin importar qué tan grande sea la entrada, es constante — tomar el primer elemento de una lista cuesta un paso, tenga la lista diez elementos o diez millones. Si hace una pasada sobre la entrada, el trabajo sigue a n: duplica la entrada, duplica el trabajo. Si puede tirar la mitad de la entrada restante en cada paso, el trabajo es el número de veces que puedes partir n a la mitad antes de que no quede nada, que es diminuto — eso es el logaritmo. Y si compara cada elemento contra cada otro elemento, el trabajo es n por n, y eso se pone feo rápido.

Big-O se queda solo con el término que domina cuando n crece y descarta las constantes. Un loop que corre 3n más 7 veces es O(n): una vez que n es grande, el 3 y el 7 no cambian la forma de la curva. Suena a tirar información, y lo es — a propósito. La constante es lo que te compra un lenguaje más rápido o un mejor CPU. La forma es lo que cuesta el algoritmo en sí, y la forma es lo que decide si tu programa termina.

Complejidad: cómo escala

Estas son las clases que vas a encontrar una y otra vez, de la más barata a la más peligrosa:

El tiempo constante, $O(1)$, es el techo — nada le gana a hacer una cantidad fija de trabajo. El tiempo logarítmico, $O(\log n)$, es casi igual de bueno: con n en mil millones, $\log_2 n$ es apenas alrededor de treinta. El tiempo lineal, $O(n)$, es el costo honesto de mirar todos tus datos una vez. Luego viene $O(n \log n)$, el precio de un buen sort, todavía muy vivible. Después de eso la cosa cambia: $O(n^2)$ se cuadruplica cuando la entrada se duplica, y $O(2^n)$ se duplica cuando la entrada crece en un solo elemento.

Algunas de estas salen de una recurrencia — un costo definido en términos de sí mismo. Merge sort parte su entrada a la mitad, ordena cada mitad y mezcla los resultados, lo cual es exactamente:

La gráfica de abajo traza el conteo de operaciones de cada clase conforme crece n. El eje y es logarítmico, porque de otro modo la línea de $O(2^n)$ aplastaría todo lo demás contra el piso:

Esa es la teoría. El punto de este libro es que la teoría también aparece en el reloj de pared. Aquí están las mismas formas, pero ahora medidas — una función real por clase, cronometrada con entradas desde 128 hasta 2048 elementos, otra vez con eje y logarítmico:

Las líneas medidas tienen el mismo orden que las teóricas. La línea constante se queda plana contra el piso, la cuadrática es la que sube más empinada, y las brechas entre ellas se ensanchan exactamente como Big-O dice que deberían.

Para qué sirve, para qué no

Big-O es la herramienta correcta cuando quieres saber si un algoritmo escala — si va a seguir funcionando cuando la entrada sea diez o cien veces más grande que tu caso de prueba. Responde eso mejor que cualquier benchmark, porque ignora el ruido que un benchmark no puede ignorar: los factores constantes que cambian con el hardware, el cache y el compilador. Dos ingenieros en máquinas distintas van a estar en desacuerdo sobre los milisegundos y de acuerdo sobre el Big-O.

Lo que oculta son exactamente esas constantes, y a veces las constantes son toda la historia. Un algoritmo $O(n)$ con una constante enorme puede perder contra uno $O(n^2)$ en todas las entradas que vayas a correr en la vida real — por eso la librería estándar usa insertion sort, un algoritmo $O(n^2)$, para arrays cortos. Big-O es además una afirmación asintótica, sobre el comportamiento cuando n se va a infinito; para el n pequeño que tienes enfrente puede ser engañoso. Trátalo como la primera pregunta que haces, nunca la última. Te dice qué algoritmos descartar; medir te dice cuál de los sobrevivientes mandar a producción.

Los datos, o las entradas

Las entradas de este capítulo son aburridas a propósito: listas de enteros. Lo que importa es su tamaño, no su contenido, porque Big-O es una afirmación sobre el tamaño. Cada función hecha desde cero recibe una forma representativa de entrada — una lista ordenada para las búsquedas, una desordenada para el sort, una lista simple para el conteo del loop anidado — y el código de trazas las corre en un rango de tamaños para que podamos ver cómo se curva el costo.

La única entrada que vale la pena mirar de cerca es el array ordenado sobre el que corren las dos búsquedas, porque ahí es donde de verdad puedes ver la diferencia entre un costo lineal y uno logarítmico.

Constrúyelo, una función a la vez

Empieza con lo más barato que existe. El tiempo constante hace una cantidad fija de trabajo sin importar n:

def first(values):
    """O(1): touch one element, no matter how long the list is.

    A million elements or ten, this does the same single indexing operation.
    Constant time is the ceiling every other class is measured against.
    """
    return values[0]

La búsqueda lineal es el costo honesto de una pasada. Mira elementos hasta encontrar lo que busca; en el peor caso los mira todos. La lista opcional probe registra cada índice que toca, y eso es lo que alimenta la animación más adelante:

def linear_search(values, target, probe=None):
    """O(n): scan left to right until the target is found.

    Returns the index of `target`, or -1. Every index it examines is appended to
    `probe` (when given) so the search can be animated. Worst case — the target
    is last or absent — touches all n elements, so the work grows in step with n.
    """
    for i, value in enumerate(values):
        if probe is not None:
            probe.append(i)
        if value == target:
            return i
    return -1

La búsqueda binaria es de donde sale el logaritmo, y solo funciona porque la entrada está ordenada. Mantiene una ventana, mira el centro y tira la mitad que no puede contener el objetivo. Partir n a la mitad una y otra vez es la definición de un logaritmo:

def binary_search(values, target, probe=None):
    """O(log n): halve a SORTED range each step.

    Invariant: if `target` is present it lies in values[lo:hi]. Each iteration
    throws away half of what's left, so the number of steps is the number of
    times n can be halved before nothing remains — log2(n). Each probe records
    the live window (lo, hi, mid) so the animation can show the range collapsing.
    """
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append((lo, hi, mid))
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1      # target is in the right half
        else:
            hi = mid          # target is in the left half
    return -1

Merge sort es el caballo de batalla $O(n \log n)$ y la forma concreta de aquella recurrencia de la sección pasada — partir, ordenar las mitades, mezclar:

def merge_sort(values):
    """O(n log n): split in half, sort each half, merge the two sorted halves.

    The recurrence T(n) = 2T(n/2) + O(n) unfolds to O(n log n): there are log n
    levels of splitting, and the merges at each level together touch all n
    elements. This is the price of a comparison sort that never degrades.
    """
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    return _merge(left, right)


def _merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

El loop anidado es la forma a la que hay que tenerle miedo. Dos loops sobre n significan alrededor de $n^2/2$ comparaciones, que se cuadruplican cada vez que la entrada se duplica:

def count_pairs(values, threshold):
    """O(n^2): every element against every other — a nested loop.

    Counts unordered pairs whose sum exceeds `threshold`. The work is about
    n^2 / 2 comparisons, so when n doubles the cost quadruples. This is the class
    that quietly kills programs: fine on the test data, unusable in production.
    """
    n = len(values)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if values[i] + values[j] > threshold:
                count += 1
    return count

Y el Fibonacci recursivo ingenuo es el cuento con moraleja — la razón de que más adelante exista toda una familia de capítulos dedicada a matar este patrón. Cada llamada hace dos más, así que el trabajo se duplica con cada paso que sube n:

def fib_recursive(n):
    """O(2^n): the naive recursion recomputes the same subproblems endlessly.

    The cautionary tale. Each call spawns two more, so the number of calls
    roughly doubles with every increment of n. Painless at n=25, hopeless at
    n=50. The dynamic-programming chapters exist to fix exactly this.
    """
    if n < 2:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

Ese último no es académico. Cronometrado una vez, fib_recursive(30) tardó alrededor de 51.56 ms en la máquina que generó esta página — para un solo número. Súbelo a 45 y estás esperando minutos; a 60, más de lo que vas a vivir. La misma respuesta, una forma catastrófica.

Míralo trabajar

Este es todo el capítulo en una sola imagen. Ambas búsquedas persiguen el mismo objetivo en el mismo array ordenado de 24 elementos. La fila de arriba es el recorrido lineal, la de abajo es la búsqueda binaria. Naranja es la celda que se examina en este momento, las celdas atenuadas ya quedaron descartadas, azul es el rango que la búsqueda binaria todavía tiene que considerar, y verde es el acierto.

Avanza paso a paso. Mira cómo el recorrido lineal se arrastra celda por celda desde la izquierda mientras la búsqueda binaria salta al centro y tira la mitad del array en cada movimiento. Para este objetivo el recorrido necesita 20 sondeos; la búsqueda binaria necesita 5. Esa brecha es la diferencia entre $O(n)$ y $O(\log n)$, y no hace más que crecer: con un millón de elementos el recorrido necesita un millón de sondeos y la búsqueda binaria necesita veinte.

El código completo

Aquí está todo, ambas versiones en un solo lugar — cambia entre ellas. La pestaña desde cero es las seis funciones ensambladas; la pestaña de librería es lo que escribirías en la práctica, porque Python trae las tres: bisect para la búsqueda binaria, sorted para el sort, list.index para el recorrido lineal. Cada built-in tiene el mismo Big-O que el nuestro — solo que implementado en C.

"""From-scratch reference functions spanning the core complexity classes.

Each function does honest work and can optionally record the operations it
performs (into a `probe` list) so the chapter can animate it. With `probe=None`
the functions run clean, at their natural cost — that's what gets timed. The
point of this chapter is not any one function; it is the SHAPE of the cost as
the input grows, so we keep one small representative of each growth class.
"""


# region: constant_time
def first(values):
    """O(1): touch one element, no matter how long the list is.

    A million elements or ten, this does the same single indexing operation.
    Constant time is the ceiling every other class is measured against.
    """
    return values[0]
# endregion


# region: linear_search
def linear_search(values, target, probe=None):
    """O(n): scan left to right until the target is found.

    Returns the index of `target`, or -1. Every index it examines is appended to
    `probe` (when given) so the search can be animated. Worst case — the target
    is last or absent — touches all n elements, so the work grows in step with n.
    """
    for i, value in enumerate(values):
        if probe is not None:
            probe.append(i)
        if value == target:
            return i
    return -1
# endregion


# region: binary_search
def binary_search(values, target, probe=None):
    """O(log n): halve a SORTED range each step.

    Invariant: if `target` is present it lies in values[lo:hi]. Each iteration
    throws away half of what's left, so the number of steps is the number of
    times n can be halved before nothing remains — log2(n). Each probe records
    the live window (lo, hi, mid) so the animation can show the range collapsing.
    """
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append((lo, hi, mid))
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1      # target is in the right half
        else:
            hi = mid          # target is in the left half
    return -1
# endregion


# region: merge_sort
def merge_sort(values):
    """O(n log n): split in half, sort each half, merge the two sorted halves.

    The recurrence T(n) = 2T(n/2) + O(n) unfolds to O(n log n): there are log n
    levels of splitting, and the merges at each level together touch all n
    elements. This is the price of a comparison sort that never degrades.
    """
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    return _merge(left, right)


def _merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
# endregion


# region: count_pairs
def count_pairs(values, threshold):
    """O(n^2): every element against every other — a nested loop.

    Counts unordered pairs whose sum exceeds `threshold`. The work is about
    n^2 / 2 comparisons, so when n doubles the cost quadruples. This is the class
    that quietly kills programs: fine on the test data, unusable in production.
    """
    n = len(values)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if values[i] + values[j] > threshold:
                count += 1
    return count
# endregion


# region: fib_recursive
def fib_recursive(n):
    """O(2^n): the naive recursion recomputes the same subproblems endlessly.

    The cautionary tale. Each call spawns two more, so the number of calls
    roughly doubles with every increment of n. Painless at n=25, hopeless at
    n=50. The dynamic-programming chapters exist to fix exactly this.
    """
    if n < 2:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)
# endregion

"""The tools a working Python programmer actually reaches for.

The lesson of this chapter's face-off: the library changes the CONSTANT FACTOR,
not the growth class. `bisect` is still O(log n); `sorted` is still O(n log n).
They win because they run in C, not because they bend the asymptotics — the
curve has the same shape, just a gentler slope.
"""
import bisect


# region: linear_builtin
def linear_search_builtin(values, target):
    """O(n): list.index scans left to right, same as the from-scratch loop —
    but the scan runs in C, so the constant is far smaller."""
    try:
        return values.index(target)
    except ValueError:
        return -1
# endregion


# region: binary_builtin
def binary_search_builtin(values, target):
    """O(log n): the standard library's bisect does the halving in C. Returns
    the index of `target`, or -1 if absent, to match the from-scratch signature."""
    i = bisect.bisect_left(values, target)
    if i < len(values) and values[i] == target:
        return i
    return -1
# endregion


# region: sort_builtin
def sort_builtin(values):
    """O(n log n): Timsort. Same asymptotic class as merge sort, but adaptive
    (it exploits runs that are already ordered) and implemented in C."""
    return sorted(values)
# endregion

Desde cero vs librería

Aquí está el duelo, y demuestra el punto central del capítulo mejor que cualquier párrafo. La gráfica cronometra el código desde cero contra el built-in para la búsqueda lineal, la búsqueda binaria y el sort, con tamaños de entrada de hasta 16000. Cada par de líneas tiene la misma forma — porque son la misma clase de complejidad — con la línea de la librería más abajo, porque corre en C:

Con n = 16000 el sort built-in terminó en alrededor de 1.28 ms contra los 15.6 ms de merge sort — más o menos doce veces más rápido. Las búsquedas built-in le ganaron a las nuestras por unas cinco o seis veces. Fíjate en lo que no pasó: la librería no convirtió una búsqueda lineal en una logarítmica, ni un sort cuadrático en uno linearítmico. Hizo más barata la curva de la misma forma por un factor constante. Esa es toda la relación entre Big-O y el rendimiento real. Big-O elige el algoritmo; la constante — el lenguaje, la implementación, el comportamiento del cache — decide qué tan por debajo de la curva aterrizas.

Dónde te lo vas a topar de verdad

El análisis de complejidad no es un ejercicio de salón que dejas atrás; es el vocabulario de toda decisión técnica que involucra datos a escala. Es la razón de que una base de datos use un índice B-tree en vez de escanear cada fila — búsquedas $O(\log n)$ en vez de $O(n)$. Es por lo que un ingeniero senior marca el inocente loop anidado en el code review: ese $O(n^2)$ está bien con las cien filas del fixture de pruebas y es un incendio con el millón de filas de producción. Es lo primero que sondea una entrevista técnica, porque separa a la gente que puede razonar sobre escala de la que solo puede correr código y cruzar los dedos. Y es la etiqueta de cada capítulo que sigue: cada estructura de datos de este libro es en realidad un intercambio — gastar algo de memoria o algo de tiempo de preparación para mover una operación de $O(n)$ a $O(\log n)$ o $O(1)$.

Conclusiones

Big-O es una manera de hablar de cómo crece el trabajo con el tamaño de la entrada, con las constantes descartadas a propósito para que lo que quede sea una propiedad del algoritmo y no de tu hardware. Aprende a leer la escalera — $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$ — y a detectar en qué peldaño se sienta un pedazo de código, normalmente contando loops anidados y preguntándote si cada paso descarta una fracción constante del trabajo.

Úsalo como filtro, no como veredicto. Descarta los algoritmos que no van a escalar y te dice dónde invertir el esfuerzo; después mides para elegir entre lo que queda, porque las constantes que oculta a veces son las que pagan tus cuentas. Cada capítulo restante es una instancia concreta de este intercambio — una estructura que compra un mejor exponente en alguna operación que te importa. De aquí en adelante, cuando construyamos algo y lo pongamos a competir contra la librería, la pregunta siempre es la misma, en dos partes: cuál es el Big-O, y cuál es la constante. Este capítulo es cómo respondes la primera. El resto del libro es cómo te ganas la segunda.