Complexidade de espaço
Uso de memória relativo ao tamanho da 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["Complexidade de espaço"]:::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;
🧒 Explique como se eu tivesse 5 anos
Imagine fazer as malas para uma viagem. A complexidade de espaço é como perguntar: 'De quantas malas preciso se levar mais coisas?' Alguns métodos precisam sempre de apenas uma bolsa (O(1)), outros precisam de uma bolsa para cada item (O(n)).
🤓 Expert Deep Dive
A otimização de recursão de cauda converte O(n) de espaço de pilha em O(1). Tradeoffs espaço-tempo são fundamentais: tabelas hash trocam O(n) de espaço por O(1) de busca. Algoritmos de streaming processam dados em O(1) de espaço.