시간복잡도 계산
시간복잡도
코딩테스트에 나오는 문제는 항상 시간 제한과 메모리 제한이 존재한다.
이 중 시간 제한을 만족시키기 위해서는 시간복잡도라는 개념을 알아야 한다.
시간복잡도란 입력값과 연산 수행 시간의 상관 관계를 나타내는 척도이다.
알고리즘 문제에서 시간이라는 것은 사용자가 작성한 코드 외에도 너무나 많은 요소에 영향을 받는다.
따라서 절대적인 시간을 측정하기보다 주요 로직의 반복 횟수를 통해 대략적인 시간을 예측할 수 있어야 한다.
아래는 예시코드이다.
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
for (int i = 0; i < 10; i++) { //10번 반복
for (int j = 0; j < n; j++) { // n번 반복
for (int k = 0; k < n; k++) { // n번 반복
cout << "hello world" << '\n'; // 1
}
}
}
for (int i = 0; i < n; i++) { // n번 반복
cout << "i" << '\n';
}
return 0;
}
얼마나 반복되는지를 통해서 시간복잡도를 계산할 수 있다.
반복문이 위와 같이 단순히 중첩되면 곱하고, 나열되어 있으면 더하면 된다.
따라서 예시 코드의 시간복잡도는 $10n^2 + n$ 이 된다.
🔎 빅오 표기법(Big-O notation)
빅오 표기법이란 복잡도에 가장 영향을 많이 끼치는 항만을 계수를 떼어내고 나타내는 표기법이다.
위의 예시 코드처럼 시간복잡도가 $10n^2 + n$ 이라면
빅오 표기법으로는 가장 영향을 많이 끼치는 항만을($10n^2$) 계수를 떼어내고($n^2$) 나타내 $O(n^2)$ 으로 표기된다.
영향을 가장 많이 끼치는 정도는 아래의 Big-O 복잡도 차트를 이용해 구분할 수 있다.
차트에 따라 $n!$ > $2^n$ > $n^2$ > $n\log{n}$ > $n$ > $\log{n}$ > $1$ 순서로 영향이 큰 항만을 계수 없이 표기하면 된다.
(여기서 $\log{n}$은 보통 $\log_{2}{n}$를 뜻한다.)
코딩테스트 문제에서 빅오표기법을 통해 시간 제한을 맞추기 위해서는 위의 순서를 외우는 것이 필수적이다.
$3^n$, $4^n$, $5^n$, …, $n^3$, $n^4$, $n^5$, … 과 같은 알고리즘은 사실상 마주하기가 힘들기 때문에 위의 차트에서 고려되지 않는다.
입력값이 여러 개인 경우
시간복잡도 및 빅오 표기법을 처음 접하면 이러한 의문점이 생긴다.
‘대부분 예시에서는 n을 이용해서 표기하던데 입력값이 여러 개인 경우에는 어떻게 표시할까?’
아래의 예시와 같은 경우이다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
cin >> n, m;
for (int i = 0; i < 7; i++) { // 7번 반복
for (int j = 0; j < n; j++) { // n번 반복
for (int k = 0; k < n; k++) { // n번 반복
cout << "ReturnRudi" << '\n'; // 1
}
}
}
for (int i = 0; i < m; i++) { // m번 반복
cout << "ReturnRudi" << '\n'; // 1
}
return 0;
}
이러한 부분이 헷갈린다면 시간복잡도의 개념을 다시 한 번 생각해보면 된다.
시간복잡도란 입력값과 연산 수행 시간의 상관 관계를 구하는 것이고
이를 통해서 대략적인 처리 시간을 계산하는 것에 목적이 있다.
따라서 위의 예시의 n과 m 은 시간적인 측면에서 상수가 아닌 변수가 된다.
즉 단순히 시간복잡도를 $7n^2 + m$과 같이 표시하면 되고
빅오 표기법으로 표기하면 $O(n^2 + m)$이 된다.
각 요소의 예시
일반적으로 잘 알려진 각 요소들의 예시는 아래와 같다.
$O(1)$: 입력(cin, scanf), 출력(cout, printf), 연산( $+, -, *,$ /, %, … )
간단한 비교 if문( if( a == 1 ) ), 배열의 인덱스 참조( a[1] = 3; )등 …
$O(\log{n})$: 이진트리, …
$O(n)$: for문(반복문), 정렬되지 않은 배열에서 특정 값 검색…
$O(n\log{n})$: 퀵 정렬, 병합 정렬, 힙 정렬, …
$O(n^2)$: 중첩 for문(반복문), 삽입 정렬, 버블 정렬, 선택 정렬, …
$O(2^n)$: 피보나치 수열, …
$O(n!)$: 완전 탐색, …
🔎 시간복잡도 문제 적용
위의 정보를 바탕으로 시간복잡도를 코딩테스트 문제에 적용해보자.
대부분의 알고리즘 문제는 시간 제한을 ‘$n$ 초’ 와 같이 제시해준다.
알고리즘 문제에서 시간이 많은 요소에 영향을 받는다고는 하지만 보통 대략적으로 1초에 1억줄의 코드를 처리할 수 있다.
이를 바탕으로 빅오표기법을 통해 대략적인 최대 입력 크기를 계산할 수 있다.
$O(n)$: 약 1억
$O(n^2)$: 약 1만 ( $10,000^2 = 100,000,000$ )
$O(n^3)$: 약 500 ( $500^3 = 125,000,000$ )
$O(2^n)$: 약 20 ( $2^20 = 1,048,576$ )
$O(n!)$: 약 10 ( $10! = 3,628,800$)
이와 같이 보통 외우기 쉽게 단위가 떨어지게 계산해두고 적용한다.
예를 들어 문제의 시간 제한이 1초 일 때
입력값인 n의 크기가 0 ~ 10,000으로 제시되어있다면
$O(n^2)$ 보다 큰 시간복잡도 풀이는 고려하지 않아야 한다.
또한 $O(2^n)$, $O(n!)$의 경우 숫자가 커지는 속도가 너무 빠르므로
$2^{26} = 67,108,864$ 이나 $11! = 39,916,800$ 와 같이 1억으로부터 여유가 있어도
위의 기준을 이미 초과했다면 다른 풀이를 생각해보는 것이 좋다.
시간복잡도를 계산할 때는 정석대로 한다면 입력크기 n에 대한 점화식을 완성해야 한다.
하지만 너무 복잡한 경우가 아니라면 cnt 변수를 이용해서 시간복잡도 식을 유추하는 것이 빠르다.
ex) cnt는 함수가 호출될 때마다 ++
n = 1 → cnt = 1 → 1
n = 2 → cnt = 3 → 1 + 2
n = 3 → cnt = 7 → 1 + 2 + 4
n = 4 → cnt = 15 → 1 + 2 + 4 + 8
n은 등비수열의 합이구나! 유추
아래는 자주나오는 등차수열과 등비수열의 합을 구하는 공식이다.
등차수열의 합(첫째항이 a, 공차가 d인 경우)
$S_n = \frac{n \{2 a + (n-1)d \} }{2}$
등비수열의 합(첫째항이 a, 공차가 r인 경우)
$S_n = \frac{a(r^n - 1)}{r-1}$
댓글남기기