2025-08-27 22:48
Tags: 알고리즘
점근적 표기법(Asymptotic Notation)
- 입력 데이터의 크기(n) 이 무한히 커질때 알고리즘의 성능은 어떤 형태로 증가할지 성장추세에 집중
빅오 표기법 (Big-O Notation): 최악의 경우를 대비하라!
- 알고리즘 성능의 상한(최악의 경우 얼마나 느려질 수 있는가)
- 수학적 정의:
f(n) = O(g(n))이라는 것은,n이 특정 값(n0) 이상일 때f(n) <= c * g(n)을 만족하는 양의 상수c와n0가 존재한다는 의미입니다.
빅오메가 표기법 (Big-Ω Notation): 최소한 이 정도는 보장한다!
- 알고리즘 성능의 하한(최상의 경우에도 최소 어느정도의 연산 수행해야 하는가)
- 수학적 정의:
f(n) = Ω(g(n))이라는 것은,n이 특정 값(n0) 이상일 때f(n) >= c * g(n)을 만족하는 양의 상수c와n0가 존재한다는 의미입니다.
빅세타 표기법 (Big-Θ Notation): 이상과 현실의 일치
- 알고지름 성능의 평균적인 범위, 최상의 경우와 최악의 경우가 동일할 때
- 수학적 정의:
f(n) = Θ(g(n))이라는 것은,f(n) = O(g(n))이면서 동시에f(n) = Ω(g(n))이라는 의미입니다. 즉,c1 * g(n) <= f(n) <= c2 * g(n)을 만족하는 양의 상수c1,c2,n0가 존재합니다.
만약 등호 없는 비교 하고 싶으면 리틀오(o)와 리틀오메가(ω) 표기법도 사용할 수 있다.
일반적인 시간 복잡도 유형
| 빅오 표기법 | 명칭 | 설명 | 예시 |
|---|---|---|---|
| O(1) | 상수 시간 (Constant) | 입력 크기와 상관없이 항상 일정한 시간이 걸림 | 배열의 특정 인덱스 접근, 해시 테이블 삽입/삭제 |
| O(log n) | 로그 시간 (Logarithmic) | 입력 크기가 두 배로 늘어도 연산은 한 번만 추가됨 | 이진 탐색 (Binary Search) |
| O(n) | 선형 시간 (Linear) | 입력 크기에 비례하여 연산 횟수가 증가함 | 배열 순회, 선형 검색 |
| O(n log n) | 로그 선형 시간 (Log-linear) | O(n)과 O(log n)이 결합된 형태로, 효율적인 정렬 알고리즘에서 많이 보임 | 병합 정렬, 퀵 정렬, 힙 정렬 |
| O(n²) | 이차 시간 (Quadratic) | 입력 크기의 제곱에 비례하여 연산 횟수가 증가함 (이중 반복문) | 버블 정렬, 선택 정렬, 삽입 정렬 |
| O(2ⁿ) | 지수 시간 (Exponential) | 입력 크기가 하나 늘어날 때마다 연산 횟수가 두 배씩 증가함 | 재귀를 이용한 피보나치 수열 계산, 조합 탐색 |
| O(n!) | 팩토리얼 시간 (Factorial) | 입력 크기가 하나 늘어날 때마다 연산 횟수가 n배 증가함. 가장 느림 | 외판원 문제(TSP)의 모든 경로 탐색 |