Notación Big O explicada con ejemplos

Qué problema resuelve Big O

Medir un programa en segundos solo dice algo sobre una máquina, un lenguaje y una entrada. Big O responde a una pregunta más útil: si la entrada se hace 10 veces mayor, ¿cuánto más trabajo hace el algoritmo? Un algoritmo que hace 10 veces más trabajo escala de forma muy distinta a uno que hace 100 veces más.

Formalmente, f(n) es O(g(n)) si existen constantes c y n₀ tales que f(n) ≤ c · g(n) para todo n ≥ n₀. En palabras sencillas, g es una cota superior del crecimiento de f cuando n es suficientemente grande, ignorando los factores constantes.

• n es el tamaño de la entrada: la longitud de una lista, el número de caracteres de una cadena, el número de nodos de un grafo.
• La complejidad temporal cuenta los pasos básicos (comparaciones, asignaciones, operaciones aritméticas).
• La complejidad espacial cuenta la memoria extra utilizada, sin contar la propia entrada.

Cómo simplificar una expresión

Cuenta los pasos como una función de n y aplica dos reglas: descarta los factores constantes y conserva solo el término dominante.

Cuando un algoritmo tiene dos entradas independientes, conserva ambas: recorrer una lista de longitud n y luego otra de longitud m es O(n + m), y un bucle dentro de otro es O(n · m). La base del logaritmo no importa en Big O, porque log₂ n y log₁₀ n solo se diferencian en un factor constante.

Clases de complejidad comunes

Una guía aproximada: en un ordenador moderno, un bucle simple puede ejecutar decenas de millones de pasos básicos por segundo en Python y mucho más en lenguajes compilados. Así, O(n log n) funciona bien con millones de elementos, O(n²) se vuelve lento hacia las decenas de miles y O(2ⁿ) no es viable más allá de unos 40 a 60 elementos.

Cómo leer la complejidad en código Python

Fíjate en los bucles. Un único bucle sobre la entrada es O(n). Un bucle anidado en otro sobre la misma entrada es O(n²). Un bucle que reduce a la mitad el rango restante en cada vuelta es O(log n).

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

Las llamadas a bibliotecas tienen su propio coste. x in some_list es O(n), x in some_set es O(1) en promedio, list.insert(0, x) es O(n) porque se desplazan todos los elementos, y sorted() es O(n log n). Un bucle que llama n veces a una operación O(n) es O(n²), aunque parezca un solo bucle.

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

Mejor, promedio y peor caso

El mismo algoritmo puede hacer cantidades de trabajo distintas con entradas diferentes del mismo tamaño, por lo que la complejidad suele indicarse para tres casos.

Cuando alguien dice solo «la complejidad de X», normalmente se refiere al peor caso, o al caso promedio en las tablas hash y en quicksort. El coste amortizado es una cuarta idea: añadir un elemento a una lista de Python es ocasionalmente O(n) cuando la lista amplía su almacenamiento, pero O(1) en promedio a lo largo de muchas inserciones.

Big O, Big Omega y Big Theta

Estrictamente, un algoritmo O(n) también es O(n²), porque O es solo una cota superior. En el uso cotidiano, la gente escribe Big O pero se refiere a la cota más ajustada que conoce, que es lo que expresa Θ.

Errores comunes

• Olvidar el coste de las operaciones integradas, como in en una lista o el slicing items[1:], que copia y cuesta O(k) para k elementos copiados.
• Contar mal las llamadas recursivas: una función que se llama dos veces con n − 1 es O(2ⁿ), no O(n).
• Ignorar el espacio: construir una lista nueva de tamaño n, o una recursión de profundidad n, cuesta O(n) de memoria.
• Escribir O(2n) u O(n + 5). Ambas se simplifican a O(n).