코드의 시간 복잡도 계산하기

점근 표기법

점근 표기법은 시간 복잡도를 근사치로 표현한 것으로, 일반적으로 Big-O 표기법을 사용한다.

코딩 테스트 문제에서 시간제한은 보통 1초에서 5초 사이로, 연산 횟수가 대략 10억 번을 넘어가면 오답 판정을 받을 가능성이 높으며, 메모리 제한은 128MB - 512MB 사이에서 주어지기 때문에 데이터의 개수가 대략 천만을 넘어가지 않도록 설계하는 것이 좋다.

시간 복잡도

시간 복잡도는 연산의 개수 즉, 몇 번의 연산이 수행되는지를 계산하여 로직의 효율을 분석하는 데 사용된다.

제한 시간이 1초인 문제를 기준으로 풀이 가능한 정도

코딩 테스트 환경에서 1초에 최대 1억 정도의 연산을 처리한다고 가정

• N의 범위가 500인 경우 : 시간 복잡도 O(N^3) 이하의 알고리즘으로 설계하면 풀이 가능
• N의 범위가 10,000인 경우 : 시간 복잡도 O(N^2) 이하의 알고리즘으로 설계하면 풀이 가능
• N의 범위가 1,000,000인 경우 : 시간 복잡도 O(N log N) 이하의 알고리즘으로 설계하면 풀이 가능
• N의 범위가 100,000,000인 경우 : 시간 복잡도 O(N) 이하의 알고리즘으로 설계하면 풀이 가능

계산 예시

// 1번만 읽기 때문에 시간 복잡도는 O(1)
if (n > 100) Debug.Log(n);

// 반복문으로 n번의 코드를 읽기 때문에 O(n)
for (int i = 0; i < n; i++) {
    Debug.Log(n);
}

// 위 반복문을 2번 반복한다면 n번의 코드를 2번 읽기 때문에 O(2n)
for (int i = 0; i < 2; i++) {
    for (int i = 0; i < n; i++) {
        Debug.Log(n);
    }
}

// 반복문을 n번 반복한다면 O(n^2)
for (int i = 0; i < n; i++) {
    for (int i = 0; i < n; i++) {
        Debug.Log(n);
    }
}