Cheat sheet de Big-O
Complejidad temporal y espacial de cada estructura de datos y algoritmo de BytePatterns, de las tablas hash a Dijkstra, cada fila con su lección animada.
Actualizado el 78 filas94 lecciones enlazadasSe imprime limpia: usa la impresión de tu navegador
Cómo leerla
- n es el tamaño de la entrada. Las constantes y los términos menores se descartan: 3n + 5 es O(n).
- El tiempo es el peor caso salvo que la celda diga avg (promedio) o amortized (amortizado: barato en promedio a lo largo de muchas operaciones, aunque una de ellas sea costosa).
- El espacio es espacio extra: memoria además de la entrada, sin contar la salida. La recursión cuenta: su pila de llamadas es espacio.
- V y E son vértices y aristas; m y n son las dos longitudes en un problema de dos strings o de cuadrícula. Cualquier otra letra se define en su fila.
- Constante o logarítmica
- Lineal o n log n
- Polinomial
- Exponencial o factorial
¿Es nueva para ti la notación? El módulo de Big-O la explica una idea a la vez: ¿Qué es Big-O?, O(1) y O(n), O(log n) y la división a la mitad, O(n²) y bucles anidados, Comparar complejidades.
Órdenes de crecimiento
La forma importa más que los números: una solución O(n²) que va bien con n = 100 no tiene remedio con n = 100 000. El gráfico muestra la forma para n pequeños; la tabla muestra la cantidad de pasos en tamaños que aparecen en restricciones reales.
| Orden | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) constante | 1 | 1 | 1 |
| O(log n) logarítmica | 3.3 | 10 | 19.9 |
| O(n) lineal | 10 | 1,000 | 1,000,000 |
| O(n log n) linearítmica | 33.2 | 9,966 | ≈ 107 |
| O(n2) cuadrática | 100 | 1,000,000 | ≈ 1012 |
| O(2n) exponencial | 1,024 | ≈ 10301 | ≈ 10301029 |
| O(n!) factorial | 3,628,800 | ≈ 102567 | ≈ 105565708 |
| Límite de entrada | Suele alcanzar |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 20 | O(2n) |
| n ≤ 500 | O(n3) |
| n ≤ 5000 | O(n2) |
| n ≤ 106 | O(n log n) |
| n ≤ 107 | O(n) |
| más grande | O(log n) u O(1) |
Una regla práctica para un límite de un segundo, suponiendo unos 10⁷–10⁸ pasos simples por segundo. Los factores constantes y el lenguaje la mueven; el orden de las filas no cambia.
Estructuras de datos
Lo que cuesta cada operación. Los títulos de las tarjetas enlazan a la lección que la anima.
Array dinámico
- Leer / escribir por índice
- O(1)
- Buscar (sin ordenar)
- O(n)
- Agregar al final
- O(1) amortized
- Insertar / eliminar en el medio
- O(n)
- Espacio
- O(n)
Cada elemento que está después del hueco tiene que desplazarse.
Lista simplemente enlazada
- Llegar al k-ésimo nodo
- O(n)
- Buscar
- O(n)
- Insertar / eliminar en la cabeza
- O(1)
- Insertar / eliminar tras un nodo conocido
- O(1)
- Espacio
- O(n)
Ver también: Inserción y eliminación
Lista doblemente enlazada
- Push / pop en cualquier extremo
- O(1)
- Desenlazar un nodo que ya tienes
- O(1)
- Buscar
- O(n)
- Espacio
- O(n)
El puntero prev es lo que hace que desenlazar sea O(1): la base de una caché LRU.
Pila
- Push / pop / peek
- O(1)
- Buscar
- O(n)
- Espacio
- O(n)
Cola / deque
- Encolar / desencolar
- O(1)
- Ver el frente
- O(1)
- Buscar
- O(n)
- Espacio
- O(n)
Quitar del frente de un array común es O(n): usa un deque (cola doble) o un buffer circular.
Ver también: Cola circular
Tabla hash (map / set)
- Buscar
- O(1) avgO(n) worst
- Insertar
- O(1) avgO(n) worst
- Eliminar
- O(1) avgO(n) worst
- Espacio
- O(n)
El peor caso es que todas las claves caigan en un mismo bucket. No hay orden: recorrerla ordenada cuesta O(n log n).
Ver también: Cuando el hashing falla
Heap binario
- Ver el mínimo / máximo
- O(1)
- Push
- O(log n)
- Pop del mínimo / máximo
- O(log n)
- Construirlo con n elementos (heapify)
- O(n)
- Buscar
- O(n)
- Espacio
- O(n)
Ver también: Heapify y sift · Cola de prioridad
Árbol binario de búsqueda
- Buscar / insertar / eliminar
- O(h)
- …si está balanceado
- O(log n)
- …si está degenerado (una cadena)
- O(n)
- Recorrido inorden
- O(n)
- Espacio
- O(n)
h es la altura. Una entrada ordenada construye la cadena.
Ver también: Inserción y búsqueda en un BST · Profundidad y balance de un árbol
Trie
- Insertar una palabra
- O(L)
- Buscar una palabra
- O(L)
- ¿Empieza con un prefijo?
- O(L)
- Espacio
- O(total characters)
L es la longitud de la palabra o del prefijo, sin importar cuántas palabras haya guardadas.
Ver también: Búsqueda por prefijo · Trie vs. hash set
Union-find (conjuntos disjuntos)
- Find / union, con ambas optimizaciones
- O(α(n)) amortized
- …solo con unión por tamaño
- O(log n)
- …sin ninguna
- O(n)
- Espacio
- O(n)
α es la inversa de la función de Ackermann: como mucho 4 para cualquier entrada que quepa en memoria.
Ver también: Compresión de caminos · Unión por rango o tamaño
Grafo — lista de adyacencia
- ¿Hay una arista u → v?
- O(deg u)
- Visitar todos los vecinos de u
- O(deg u)
- Agregar una arista
- O(1)
- Espacio
- O(V + E)
La opción por defecto para grafos dispersos, que son la mayoría de los grafos de entrevista.
Ver también: Fundamentos de grafos
Grafo — matriz de adyacencia
- ¿Hay una arista u → v?
- O(1)
- Visitar todos los vecinos de u
- O(V)
- Agregar una arista
- O(1)
- Espacio
- O(V2)
Solo conviene si el grafo es denso o V es pequeño.
Ordenamiento
Los ordenamientos por comparación no pueden bajar de O(n log n) en el peor caso; counting sort (ordenamiento por conteo) y radix sort (ordenamiento por base) esquivan ese límite porque no comparan.
| Algoritmo | Mejor | Promedio | Peor | Espacio | Estable | Notas |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n2) | O(n2) | O(1) | Sí | El mejor caso O(n) requiere cortar cuando una pasada no hace intercambios. |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) | No | Como mucho n − 1 intercambios: su única ventaja. |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) | Sí | Rápido con una entrada casi ordenada. |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí | |
| Quicksort | O(n log n) | O(n log n) | O(n2) | O(log n) | No | El peor caso viene de elegir malos pivotes una y otra vez; la pila crece entonces hasta O(n). |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Sí | k es el rango de valores. Solo enteros (o claves). |
| Radix sort | O(d·(n + b)) | O(d·(n + b)) | O(d·(n + b)) | O(n + b) | Sí | d dígitos en base b, una pasada estable por dígito. |
Búsqueda
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| Búsqueda lineal | O(n) | O(1) | |
| Búsqueda binaria | O(log n) | O(1) | Entrada ordenada. Versión iterativa; la recursiva suma O(log n) de pila. |
| Búsqueda en un array ordenado y rotado | O(log n) | O(1) | Valores distintos. Con duplicados puede llegar a O(n). |
| Encontrar un pico | O(log n) | O(1) | |
| Búsqueda binaria sobre la respuesta | O(Clog R) | O(1) | R es el tamaño del rango de respuestas; C, el costo de comprobar si una respuesta es factible. |
| Búsqueda en una matriz 2D ordenada (escalera) | O(m + n) | O(1) | m filas, n columnas; cada paso descarta una fila o una columna. |
Técnicas con arrays, listas y strings
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| Dos punteros | O(n) | O(1) | |
| Ventana deslizante | O(n) | O(k) | Cada elemento entra y sale una vez; k es lo que la ventana tiene que recordar. |
| Sumas de prefijos | O(n) buildO(1) per query | O(n) | |
| Suma de subarrays con un hash map | O(n) | O(n) | |
| Subarray máximo de Kadane | O(n) | O(1) | |
| Product of array except self | O(n) | O(1) | Sin contar el array de salida. |
| Bandera nacional holandesa (partición en 3) | O(n) | O(1) | |
| Punteros rápido y lento (detección de ciclos) | O(n) | O(1) | |
| Invertir una lista enlazada | O(n) | O(1) | Versión iterativa. La recursión cuesta O(n) de pila. |
| Pila monótona | O(n) amortized | O(n) | Cada elemento entra en la pila una vez y sale como mucho una vez. |
| Máximo en ventana deslizante (deque) | O(n) | O(k) | |
| Búsqueda de patrones con KMP | O(n + m) | O(m) | n es el texto; m, el patrón. |
| Rolling hash de Rabin–Karp | O(n + m) avgO(n·m) worst | O(1) | El peor caso es que el hash de cada ventana colisione. |
| Algoritmo Z | O(n + m) | O(n + m) |
Heaps y orden
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| Top-k con un heap de tamaño k | O(n log k) | O(k) | |
| Top-k más frecuentes con buckets | O(n) | O(n) | |
| K-way merge | O(N log k) | O(k) | N elementos en total, repartidos entre k listas ordenadas. |
| Mediana acumulada (dos heaps) | O(log n) addO(1) median | O(n) | |
| Fusionar intervalos | O(n log n) | O(n) | Domina el ordenamiento; el barrido es O(n). |
| Meeting rooms (min-heap de horas de fin) | O(n log n) | O(n) |
Grafos y cuadrículas
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| Búsqueda en anchura | O(V + E) | O(V) | |
| Búsqueda en profundidad | O(V + E) | O(V) | Un DFS recursivo puede chocar con el límite de la pila en un camino largo. |
| Camino más corto sin pesos (BFS) | O(V + E) | O(V) | |
| Flood fill / islas en una cuadrícula | O(R·C) | O(R·C) | R filas × C columnas: cada celda se visita una vez. |
| Ordenamiento topológico (Kahn) | O(V + E) | O(V) | |
| Dijkstra (heap binario) | O((V + E) log V) | O(V) | Solo pesos no negativos. |
| Bellman–Ford | O(V·E) | O(V) | Admite pesos negativos y detecta ciclos negativos. |
| Árbol de expansión mínima (Kruskal) | O(E log E) | O(V) | Ordena las aristas y luego usa union-find. |
| Árbol de expansión mínima (Prim, heap binario) | O(E log V) | O(V) | |
| Verificar si es bipartito (bicoloración) | O(V + E) | O(V) | |
| Componentes fuertemente conexos | O(V + E) | O(V) |
Programación dinámica
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| Climbing stairs / estilo Fibonacci | O(n) | O(1) | Dos variables que se van actualizando, en lugar de la tabla. |
| House robber | O(n) | O(1) | |
| Coin change (mínimo de monedas) | O(n·A) | O(A) | n tipos de moneda; A, el monto. |
| Mochila 0/1 | O(n·W) | O(W) | W es la capacidad; una sola fila, que se llena de derecha a izquierda. |
| Subsecuencia común más larga | O(m·n) | O(m·n) | O(min(m, n)) de espacio si solo se necesita la longitud. |
| Distancia de edición | O(m·n) | O(m·n) | |
| Subsecuencia creciente más larga (DP) | O(n2) | O(n) | |
| Subsecuencia creciente más larga (tails) | O(n log n) | O(n) | |
| Caminos en una cuadrícula | O(m·n) | O(n) | Una fila de la tabla a la vez. |
| DP de intervalos (cadena de matrices) | O(n3) | O(n2) |
Recursión y backtracking
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| Fibonacci recursivo ingenuo | O(2n) | O(n) | Es una cota superior; la cota ajustada es de unos 1.618ⁿ. |
| Recursión con memoización (Fibonacci) | O(n) | O(n) | |
| Todos los subconjuntos | O(n·2n) | O(n) | Sin contar la salida. |
| Todas las permutaciones | O(n·n!) | O(n) | Sin contar la salida. |
| N-queens | O(n!) | O(n) | Cota superior; la poda recorta la mayor parte. |
Matemáticas y bits
| Algoritmo | Tiempo | Espacio | Notas |
|---|---|---|---|
| MCD (Euclides) | O(log min(a, b)) | O(1) | |
| Exponenciación rápida | O(log n) | O(1) | Elevar al cuadrado de forma iterativa; n es el exponente. |
| Criba de Eratóstenes | O(n log log n) | O(n) | |
| XOR para encontrar el número único | O(n) | O(1) | |
| Contar bits encendidos (apagar el 1 más bajo) | O(k) | O(1) | k es la cantidad de bits en 1: como mucho, el tamaño de palabra. |
| Comprobar si es potencia de dos | O(1) | O(1) |
bytepatterns.com/cheatsheets/big-o: cada fila enlaza ahí a una lección animada.