Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.

알고리즘의 성능을 분석할 때 사용하는 세 가지 점근적 표기법으로, 각각 상한, 평균(정확한 경계), 하한을 나타냅니다.

세 가지 표기법 비교

표기이름의미기준
O(f(n))Big-O상한선 (최악)이보다 느릴 수 없다
Ω(f(n))Big-Omega하한선 (최선)이보다 빠를 수 없다
Θ(f(n))Big-Theta상·하한 동시정확한 성능 경계

Big-Theta는 Big-O와 Big-Omega가 동시에 성립 및 같을 때만 가능

직관적 이해

Ω(n)        Θ(n log n)        O(n²)
 ↑                               ↑
최소한 이만큼    정확히 이만큼    많아야 이만큼
걸린다          걸린다           걸린다

예시: 배열에서 값 탐색 (선형 탐색)

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}
표기경우설명
O(n)최악target이 맨 끝 or 없음 → n번 탐색
Ω(1)최선target이 첫 번째 → 1번 탐색
Θ(?)—최선·최악이 달라 Θ로 표현 불가

Θ는 최선과 최악이 동일할 때만 성립합니다.

Θ가 성립하는 예시

// 배열 전체 합산 - 무조건 n번 순회
int sum(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}
// 최선 = 최악 = n번 → Θ(n)

실무에서의 관례

실제 코딩 테스트나 실무에서는 Big-O만 주로 사용합니다.

CSLOG에서 보기