Explicación de la complejidad temporal y espacial de un algoritmo
Imagina dos programas que realizan exactamente la misma tarea. Si les introduces mil registros a cada uno, no podrás distinguirlos. Pero si les introduces mil millones, uno terminará antes de que sueltes la tecla Intro, mientras que el otro seguirá trabajando sin parar el martes que viene.
El mismo portátil. Los mismos datos. Lo que los diferencia es la complejidad temporal, que no es más que una forma de describir la rapidez con la que aumenta la carga de trabajo de un algoritmo a medida que se le proporciona más información.
Analizaremos qué significa realmente el término, cómo se representa con la notación Big O, cómo aplicarlo a un fragmento de código real y dónde entra en juego la complejidad espacial. Finalmente, llegaremos al punto en que todo esto deja de ser tarea y empieza a costar dinero de verdad: los contratos inteligentes.
¿Qué es la complejidad temporal de un algoritmo?
Olvídese de los segundos por un momento. La complejidad temporal se mide en pasos. Comparaciones, asignaciones, un poco de aritmética aquí y allá, y el total se expresa como una función de n, que es el tamaño de la entrada.
Esta es la función más aburrida que puedas imaginar:
python def print_all(items): for item in items: print(item)
¿Diez artículos? Diez recorridos por el circuito. ¿Diez mil? Diez mil recorridos.
El trabajo aumenta en línea recta junto a la entrada, por lo que lo llamamos O(n).
Ahora bien, tal vez cada viaje realmente requiera tres pequeñas operaciones en lugar de una. De acuerdo, eso es 3n. A nadie le importa, la verdad, porque duplicar la lista sigue duplicando el trabajo, y esa curva de crecimiento es lo que nos interesa. El número exacto se descarta a propósito.
Por eso mismo, todos los cursos de Estructuras de Datos y Algoritmos, y la mitad de las entrevistas de programación, hacen tanto hincapié en la complejidad temporal. Si puedes deducir la complejidad de un algoritmo con solo mirarlo, puedes adivinar cómo se comportará con datos de entrada que nunca llegaste a probar. Lo cual, en producción, representa la mayor parte de los datos.
Por qué el tiempo de ejecución es una medida deficiente de un algoritmo
Entonces, ¿por qué no ejecutarlo simplemente con un temporizador? Mucha gente lo hace, y lo entiendo. El problema es que el tiempo de ejecución añade un montón de cosas con las que tu algoritmo no tiene nada que ver:
- Hardware. Mi portátil de cinco años y un servidor en la nube completamente nuevo te darán resultados muy diferentes para el mismo script.
- Lenguaje de programación. Escribe el mismo bucle en C y en Python y podrías ver una diferencia de 10 veces, o incluso más.
- Carga del sistema. Se inicia algún actualizador en segundo plano, el recolector de basura se activa, la caché está vacía. El resultado se mueve.
- Cualquier dato que hayas obtenido. Un algoritmo de ordenación que funciona a la perfección con datos casi ordenados puede ser muy lento con datos desordenados.
Un cronómetro te da una sola medición en un solo dispositivo con una sola entrada. Si le pides cien veces más datos, no te dará nada.
El número de pasos no varía. Con el mismo algoritmo y la misma entrada, se obtiene el mismo número de pasos, ya sea Rust en un servidor o JavaScript en el teléfono de alguien. Por eso, la complejidad temporal es una comparación justa entre dos soluciones antes de realizar las pruebas de rendimiento. Aun así, yo las realizaría después, por si sirve de algo. Simplemente es una cuestión diferente.
Explicación de la notación Big O y otras notaciones asintóticas.
Los libros de texto la llaman notación asintótica, que suena peor de lo que es. Se deja que n crezca enormemente y se deja de prestar atención a los detalles, por lo que los multiplicadores constantes y las entradas pequeñas desaparecen y solo sobrevive la curva de crecimiento. Hay tres de ellas que vale la pena conocer:
| Notación | Lo que describe | Significado simple | Ejemplo |
|---|---|---|---|
| O grande, O(f(n)) | Límite superior | El algoritmo no crece más rápido que f(n). | La búsqueda lineal es O(n). |
| Omega grande, Ω(f(n)) | Límite inferior | El algoritmo necesita al menos f(n) trabajo | Cualquier ordenación por comparación es Ω(n log n) |
| Big-Theta, Θ(f(n)) | Apretado | Los límites superior e inferior coinciden. | La ordenación por fusión es Θ(n log n) |
En la práctica, escucharás la notación Big O aproximadamente el 95% de las veces. Establece un límite superior, lo que significa que el tiempo de ejecución no crecerá más rápido que la tasa dentro de los paréntesis. En mi primera revisión de código en un trabajo real, un desarrollador senior escribió "O(n²), por favor, corrígelo" junto a un bucle anidado, y lo que quería decir era que la complejidad temporal en el peor de los casos era cuadrática y la lista estaba a punto de hacerse mucho más larga.
Omega y Theta se usan principalmente en cursos universitarios sobre análisis de algoritmos, y creo que hace años que no escribo ninguna de las dos en el trabajo. La notación Big O gana porque responde a la pregunta que la gente realmente hace en una reunión: "¿Qué tan grave se vuelve esto si el tráfico se triplica?".
Hay un detalle técnico que me confundió durante un tiempo. Dado que la notación Big O solo representa un límite superior, una función O(n) también es O(n²), estrictamente hablando, del mismo modo que una persona de 1,52 metros (5 pies) mide menos de 2,13 metros (7 pies). Cierto, pero inútil. Cada quien cita el límite más estricto que puede justificar, y yo haré lo mismo.
Clases de complejidad temporal comunes con ejemplos
No hay muchas clases que verás en código real, tal vez siete si contamos las más complejas. Esto es aproximadamente lo que cuesta cada una con n = 1000:
| Clase | Nombre | Ejemplo típico | Operaciones con n = 1000 |
|---|---|---|---|
| O(1) | Constante | Índice de matriz, búsqueda en tabla hash | 1 |
| O(log n) | Logarítmico | Búsqueda binaria | ~10 |
| En) | Lineal | Escanear una lista | 1.000 |
| O(n log n) | Linearítmico | Ordenación por fusión, ordenación rápida (promedio) | ~10.000 |
| O(n²) | Cuadrático | Bucles anidados, ordenación de burbuja | 1.000.000 |
| O(2ⁿ) | Exponencial | Fibonacci recursivo ingenuo | Más que átomos en el universo |
| ¡En!) | Factorial | Vendedor ambulante de fuerza bruta | Aún más grande |
O(1): Tiempo constante
Ya sea que tu diccionario de Python tenga diez claves o diez millones, extraer una por clave cuesta prácticamente lo mismo, al igual que leer items[5] de una lista. Esa uniformidad es la clave del tiempo constante.
O(log n): Tiempo logarítmico
Pienso en estos algoritmos como el de "adivina el número entre 1 y 100", donde cada intento descarta la mitad de lo que queda. La búsqueda binaria hace exactamente eso en una lista ordenada:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Con mil millones de elementos ordenados, necesita unas 30 comparaciones, mientras que revisarlos uno por uno podría llevar los mil millones completos, y nunca he dejado de encontrar eso gracioso.
O(n) y O(n log n)
Un algoritmo lineal visita cada elemento un número fijo de veces, como si buscaras a simple vista el número más grande en una columna de una hoja de cálculo. O(n log n) es el umbral para una ordenación eficiente. El algoritmo de ordenación por fusión divide la lista en elementos individuales (log n niveles de división) y luego realiza una pasada lineal por nivel durante la fusión, por lo que su tiempo de ejecución se mantiene constante independientemente de si los datos llegan ordenados o desordenados.
O(n²) y peor
El código cuadrático casi siempre tiene un bucle dentro de otro bucle, como esta comprobación de duplicados que compara cada par:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
El crecimiento exponencial y factorial es muchísimo peor. El método recursivo de Fibonacci de los libros de texto resuelve los mismos subproblemas una y otra vez, por lo que cada incremento de n prácticamente duplica el trabajo. Con n = 20 no lo notarás; con n = 60 puedes ir a preparar la cena, comerla, lavar los platos y aún así no habrá terminado.
Cómo calcular la complejidad temporal paso a paso
Casi nunca se necesita una demostración formal para calcular la complejidad temporal. Repaso mentalmente esta lista y abarca la mayor parte del código que veo:
- Defina n. Decida cuál es el tamaño de entrada: la longitud de una lista, el número de nodos en un grafo, el número de dígitos en un número.
- Cuenta el trabajo en cada línea. Las instrucciones simples (asignaciones, comparaciones, aritméticas) cuestan O(1).
- Añade bloques secuenciales. Dos bucles uno tras otro, cada uno sobre n, dan como resultado n + n = 2n.
- Multiplicar bloques anidados. Un bucle sobre n dentro de otro bucle sobre n da como resultado n × n = n².
- Elimina las constantes. 2n se convierte en n, y 500 se convierte en 1.
- Conserva solo el término dominante. En n² + n, la parte n² predomina sobre el resto a medida que n aumenta.
Un ejemplo rápido. El resultado es T(n) = 3n² + 5n + 2. Sustituimos un millón: 3n² son tres billones, 5n son cinco millones. Error de redondeo. Lo llamamos O(n²), listo.
Los bucles que se saltan uno en lugar de avanzar paso a paso son más astutos:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Cada iteración reduce n a la mitad, por lo que este bucle while se detiene después de aproximadamente log₂(n) iteraciones. Esta es, básicamente, la respuesta a la pregunta "¿cuándo la complejidad temporal es O(log n)?". Si lo que queda se reduce por un factor constante en cada paso, se ha alcanzado ese punto.
La recursión requiere una herramienta más: una recurrencia. El algoritmo de ordenación por fusión realiza dos operaciones de tamaño reducido y luego una fusión, por lo que T(n) = 2T(n/2) + n. El teorema maestro es una guía rápida para recurrencias de esa forma, y para esta en particular arroja un valor de O(n log n).
Y una regla general de la programación competitiva en la que me apoyo mucho: una máquina normal realiza aproximadamente 10⁸ operaciones simples por segundo. Es una aproximación, pero suficiente para comprobar la complejidad temporal de una solución antes de enviarla. Con n = 10⁵, O(n²) son aproximadamente 10¹⁰ operaciones, por lo que se agota el tiempo. O(n log n) es inferior a 2 millones. Se ejecuta sin problemas.
Análisis del peor caso, el mejor caso y el caso promedio
Si se introducen diferentes datos en el mismo algoritmo, la cantidad de trabajo puede variar enormemente. La búsqueda lineal lo demuestra claramente:
- En el mejor de los casos, lo que buscas está justo al frente. Una comparación y te quedas fuera.
- En el peor de los casos: está al final, o no está en absoluto. Eso son comparaciones.
- Caso promedio: si pudiera estar en cualquier lugar con igual probabilidad, comprobarás alrededor de n/2 en promedio. Aun así, O(n), ojo.
Si le preguntas a un desarrollador sobre "la complejidad" de algo, casi siempre te dará la complejidad temporal en el peor de los casos, porque ese número es una promesa en torno a la cual puedes planificar.
Supongamos que tu API procesa una solicitud en O(n) como máximo. Perfecto, ahora sabes cómo se comporta la solicitud más lenta y, además, estás protegido si alguien te envía datos basura a propósito. Esto es algo que ocurre con frecuencia: si un atacante descubre qué claves provocan una colisión en tu tabla hash, esas serán las únicas claves que verás durante un tiempo.
Vale la pena analizar el caso promedio cuando el escenario desfavorable rara vez se presenta. Quicksort es el ejemplo paradigmático, con una complejidad promedio de O(n log n), pero que puede llegar a O(n²) si se eligen pivotes de forma ingenua en datos que ya están ordenados. Las bibliotecas estándar solucionan este problema utilizando pivotes aleatorios o cambiando a un algoritmo de ordenación diferente cuando la recursión alcanza niveles excesivamente profundos.
¿Qué es la complejidad espacial y el espacio auxiliar?
La memoria es otro gasto que conlleva un algoritmo. La complejidad espacial indica cuánta memoria se necesita a medida que aumenta el tamaño de la entrada, y se expresa con la misma notación Big O que el tiempo.
Parte de esa memoria es la entrada en sí, por la que pagas independientemente de lo que hagas con ella. La parte que realmente controlas se llama espacio auxiliar, es decir, la información adicional que tu código asigna mientras se ejecuta, como variables temporales y nuevos arreglos, además de la pila de llamadas que nadie recuerda hasta que les causa problemas.
Algunos ejemplos rápidos:
- Intercambiar dos variables necesita un par de ranuras independientemente de cualquier otra cosa, por lo que es un espacio auxiliar O(1).
- Copiar una lista de n elementos en una lista nueva le cuesta O(n) memoria adicional.
- La recursión a n niveles de profundidad deja n marcos en la pila, lo que es un espacio O(n) aunque nunca hayas construido una matriz.
Vi a un desarrollador junior perder una tarde entera con ese último problema. Su función recursiva parecía no usar memoria en absoluto, pero cada llamada incompleta se quedaba en la pila esperando a que las más profundas devolvieran el resultado, y con una entrada grande, todo fallaba con un desbordamiento de pila.
Gran parte de la optimización consiste simplemente en intercambiar memoria por tiempo, o viceversa. La memorización almacena en caché los resultados ya calculados, lo que reduce el tiempo de cálculo de Fibonacci de O(2ⁿ) a O(n) a cambio de O(n) de memoria. Las tablas hash ofrecen un promedio de O(1) consultas al ocupar espacio en cubetas. En un servidor con 64 GB de RAM, este intercambio suele ser una decisión obvia, pero en un microcontrolador o dentro de un contrato inteligente, conviene pensarlo dos veces.
Complejidad temporal y espacial de las estructuras de datos comunes
Elegir la estructura de datos adecuada suele ser más efectivo que optimizar minuciosamente el código dentro del bucle. Costos promedio para las estructuras que usarás con mayor frecuencia:
| Estructura de datos | Acceso | Buscar | Insertar | Borrar | Espacio |
|---|---|---|---|---|---|
| Formación | O(1) | En) | En) | En) | En) |
| Lista enlazada | En) | En) | O(1) | O(1) | En) |
| Tabla hash | n / A | O(1) | O(1) | O(1) | En) |
| Árbol de búsqueda binaria equilibrado | O(log n) | O(log n) | O(log n) | O(log n) | En) |
| Montón binario | O(1) para min/max | En) | O(log n) | O(log n) | En) |
Dos notas al pie. Las inserciones y eliminaciones en listas enlazadas solo tienen una complejidad de O(1) si ya se posee el nodo. Y una tabla hash puede llegar a tener una complejidad de O(n) cuando se producen colisiones entre muchas claves.
Los algoritmos de ordenación varían igualmente:
| Algoritmo de ordenación | Mejor | Promedio | El peor | Espacio auxiliar |
|---|---|---|---|---|
| Clasificación de burbujas | En) | O(n²) | O(n²) | O(1) |
| Ordenación por fusión | O(n log n) | O(n log n) | O(n log n) | En) |
| Ordenación rápida | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Ordenación por montículos | O(n log n) | O(n log n) | O(n log n) | O(1) |
El algoritmo Merge Sort es predecible, pero requiere memoria adicional. El algoritmo Heap Sort ordena in situ y mantiene el mismo resultado en el peor de los casos. Quicksort, a pesar de su límite superior menos eficiente, suele ser superior en la práctica.
Complejidad temporal en blockchain y contratos inteligentes
Aquí es donde empieza lo interesante. En tu propio servidor, un algoritmo deficiente consume CPU y puede molestar a algún usuario. En Ethereum o cualquier cadena EVM, supone un derroche de dinero. Cada operación que ejecuta un contrato inteligente cuesta gas, que se paga con la criptomoneda nativa de la cadena, por lo que el número de operaciones aparece en la factura de alguien. En otras palabras, una mala complejidad temporal tiene un precio.
Digamos que tienes un contrato que recorre a todos los poseedores de tokens para pagar recompensas. O(n), y el gas aumenta gradualmente con cada nuevo poseedor. El día del lanzamiento nadie se da cuenta.
Entonces, la lista de poseedores sigue creciendo. Un día, el pago requiere más gas que el límite de gas del bloque, que es el tope de la cantidad de gas que puede contener un solo bloque. Después de eso, la transacción no se puede completar. No es que sea lenta. Simplemente nunca se completa, y los fondos que estaban esperando detrás de esa función quedan bloqueados. Los auditores clasifican los bucles infinitos como este como denegación de servicio, y con razón.
Las soluciones son, simple y llanamente, pensar en la complejidad:
- Divide el trabajo en lotes de tamaño fijo a lo largo de varias transacciones.
- Dale la vuelta para que cada usuario reclame su propia recompensa. Cada llamada es O(1).
- Sustituye el bucle por una prueba Merkle.
Me encantan las pruebas Merkle como ejemplo de por qué log n es tan importante en la cadena de bloques. Un árbol Merkle aplica un hash a una gran cantidad de datos, convirtiéndolos en un único hash raíz.
Para demostrar que una entrada pertenece a un conjunto de n, se necesitan aproximadamente log₂(n) hashes. Para un millón de entradas, eso equivale a unos 20, no a un millón. Los airdrops se basan en esto, y las carteras ligeras de Bitcoin utilizan el mismo truco para confirmar una transacción sin descargar el bloque completo.
Fuera de la cadena, ocurre lo mismo. Imagina un sistema de pago que relaciona cada transacción entrante de la cadena de bloques con una factura escaneando todas las facturas abiertas. Esto implica una complejidad de O(n) por pago, y se vuelve más lento a medida que crece el negocio. Si colocas las facturas en un mapa hash indexado por dirección o ID, cada coincidencia tiene una complejidad de O(1). Y si prefieres no desarrollar ni gestionar tú mismo esta infraestructura, una pasarela de pago de criptomonedas como Plisio lo hace por ti.
