공간 복잡도
입력 크기에 대한 메모리 사용량(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["공간 복잡도"]:::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;
🧒 5살도 이해할 수 있게 설명
여행을 위해 짐을 싸는 것을 상상해 보세요. 공간 복잡도는 '물건을 더 가져가면 가방이 몇 개 필요할까?'라고 묻는 것과 같습니다. 어떤 방법은 항상 가방 하나만 필요하고(O(1)), 다른 방법은 각 항목마다 가방이 필요합니다(O(n)).
🤓 Expert Deep Dive
꼬리 재귀 최적화는 O(n) 스택 공간을 O(1)로 변환합니다. 공간-시간 트레이드오프는 기본적입니다: 해시 테이블은 O(n) 공간을 O(1) 검색과 교환합니다. 스트리밍 알고리즘은 O(1) 공간에서 데이터를 처리합니다.