[Algorithm] 시간 복잡도(Time Complexity)

시간 복잡도(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

2751번: 수 정렬하기 2

---

시간제한이 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으로 유지된다.