Saltar al contenido

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.

Cómo crecen las clases de complejidad más comunesPasos según el tamaño de entrada n, de 1 a 20, con corte en 60 pasos. O(1) se mantiene plana y O(log n) apenas sube; O(n) sube de forma constante y O(n log n) un poco más rápido; O(n²) sale del gráfico antes de que n llegue a 8, O(2ⁿ) antes de 6 y O(n!) antes de 5.15101520tamaño de entrada n →pasos →O(n!)O(2n)O(n2)O(n log n)O(1)O(log n)O(n)
Pasos según n, de n = 1 a 20, con corte en 60 pasos.
Pasos en tamaños de entrada reales
Ordenn = 10n = 1,000n = 1,000,000
O(1) constante111
O(log n) logarítmica3.31019.9
O(n) lineal101,0001,000,000
O(n log n) linearítmica33.29,966≈ 107
O(n2) cuadrática1001,000,000≈ 1012
O(2n) exponencial1,024≈ 10301≈ 10301029
O(n!) factorial3,628,800≈ 102567≈ 105565708
De la restricción a la complejidad
Límite de entradaSuele alcanzar
n ≤ 10O(n!)
n ≤ 20O(2n)
n ≤ 500O(n3)
n ≤ 5000O(n2)
n ≤ 106O(n log n)
n ≤ 107O(n)
más grandeO(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.

Algoritmos de ordenamiento: tiempo en el mejor caso, promedio y peor caso, espacio extra y estabilidad
AlgoritmoMejorPromedioPeorEspacioEstableNotas
Bubble sortO(n)O(n2)O(n2)O(1)SíEl mejor caso O(n) requiere cortar cuando una pasada no hace intercambios.
Selection sortO(n2)O(n2)O(n2)O(1)NoComo mucho n − 1 intercambios: su única ventaja.
Insertion sortO(n)O(n2)O(n2)O(1)SíRápido con una entrada casi ordenada.
Merge sortO(n log n)O(n log n)O(n log n)O(n)Sí
QuicksortO(n log n)O(n log n)O(n2)O(log n)NoEl peor caso viene de elegir malos pivotes una y otra vez; la pila crece entonces hasta O(n).
Heap sortO(n log n)O(n log n)O(n log n)O(1)No
Counting sortO(n + k)O(n + k)O(n + k)O(n + k)Sík es el rango de valores. Solo enteros (o claves).
Radix sortO(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

Búsqueda: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
Búsqueda en un array ordenado y rotadoO(log n)O(1)Valores distintos. Con duplicados puede llegar a O(n).
Encontrar un picoO(log n)O(1)
Búsqueda binaria sobre la respuestaO(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

Técnicas con arrays, listas y strings: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
Dos punterosO(n)O(1)
Ventana deslizanteO(n)O(k)Cada elemento entra y sale una vez; k es lo que la ventana tiene que recordar.
Sumas de prefijosO(n) buildO(1) per queryO(n)
Suma de subarrays con un hash mapO(n)O(n)
Subarray máximo de KadaneO(n)O(1)
Product of array except selfO(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 enlazadaO(n)O(1)Versión iterativa. La recursión cuesta O(n) de pila.
Pila monótonaO(n) amortizedO(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 KMPO(n + m)O(m)n es el texto; m, el patrón.
Rolling hash de Rabin–KarpO(n + m) avgO(n·m) worstO(1)El peor caso es que el hash de cada ventana colisione.
Algoritmo ZO(n + m)O(n + m)

Heaps y orden

Heaps y orden: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
Top-k con un heap de tamaño kO(n log k)O(k)
Top-k más frecuentes con bucketsO(n)O(n)
K-way mergeO(N log k)O(k)N elementos en total, repartidos entre k listas ordenadas.
Mediana acumulada (dos heaps)O(log n) addO(1) medianO(n)
Fusionar intervalosO(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

Grafos y cuadrículas: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
Camino más corto sin pesos (BFS)O(V + E)O(V)
Flood fill / islas en una cuadrículaO(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–FordO(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 conexosO(V + E)O(V)

Programación dinámica

Programación dinámica: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
Climbing stairs / estilo FibonacciO(n)O(1)Dos variables que se van actualizando, en lugar de la tabla.
House robberO(n)O(1)
Coin change (mínimo de monedas)O(n·A)O(A)n tipos de moneda; A, el monto.
Mochila 0/1O(n·W)O(W)W es la capacidad; una sola fila, que se llena de derecha a izquierda.
Subsecuencia común más largaO(m·n)O(m·n)O(min(m, n)) de espacio si solo se necesita la longitud.
Distancia de ediciónO(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ículaO(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

Recursión y backtracking: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
Fibonacci recursivo ingenuoO(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 subconjuntosO(n·2n)O(n)Sin contar la salida.
Todas las permutacionesO(n·n!)O(n)Sin contar la salida.
N-queensO(n!)O(n)Cota superior; la poda recorta la mayor parte.

Matemáticas y bits

Matemáticas y bits: tiempo y espacio extra
AlgoritmoTiempoEspacioNotas
MCD (Euclides)O(log min(a, b))O(1)
Exponenciación rápidaO(log n)O(1)Elevar al cuadrado de forma iterativa; n es el exponente.
Criba de EratóstenesO(n log log n)O(n)
XOR para encontrar el número únicoO(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 dosO(1)O(1)

bytepatterns.com/cheatsheets/big-o: cada fila enlaza ahí a una lección animada.