Big O

개념

Big-O 표기법(Big-O Notation)은 알고리즘의 시간복잡도를 표현하는 방법으로 입력 크기 $N$이 증가할 때 연산 횟수가 어떻게 증가하는지를 나타내는 표기법이며 코딩 테스트에서는 보통 최악의 경우(Worst Case) 를 기준으로 알고리즘의 성능을 분석합니다.

Big-O 표기법은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라 입력 크기가 커질수록 연산량이 얼마나 빠르게 증가하는지를 표현합니다.

대표적인 Big-O 순서

시간복잡도는 일반적으로 다음과 같은 순서로 증가합니다.

$$ O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(2^N) $$

왼쪽에 가까울수록 효율적인 알고리즘이며 오른쪽으로 갈수록 연산량이 빠르게 증가합니다.

Big-O 특징

Big-O 표기법은 다음과 같은 규칙을 따릅니다.

상수는 무시

$$ O(2N) = O(N) $$

상수 배수는 알고리즘의 성장률에 큰 영향을 주지 않기 때문에 제거합니다.

낮은 차수는 무시

$$ O(N^2 + N + 1) = O(N^2) $$

입력 크기 $N$이 충분히 커지면 가장 높은 차수의 항이 지배적인 영향을 미칩니다.

계수는 무시

$$ O(100N) = O(N) $$

상수 계수는 제거하고 성장률만 표현합니다.

예시

$O(N + N)$

Java

for(int i = 0; i < n; i++){
    System.out.println(i);
}

for(int i = 0; i < n; i++){
    System.out.println(i);
}

Python

for i in range(n):
    print(i)

for i in range(n):
    print(i)

JavaScript

for(let i = 0; i < n; i++){
    console.log(i);
}

for(let i = 0; i < n; i++){
    console.log(i);
}

시간복잡도는 $O(N + N)$ 이며 Big-O 표기법에서는 $O(N)$ 으로 표현합니다.

$O(N^2 + N)$

Java

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        System.out.println(i + " " + j);
    }
}

for(int i = 0; i < n; i++){
    System.out.println(i);
}

Python

for i in range(n):
    for j in range(n):
        print(i, j)

for i in range(n):
    print(i)

JavaScript

for(let i = 0; i < n; i++){
    for(let j = 0; j < n; j++){
        console.log(i, j);
    }
}

for(let i = 0; i < n; i++){
    console.log(i);
}

이 경우 첫 번째 반복문은 $N^2$번 실행되고 두 번째 반복문은 $N$번 실행되므로 시간복잡도는 $O(N^2 + N)$ 이며 Big-O 표기법에서는 $O(N^2 + N) = O(N^2)$으로 표현합니다.