[TIL] 시간복잡도는 if문 개수보다 반복 횟수가 중요한 이유

코딩테스트 문제를 풀다가 약수를 구하는 문제를 접했다.

처음에는 다음과 같은 코드가 더 효율적이라고 생각했다.

for(int i = 1; i <= n; i++) {
    if(n % i == 0) {
        ...
    }
}

반복문 안에 if가 하나밖에 없기 때문이다.

반면, 제곱근을 이용한 풀이를 보면 다음과 같은 구조가 나온다.

for(int i = 1; i <= Math.sqrt(n); i++) {

    if(n % i == 0) {

        if(i != n / i) {

        }
    }
}

반복문 안에 if가 두 개나 들어가 있으니 처음에는 오히려 더 비효율적인 코드가 아닐까 하는 의문이 들었다.

하지만 시간복잡도를 공부하면서 중요한 사실을 알게 되었다.

시간복잡도는 if문의 개수가 아니라 반복문의 횟수가 결정한다

예를 들어 다음 코드를 보자.

for(int i = 1; i <= 1_000_000; i++) {
    if(...)
}

이 코드는 약 100만 번 반복된다.

반면,

for(int i = 1; i <= 1000; i++) {

    if(...)

    if(...)
}

이 코드는 if가 두 개 있지만 실제 검사 횟수는 약 2000번 정도이다.

100만 번 반복하는 것과 2000번 반복하는 것 중 어느 쪽이 더 빠를지는 명확하다.

즉, 대부분의 경우 if 문 자체의 비용은 매우 작고, 성능에 큰 영향을 주는 것은 반복문의 횟수이다.

빅오 표기에서는 상수를 무시한다

예를 들어

for(int i = 1; i <= n; i++) {

    if(...)

    if(...)

    if(...)
}

를 생각해보자.

정확하게 말하면 작업 횟수는 약 3n번이다.

하지만 빅오 표기법에서는 상수를 제거한다.

O(3n)
↓
O(n)

으로 표현한다.

따라서 if가 하나인지 세 개인지는 시간복잡도 관점에서는 큰 차이가 없다.

정말 조심해야 하는 것은 이중 반복문

다음 코드는 다르다.

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {

    }
}

바깥 반복문이 n번,

안쪽 반복문도 n번 실행된다.

즉,

n × n

이 되어

O(n²)

가 된다.

이 경우는 실제로 성능 차이가 매우 크다.

 

정리

처음에는 반복문 안에 if가 많으면 비효율적이라고 생각했다.

하지만 실제로 중요한 것은 if의 개수가 아니라 반복문의 횟수였다.

코딩테스트에서 성능을 개선하고 싶다면 다음 순서로 생각하는 것이 좋다.

 

1. 반복문이 몇 번 실행되는가?
2. 이중 반복문은 없는가?
3. 반복 횟수를 줄일 수 있는 방법은 없는가?