Referencia
Complejidades
Cuánto tarda cada cosa cuando los datos crecen. Es lo que decide si tu programa termina hoy o mañana.
| Estructura | Acceso | Búsqueda | Inserción | Nota |
|---|---|---|---|---|
| Arreglo | O(1) | O(n) | O(n) | Largo fijo, memoria contigua: por eso el índice es O(1) |
| Arreglo ordenado | O(1) | O(log n) | O(n) | Búsqueda binaria |
| Lista ligada | O(n) | O(n) | O(1) | Largo variable, memoria dispersa unida por punteros |
| Stack | — | — | O(1) | LIFO: push y pop en el mismo extremo |
| Cola | — | — | O(1) | FIFO: entra por atrás, sale por delante |
| Tabla de hash | — | O(1) prom. | O(1) prom. | Peor caso O(n) si todo colisiona |
| Heap | O(1) al tope | O(n) | O(log n) | Extraer el máximo o mínimo cuesta O(log n) |
| Algoritmo | Mejor | Promedio | Peor | Memoria | Nota |
|---|---|---|---|---|---|
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Siempre igual, ordenado o no |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Excelente si la entrada viene casi ordenada |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Estable y predecible; paga memoria extra |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place, no estable |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | El peor caso depende del pivote |
| Countingsort | O(n + k) | O(n + k) | O(n + k) | O(k) | Solo enteros en un rango acotado k |
| Radixsort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n + k) | d dígitos, apoyado en un sort estable |
Los comparativos tienen cota inferior Ω(n log n). Counting y radix la esquivan porque no comparan elementos: explotan la estructura de los datos.
| Árbol | Búsqueda | Inserción | Nota |
|---|---|---|---|
| ABB | O(log n) prom. | O(log n) prom. | Peor caso O(n): degenera en lista si la entrada viene ordenada |
| Balanceado | O(log n) | O(log n) | Se rebalancea con rotaciones |
| 2-3 | O(log n) | O(log n) | Nodos con 1 o 2 claves; crece por la raíz |
| B+ | O(log n) | O(log n) | Datos solo en las hojas, enlazadas entre sí. Pensado para disco |
Los recorridos —inorden, preorden, postorden, por niveles— son todos O(n). El inorden de un ABB entrega las claves ordenadas, y esa propiedad aparece en interrogaciones con frecuencia.
| Algoritmo | Complejidad | Para qué |
|---|---|---|
| Matriz de adyacencia | O(V²) memoria | Consultar una arista es O(1); grafos densos |
| Lista de adyacencia | O(V + E) memoria | Recorrer vecinos es eficiente; grafos dispersos |
| BFS | O(V + E) | Explorar por niveles; camino más corto sin pesos |
| DFS | O(V + E) | Explorar en profundidad; base de casi todo lo demás |
| Orden topológico | O(V + E) | Secuenciar tareas en un DAG |
| Componentes f. conexas | O(V + E) | Kosaraju o Tarjan, sobre grafos dirigidos |
| Kruskal | O(E log E) | Árbol de cobertura mínima, con union-find |
| Prim | O(E log V) | Árbol de cobertura mínima, con heap |
| Dijkstra | O((V+E) log V) | Rutas más cortas; pesos no negativos |
| Bellman-Ford | O(V · E) | Rutas más cortas; admite pesos negativos |
| Floyd-Warshall | O(V³) | Rutas más cortas entre todos los pares |
| Técnica | Idea | Señal de que aplica |
|---|---|---|
| Dividir para conquistar | Partir, resolver, combinar | El problema se parte en subproblemas independientes |
| Backtracking | Probar y deshacer al llegar a un callejón | Hay que construir la solución paso a paso con restricciones |
| Programación dinámica | Guardar resultados de subproblemas repetidos | Los subproblemas se solapan y hay subestructura óptima |
| Algoritmos codiciosos | Elegir lo mejor en cada paso, sin volver atrás | La elección local óptima lleva a la global — hay que demostrarlo |
Con los codiciosos, la pregunta de interrogación casi nunca es «escribe el algoritmo»: es «demuestra que funciona» o «da un contraejemplo donde falle».
Material de estudio no oficial · IIC2133 Estructuras de Datos y Algoritmos · PUC · 2026-2.