Complejidad y notación O grande

La idea

Cronometrar un programa dice poco: el resultado depende de la máquina, del lenguaje y de lo que esté haciendo el sistema operativo. Para comparar algoritmos se cuentan operaciones elementales (comparaciones, intercambios, sumas) en función del tamaño de la entrada n. Esa función T(n) se resume con la notación O grande, que descarta las constantes y los términos de orden inferior: escribimos T(n) = O(f(n)) cuando existen una constante c > 0 y un tamaño n₀ tales que T(n) ≤ c·f(n) para todo n ≥ n₀. Así, 3n² + 20n + 500 es O(n²), porque para n suficientemente grande el término cuadrático domina a todos los demás.

La jerarquía de crecimiento es la brújula del oficio: constante O(1) (acceder a una posición de un arreglo), logarítmica O(log n) (búsqueda binaria), lineal O(n) (recorrer una lista), lineal-logarítmica O(n log n) (ordenamiento por mezcla), cuadrática O(n²) (burbuja, comparar todos los pares), exponencial O(2ⁿ) (enumerar subconjuntos) y factorial O(n!) (enumerar permutaciones). La diferencia no es cosmética: al duplicar n, un algoritmo lineal tarda el doble, uno cuadrático cuatro veces más y uno exponencial eleva su coste al cuadrado. Con 2ⁿ y n = 60 ya no hay computadora, ni tiempo, que alcance.

Conviene distinguir el peor caso (cota superior garantizada), el mejor caso y el caso promedio, y no olvidar la complejidad espacial: la memoria también se cuenta. Y hay un matiz práctico importante: las constantes ocultas sí importan cuando n es pequeño. Un algoritmo O(n log n) con mucha sobrecarga puede perder frente a una inserción O(n²) para n = 16, y por eso las bibliotecas reales combinan estrategias y cambian de método según el tamaño del bloque que están procesando.

Fórmulas clave

• Definición de O grandeT(n) = O(f(n)) ⇔ ∃ c > 0, n₀ : T(n) ≤ c · f(n) para todo n ≥ n₀
• Búsqueda linealT(n) = n comparaciones en el peor caso → O(n)
• Búsqueda binariaT(n) = ⌊log₂ n⌋ + 1 → O(log n)
• Burbuja y selecciónC(n) = n(n − 1)/2 → O(n²)
• Ordenamiento por mezclaT(n) = 2 T(n/2) + n → O(n log n)
• JerarquíaO(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ) ⊂ O(n!)

Dónde se aplica

Un buscador web no puede recorrer miles de millones de páginas por consulta: usa índices invertidos que convierten la búsqueda en O(log n) o casi O(1). En bases de datos, añadir un índice B-tree cambia una consulta de O(n) a O(log n), y esa es la diferencia entre responder en un segundo o en una hora. En criptografía ocurre lo contrario: la seguridad de RSA se apoya en que factorizar un número de 2048 bits es exponencialmente costoso. Y en ingeniería de software, el análisis asintótico explica por qué un prototipo que funcionaba con 100 usuarios se derrumba con 100 000.

Con programación (Python)

import math, random

def ops_busqueda_lineal(a, x):
    c = 0
    for v in a:
        c += 1
        if v == x:
            return c
    return c

def ops_burbuja(a):
    b, c = list(a), 0
    for i in range(len(b) - 1):
        for j in range(len(b) - 1 - i):
            c += 1
            if b[j] > b[j + 1]:
                b[j], b[j + 1] = b[j + 1], b[j]
    return c

print(f"{'n':>5} {'lineal':>8} {'burbuja':>9} {'n(n-1)/2':>10} {'log2 n':>8}")
for n in [8, 16, 32, 64, 128]:
    a = random.sample(range(1000), n)
    lineal = ops_busqueda_lineal(a, -1)      # no está: peor caso = n
    print(f"{n:>5} {lineal:>8} {ops_burbuja(a):>9} {n*(n-1)//2:>10} {math.log2(n):>8.2f}")

print("Con n = 1000: lineal 1000, n log2 n =", round(1000 * math.log2(1000)), ", n^2 = 1000000")
print("Con n = 40 un algoritmo 2^n necesita", 2 ** 40, "operaciones: inviable")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Búsqueda binaria · Algoritmos de ordenamiento · Recursión y memoización · Grafos y caminos mínimos: Dijkstra