목차
이 글과 연관된 글
- 시간 복잡도 기본 (Time Complexity Basic) - Part 1
- 시간 복잡도 기본 (Time Complexity Basic) - Part 2
- 시간 복잡도 기본 (Time Complexity Basic) - Part 3
시간 복잡도로 실행 시간 예측하기
시간 복잡도를 계산했다면, 실행 시간을 예측할 수 있습니다.
Part 3에서 나왔던 코드를 예시로 들어보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
int main() {
int n, sum = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
sum += i;
}
printf("sum = %d", sum);
return 0;
}
이 코드의 시간 복잡도는 \(\Theta(n)\) 입니다. 그리고 이 문제에서 n을 최대 \(10^9\) 까지 입력할 수 있다고 가정해 보겠습니다.
시간 복잡도에서 최대 실행 시간을 예측하기 위해서 가장 먼저 해야 할 일은, 시간이 가장 오래 걸릴 것 같은 입력을 찾는 것입니다.
이 문제에서는 시간이 가장 오래 걸리는 입력이 \(10^9\) 임을 자명하게 알 수 있습니다.
따라서 시간 복잡도에 \(10^9\) 을 대입하면 그대로 \(10^9\)이 나옵니다.
시간 복잡도 변수에 대입해서 나온 수치를 실행 시간으로 바꾸는 공식은 다음과 같습니다.
실행 시간 (Sec) = 시간 복잡도 변수에 값을 대입해서 나온 수치 / \(10^8\)
이 공식은 현재(2023.02.26) 존재하는 Online Judge 시스템의 컴퓨터 성능을 기준으로 일반화 한 공식입니다.
따라서 사용에 유의해야 합니다.
즉 계산한 결과를 1억을 기준으로 초로 환산하면 됩니다.
따라서 위 코드의 실행 시간은 10초라고 예상할 수 있습니다.
하지만, 컴퓨터의 성능과 시간 복잡도에는 표현되어 있지 않은 상수 시간 때문에 정확히 10초 동안 동작하지는 않습니다.
더 빨라질 수도, 더 느려질 수도 있습니다.
또 컴파일러 최적화에 의해 시간 복잡도가 예상했던 것보다 작아질 수 있습니다.
따라서 예측의 정확도를 높이려면 컴퓨터의 성능과 숨겨진 상수를 고려해야 합니다.
이 부분은 해당 글에서 다루지는 않습니다.
실제로 위 코드를 실행했을 때 10초보다 훨씬 빠르게 동작함을 확인할 수 있습니다.
그 이유는 C/C++의 경우 컴파일러 최적화도 존재하고, 다른 알고리즘에 비해 숨겨진 상수가 매우 작은 편이기 때문입니다.
시간 복잡도를 계산할 때, 보통 숨겨진 상수를 고려하지 않습니다. 그리고 시간 복잡도는 간단한 문제를 풀 때 사용하기보다 복잡한 문제를 풀 때 사용하기 때문에 보통 숨겨진 상수가 적당히 크다고 가정하고 만들어진 공식이기 때문입니다. 따라서 간단한 형태인 경우 예상했던 시간보다 빨라지게 됩니다.
따라서 시간 복잡도로 정확한 실행 시간을 구할 수는 없지만, 어느 정도 시간이 필요한 지는 예측할 수 있게 됩니다.
만약 위 문제에서 n을 최대 \(10^{18}\) 까지 입력할 수 있다고 가정한다면, 위 코드의 실행 시간이 \(10^{10}\)초 정도 걸릴 것으로 예상할 수 있습니다.
따라서, 예측했던 것보다 실제 실행 시간이 조금 빨라진다고 하더라도 시간이 많이 필요함을 알 수 있고, 해당 알고리즘으로는 문제를 해결할 수 없다는 사실을 코드 작성 및 실행하지 않고도 알 수 있습니다.