시간복잡도

시간복잡도는 어떤 알고리즘의 성능을 예측하는데 사용되는 중요한 지표입니다. 예를 들어 아래의 코드를 봅시다.

int n;
cin >> n;

for (int i = 0; i < n; i++) {
    // ...
}

이 코드는 몇 번 실행될까요? 당연히 \( n \)번 입니다. 이 코드의 시간복잡도를 \( O(n) \)이라고 합니다. 이렇게 대문자 O를 써서 시간복잡도를 나타내는 것을 Big-O 표기법 이라고 합니다. 대략적으로 이 코드가 입력의 크기에 얼마나 영향을 받는지를 나타냅니다.

그렇다면 아래 코드의 시간복잡도는 얼마일까요?

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        // ...
    }
}

\( n \)에 따른 반복 횟수를 계산해봅시다. \( i \)가 0이면 \( j \)는 1부터 \( n-1 \)까지, \( i \)가 1이면 \( j \)는 2부터 \( n-1 \)까지 반복됩니다. 계산을 편하게 하기 위해 뒤에서부터 생각해보면 \( 0 + 1 + \cdots +(n-1) \)인 것을 알 수 있습니다. 따라서 이것을 정리하면

그럼 이때의 시간복잡도는 \( O\left(\frac{n(n-1)}{2}\right) \)인 걸까요? 정답은 아닙니다. 시간복잡도의 목적은 입력에 따른 반복 횟수의 대략적인 추세를 보고 싶은 것이지 정확한 반복 횟수를 구하고 싶은 것이 아닙니다. 그리고 정확히 반복 횟수를 구할 수 없는 경우가 더 많기도 하고요. 따라서 시간복잡도는 영향이 가장 큰 항만을 상수까지 모두 제거해서 나타냅니다. 위 경우 시간복잡도는 \( O(n^2) \)이 되겠네요.

이제 시간복잡도를 Big-O 표기법으로 표시할 수 있게 되었습니다. 그럼 이걸 어떻게 활용하는지 알아봅시다. 백준이던 앳코더건 코드포스건 모든 문제에는 시간 제한과 메모리 제한이 있습니다. 너무 많은 시간이나 리소스를 사용하는 알고리즘은 당연히 정답을 받지 못합니다. C++ 기준으로 1억번 반복을 1초로 생각할 수 있습니다. 파이썬은 C++보다 실행 속도가 느리지만 보통 언어의 실행 속도에 맞춰 추가 시간을 주기 때문에 마찬가지로 1억번을 1초라고 생각하면 됩니다. 그럼 시간제한이 1초인 문제에 시간복잡도가 \( O(n^2), \,\,\,\, 0 \leq n \leq 10^6 \)인 알고리즘을 만들었다고 해 봅시다. 최악의 경우 \( 10^{12} \)번 반복을 돌게 될 것이고 \( 10^8 \)이 1초라고 했으니 \( 10^4 \)초가 걸릴 것으로 예상할 수 있습니다. 이런 경우 TLE(Time Limit Excessed, 시간초과)를 받게 됩니다. 따라서 시간복잡도를 이용해 어떤 알고리즘이 제한시간 안에 돌아갈지 예상해 볼 수 있습니다. 애초에 돌아가지 않을 알고리즘을 짜서 시간 초과를 받는 불필요한 노동을 막아주었네요. 이제 어떻게 하면 시간복잡도를 줄일 수 있을지 생각해봐야 합니다. 기발한 아이디어가 떠올라서 시간복잡도가 \( O(n \log n) \)이 되었습니다! 이 알고리즘은 최악의 경우 \( 6 \times 10^6 \)번 반복하니 \( 60 \)ms 정도에 돌 것이라고 예상할 수 있습니다. 물론 정확한 것은 아니지만 시간 제한과 엄청나게 차이가 나기 때문에 걱정 없이 코드를 만들러 갈 수 있겠네요.

참고로 시간복잡도에 사용되는 로그는 많은 경우 밑이 2입니다. 하지만 밑에 상관 없이 \( \ln x / \ln a \)형태로 변형하고 \( \ln a \)는 상수이므로 생략해버릴 수 있으니 로그의 밑에 대해 자세히 집착할 필요 없습니다. 그저 편한 아무 값으로나 생각해도 괜찮습니다.

아래는 자주 사용되는 시간복잡도의 예시를 정리해본 것입니다.

• \( O(n), O(n + m), O(n^2) \)
• \( O(n \log n), O(m \log n) \)
• \( O(2^n) \)
• \( O(1) \)