시간 복잡도
입력 크기에 따른 알고리즘 실행 시간의 스케일링(Big O).
Time complexity measures how the execution time of an algorithm scales as input size (n) increases. It's expressed using Big O notation, which describes the upper bound (worst-case) growth rate.
Common time complexities:
- O(1) Constant: Same time regardless of input (array index access)
- O(log n) Logarithmic: Halves problem each step (binary search)
- O(n) Linear: Time proportional to input (single loop)
- O(n log n) Linearithmic: Efficient sorting (mergesort, quicksort)
- O(n²) Quadratic: Nested loops (bubble sort)
- O(2ⁿ) Exponential: Doubles each step (naive recursion)
Big O focuses on dominant terms as n→∞, ignoring constants and lower-order terms.
graph LR
Center["시간 복잡도"]:::main
Pre_algorithm["algorithm"]:::pre --> Center
click Pre_algorithm "/terms/algorithm"
Rel_space_complexity["space-complexity"]:::related -.-> Center
click Rel_space_complexity "/terms/space-complexity"
Rel_algorithm["algorithm"]:::related -.-> Center
click Rel_algorithm "/terms/algorithm"
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
분할 상환 분석은 시퀀스에 걸쳐 비용을 평균화합니다. Big-Θ(타이트 바운드), Big-Ω(하한)는 Big-O를 보완합니다. 마스터 정리는 점화식 T(n) = aT(n/b) + f(n)을 해결합니다. 실제 성능은 상수 요인과 캐시 효과로 인해 Big-O와 다를 수 있습니다.