시간 복잡도 (Time Complexity)

시간 복잡도 (Time Complexity)

알고리즘이 실행되는 데 필요한 시간을 입력 크기(n)의 함수로 표현한 것으로, Big-O 표기법으로 최악 케이스의 증가율을 나타냄

목적: 알고리즘 효율성 분석, 성능 비교, 확장성 예측

특징: 입력 크기 함수, 최악 케이스, 상수 무시, 최고차항만

Big-O 표기법: 점근적 상한, 최악 케이스, O(f(n)) - n이 커질 때 f(n)에 비례

표기법

• •Big-O(O): 상한(최악), 일반적 사용
• •Big-Omega(Ω): 하한(최선)
• •Big-Theta(Θ): 상한=하한(점근적 밀착 한계, Tight Bound)

복잡도 순서: O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

주요 복잡도

• •O(1): 상수, 해시 테이블 접근, 배열 인덱스
• •O(log n): 로그, 이진 탐색, 균형 트리
• •O(n): 선형, 순차 탐색, 배열 순회
• •O(n log n): 선형로그, 병합 정렬, 힙 정렬, 퀵 정렬(평균)
• •O(n²): 제곱, 버블 정렬, 삽입 정렬, 선택 정렬
• •O(2ⁿ): 지수, 피보나치(재귀), 부분집합
• •O(n!): 팩토리얼, 순열, 외판원(브루트 포스)

최선·평균·최악: 퀵 정렬 - 최선 O(n log n), 평균 O(n log n), 최악 O(n²)

장점: 성능 예측, 알고리즘 비교, 확장성 평가

단점: 상수 무시, 작은 입력에서 부정확, 실제 성능과 차이

적용사례: 알고리즘 선택, 성능 최적화, 확장성 설계

연관: Big-O, 공간 복잡도, 알고리즘 분석, 점근 표기법