Guia de Complejidad

Guía de Complejidad

Esta guía resume el vocabulario mínimo para explicar costos con claridad.

Notación

Notación	Qué describe	Cómo explicarla
Big O	Cota superior	El algoritmo no crece peor que esta función, ignorando constantes
Θ	Cota ajustada	El algoritmo crece al mismo orden por arriba y por abajo
Ω	Cota inferior	El algoritmo necesita al menos este costo en los casos relevantes

Complejidad Amortizada

La complejidad amortizada reparte operaciones costosas sobre muchas operaciones baratas.

Ejemplo:

• Insertar en un Vec suele costar O(1).
• Cuando el arreglo interno crece, una inserción puede costar O(n).
• En una secuencia larga, el costo amortizado por inserción sigue siendo O(1).

Costos Comunes

Patrón	Tiempo típico	Espacio típico
Recorrido lineal	O(n)	O(1)
Hash map de frecuencias	O(n)	O(n)
Sorting	O(n log n)	depende del algoritmo
Binary search	O(log n)	O(1)
DFS/BFS en grafo	O(V + E)	O(V)
Heap push/pop	O(log n)	O(n)
DP 1D	O(n)	O(n) o O(1) comprimido
DP 2D	O(n * m)	O(n * m)
Backtracking	exponencial	profundidad de recursión + resultado

Preguntas de Revisión

1. ¿Qué tamaño controla la entrada principal?
2. ¿Hay ciclos anidados reales o solo ciclos secuenciales?
3. ¿La estructura auxiliar crece con la entrada?
4. ¿La complejidad cambia entre promedio y peor caso?
5. ¿Hay una operación oculta costosa, como sort, clone o búsqueda lineal?

Frases Útiles

• "La cota temporal es O(n) porque cada elemento entra y sale de la ventana a lo sumo una vez."
• "El espacio es O(k) porque el mapa guarda como máximo k claves distintas."
• "La operación es amortizada O(1): algunos crecimientos cuestan más, pero no ocurren en cada inserción."
• "La cota ajustada es Θ(n) porque cualquier solución debe mirar todos los elementos para decidir."