Complejidad espacial
Uso de memoria relativo al tamaño de entrada (Big O).
Space complexity describes how an algorithm's memory usage grows with input size (n). Like time complexity, it uses Big O notation.
Space complexity = Input space + Auxiliary space
- Input space: Memory for the input itself
- Auxiliary space: Extra memory used during execution
Common space complexities:
- O(1) Constant: Fixed extra memory (in-place algorithms)
- O(n) Linear: Memory proportional to input
- O(log n) Logarithmic: Recursion depth in binary search
- O(n²) Quadratic: 2D matrix storage
graph LR
Center["Complejidad espacial"]:::main
Pre_algorithm["algorithm"]:::pre --> Center
click Pre_algorithm "/terms/algorithm"
Rel_time_complexity["time-complexity"]:::related -.-> Center
click Rel_time_complexity "/terms/time-complexity"
Rel_asymptotic_notations["asymptotic-notations"]:::related -.-> Center
click Rel_asymptotic_notations "/terms/asymptotic-notations"
Rel_big_o_notation["big-o-notation"]:::related -.-> Center
click Rel_big_o_notation "/terms/big-o-notation"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 Explícalo como si tuviera 5 años
Imagina que haces las maletas para un viaje. La complejidad espacial es como preguntar: '¿Cuántas maletas necesito si llevo más cosas?' Algunos métodos siempre necesitan solo una bolsa (O(1)), otros necesitan una bolsa para cada artículo (O(n)).
🤓 Expert Deep Dive
La optimización de recursión de cola convierte O(n) espacio de pila a O(1). Los compromisos espacio-tiempo son fundamentales: las tablas hash intercambian O(n) espacio por O(1) búsqueda. Los algoritmos de streaming procesan datos en O(1) espacio.