시간 복잡도(Time Complexity)
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
시간 복잡도 유형
- 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
- 빅-세타(θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
- 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
코팅 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?
코팅 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다.
실제 테스트에서는 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.
다음은 빅-오 표기법(O(n))으로 표현한 시간 복잡도 그래프이다. 각각의 시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다는 것을 확인할 수 있다.
시간 복잡도가 빠른 순 : O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!)
시간 복잡도 활용
알고리즘 선택의 기준으로 사용하기
- 버블 정렬의 시간 복잡도 : O(n2)
- 병합 정렬의 시간 복잡도 : O(nlogn)
→ 알고 있다는 전제 하에 아래문제를 풀어보자
https://www.acmicpc.net/problem/2751
시간제한이 2초이므로 이 조건을 만족하려면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다. 따라서 문제에서 주어진 시간제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지를 판단할 수 있다.
👉 연산 횟수는 1초에 1억 번 연산하는 것을 기준으로 생각한다.
👉 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 한다.
✅ 연산 횟수 계산 방법
알고리즘 시간 복잡도 N값에 데이터의 최대 크기를 대입
위 공식을 대입해 각 알고리즘이 이 문제에 적합한지 판단해보자.
버블 정렬 (O(n^2)) = (1,000,000)^2 = 1,000,000,000,000 > 200,000,000 → 부적합 알고리즘
병합 정렬 (O(nlogn)) = 1,000,000log2(1,000,000) = 약 20,000,000 < 200,000,000 → 적합 알고리즘
병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 문제를 풀기에 적합한 알고리즘이다.
시간 복잡도를 바탕으로 코드 로직 개선하기
코드의 시간 복잡도를 도출할 수 있으면 코드 로직 개선 가능하다.
✅ 시간 복잡도 도출 기준
① 상수는 시간 복잡도 계산에서 제외한다.
② 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
코드를 예로 들어 시간 복잡도 도출 기준에 대해 살펴보자.
//연산 횟수가 N인 경우
public class 시간복잡도_판별원리1 {
public static void main(String[] args) {
int N = 100000;
int cnt = 0;
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수: " + cnt++);
}
}
}
//연산 횟수가 3N인 경우
public class 시간복잡도_판별원리2 {
public static void main(String[] args) {
int N = 100000;
int cnt = 0;
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수: " + cnt++);
}
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수: " + cnt++);
}
for (int i = 0; i < N; i++) {
System.out.println("연산 횟수: " + cnt++);
}
}
}
두 예제 코드의 연산 횟수는 3배 차이나지만, 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다.
다음 예제 코드도 확인해보자.
//연산 횟수가 N^2인 경우
public class 시간복잡도_판별원리3 {
public static void main(String[] args) {
int N = 100000;
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println("연산 횟수: " + cnt++);
}
}
}
}
시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for 문이 전체 코드의 시간 복잡도 기준이 된다. 만약 일반 for 문이 10개 더 있다 하더라도 도출 원리의 기준 ②에 따라 시간 복잡도의 변화 없이 N^2으로 유지된다.