¡Hola! Esta página web cubre las complejidades Big-O de espacio y tiempo de algoritmos comunes utilizados en Ciencias de la Computación. En el pasado, cuando me preparaba para las entrevistas técnicas, me pasaba horas rastreando Internet y recopilando las complejidades mejores, medias y peores de los algoritmos de búsqueda y ordenación para no quedarme perplejo cuando me preguntaban por ellos. En los últimos años, he realizado entrevistas en varias startups de Silicon Valley, y también en algunas empresas más grandes, como Google, Facebook, Yahoo, LinkedIn y Uber, y cada vez que me preparaba para una entrevista, pensaba: «¿Por qué alguien no ha creado una bonita hoja de trucos de Big-O?». Así que, para ahorrarles a todos ustedes una tonelada de tiempo, me adelanté y creé una. ¡Que la disfruten! – Eric
Echa un vistazo a El Grapho, una biblioteca de visualización de datos de gráficos que soporta millones de nodos y aristas
Big-O Complexity Chart
Horrible |
Bad |
Fair |
Good |
Excellent |
Operaciones de estructura de datos comunes
| Estructura de datos | Complejidad temporal | Complejidad espacial | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Promedio | Peor | ||||||||
| Acceso | Búsqueda | Inserción | Borrado | Acceso | Búsqueda | Inserción | Borrado | ||
| Matriz | Θ(1) |
Θ(n) |
Θ(n) |
Θ(n) |
O(1) |
O(n)O(n)O(n)O(n) |
O(n) |
||
Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
| Cola | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Singly-Lista enlazada | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Lista doblementeLista enlazada | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Lista de saltos | Θ(log(n))Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n)O(n) |
O(n) |
O(n) |
O(n log(n)) |
||
N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
|
| Árbol de búsqueda binario | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n))Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
|
N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
|
| B-Árbol | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
Rojo-Árbol negro | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
Árbol de juego | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Árbol AVL | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Árbol KD | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
Algoritmos de ordenación de matrices
| Algoritmo | Complejidad temporal | Complejidad espacial | ||
|---|---|---|---|---|
| Mejor | Promedio | Peor | Peor | |
| Clasificación | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(log(n)) |
Mergesort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Timsort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(1) |
Ordenación por burbujas | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Ordenación por inserción | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
|
| Ordenación del árbol | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(n) |
| Ordenación por conchas | Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
Ordenación por cubos | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Ordenación de la matriz | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Ordenación del recuento | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
Cubosort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
Aprende más
- Cómo superar la entrevista de codificación: 150 preguntas de programación y soluciones
- Introducción a los algoritmos, 3ª edición
- Estructuras de datos y algoritmos en Java (2ª edición)
- JavaScript de alto rendimiento (Construya interfaces de aplicaciones web más rápidas)
Obtenga el póster oficial de Big-O Cheat Sheet Poster
Contribuidores
- Eric Rowell
- Quentin Pleple
- Michael Abed
- Nick Dizazzo
- Adam Forsyth
- Felix Zhu
- Jay Engineer
- Josh Davis
- Nodir Turakulov
- Jennifer Hamon
- David Dorfman
- Bart Massey
- Ray Pereda
- Si Pham
- Mike Davis
- mcverry
- Max Hoffmann
- Bahador Saket
- Damon Davison
- Alvin Wan
- Alan Briolat
- Drew Hannay
- Andrew Rasmussen
- Dennis Tsang
- Vinnie Magro
- Adam Arold
- Alejandro Ramírez
- Aneel Nazareth
- Rahul Chowdhury
- Jonathan McElroy
- steven41292
- Brandon Amos
- Joel Friedly
- Casper Van Gheluwe
- Eric Lefevre-.Ardant
- Oleg
- Renfred Harper
- Piper Chester
- Miguel Amigot
- Apurva K
- Matthew Daronco
- Yun-Cheng Lin
- Clay Tyler
- Orhan Can Ozalp
- Ayman Singh
- David Morton
- Aurelien Ooms
- Sebastian Paaske Torholm
- Koushik Krishnan
- Drew Bailey
- Robert Burke
.
Mejora esta página
¡Edita estas tablas!