PS에서의 시간복잡도에 대한 고찰

PS에서 시간복잡도는 매우 중요하다.

 

시간복잡도는 보통 Big O notation으로 나타낸다.

 

그래서 시간복잡도가 무엇인가?

 

PS에서 시간복잡도는 문제를 해결하는 데에 걸리는 시간을 입력 크기를 나타내는 변수(들)로 나타낸 함수이다.

 

하지만 우리가 관심을 가지는 것은 최악의 경우이다.

 

Big O notation의 formal한 정의를 설명하자면

 

만약 모든 실수 \(x>x_0\)에 대하여 \(f(x)\leq cg(x)\)를 만족하는 실수 \(x_0\)와 양의 실수 \(c\)가 존재한다면, \(f(x)\in O(g(x))\)로 표현한다. 정확하게는 \(O(g(x))\)는 함수들의 집합이지만 다음과 같이 많이 나타낸다.

 

\[f(x)=O(g(x))\]

 

다른 표기법도 존재하지만 Big O notation을 거의 대부분의 상황에서 사용하는 이유는 정의를 이해하면 쉽게 납득할 수 있다. \(f(x)\)의 상계를 나타내기 때문이라고 볼 수 있을 것 같다.

 

우리가 흔히 시간복잡도를 Big O notation으로 나타낼 때 가장 영향이 큰 항만 생각하고 상수 곱은 무시해도 된다고 말하는 이유를 정의를 통해서 살펴보자.

 

\(f(x)=3x+17\)이고 \(g(x)=x\)로 두고 정의를 살펴보자.

 

\(c=4\), \(x_0=17\)로 두면, 모든 실수 \(x>x_0\)에 대하여 \(f(x)\leq cg(x)\)이다.

 

즉, 모든 실수 \(x>17\)에 대하여 \(3x+17\leq4x\)이다.

 

따라서 \(3x+17\in O(x)\)로 나타낼 수 있다.

 

그럼 예를 들어서 다음 코드의 시간복잡도를 구해보자.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, sum = 0; cin >> n;
    for (int i = 1; i <= n; i += 2) {
        sum += i;
    }
    cout << sum << '\n';
    return 0;
}

아마 \(T(n)=n/2\)정도 되는 것 같다. 하지만 여기서 더 살펴볼 점이 있다. 1개의 연산의 기준은 무엇인가? 덧셈 연산과 비트 연산 등 연산은 종류와 상황에 따라 실제 수행시간이 다르다. 하지만 Big O notation으로 나타낸다면 \(T(n)=O(n)\)이라고 쉽게 적을 수 있을 것이다.

 

Big O notation은 \(x\)가 한없이 커질때 매우 유용한 표기법이다.

 

그런데 모든 PS 문제는 물론 실생활 문제에서도 입력의 크기가 한없이 크지는 않다.

 

실제로 \(n^2/64\)가 정해인 문제들도 존재한다.

 

어떤 문제에 대해 정확한 답을 내는 두개의 소스 코드가 존재한다고 해보자.

 

1번 소스코드의 시간복잡도는 \(O(n^2)\)이고, 2번 소스코드의 시간복잡도는 \(O(n\log n)\)이다.

 

2번 소스코드의 실행 시간이 1번 소스코드보다 빠르다고 보장할 수 있는가?

 

그렇지 않다.

 

어떤 풀이가 더 훌륭한 풀이인가?

 

아마도 2번 소스코드일 것 같다.

 

많은 사람들은 문제를 풀때 시간복잡도를 Big O notation으로 나타내라고 한다. 동시에 1초에 1억번 정도의 연산을 할 수 있다고 한다.

 

무언가 모순이 느껴지지 않는가?

 

오늘의 결론

 

Big O notation으로 나타내는 것이 중요하지만, 그것이 전부는 아니다.