[알고리즘] 시간 복잡도

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 어떤 코딩테스트 문제에서 제한시간을 2초로 주어졌다면, 2억 번의 연산안에 해당 문제를 해결해야 한다는 말이다.

 

시간 복잡도 유형

• 빅-오메가(Ω(n)) : 최선(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(Θ(n)) : 보통(average case)의 연산 횟수를 나타낸 표기법
• 빅오(O(n)) : 최악(worst case)의 연산 횟수를 나타낸 표기법

다음 예시로 0~99 사이의 무작윗값을 찾아 출력한다고 했을때, 

// 0~99 사이 값 무작위 선택
for findNumber = (int)(Math.random() * 100);
for(int i = 0; i < 100; i++){
	System.out.println(i);
    break;
}

만약 찾는 수가 0이라면 한번에 찾을 수있기때문에 최선의 경우로, 빅-오메가 표기법의 시간 복잡도는 1번이다.

절반 안에 숫자를 찾는 경우가 보통의 연산 횟수임으로, 빅-세타 표기법의 시간 복잡도는 N/2번이고,

최악의 경우는 99를 찾게 될 경우로 0~99까지 모든 경우를 확인해봐야한다. 그래서 빅-오 표기법의 시간복잡도는 N번이다.

 

코딩테스트에서는 빅-오 표기법(O(n))을  기준으로 수행 시간을 계산해야한다. 실제 테스트의 다양한 테스트 케이스들 중 모든 케이스를 통과해야 합격이 되기 때문에 최악의 경우를 염두해 둬야 한다.

---

시간 복잡도 활용하기

알고리즘 선택의 기준으로 사용

버블 정렬과 병합 정령의 시간 복잡도는 각각 O(n²), O(nlogn)이라고 우리가 알고 있다고 가정하고 아래의 문제를 봤을때,

수 정렬하기

출처 https://www.acmicpc.net/problem/2750

 

제한 시간 2초

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

예제 입력 1

5

5

2

3

4

1

 

예제 출력 1

1

2

3

4

5

시간 제한이 2초이므로 이 조건을 만족하려면 2억번 이하의 연산 횟수로 문제를 해결해야한다.

따라서 문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 알고리즘을 사용해야 할 것인지를 판단할 수 있다.

 

연산 횟수는 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출할 수 있다.

 

그럼 알고있는 정렬 알고리즘의 적합성을 평가해보면,

• 버블 정렬 = n² = (1,000,000) ² = 1,000,000,000,000 > 200,000,000 → 부적합
• 병합 정렬 = nlogn = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 → 적합

문제에 주어진 시간 제한이 2초이므로 2억 번 안에 원하는 답을 구해야하고, 버블 정렬은 약 10억 번의 연산 횟수가 필요함으로 해당 문제를 풀기에 적합한 알고리즘이 아니다, 반면 병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 문제 풀기에 적합한 알고리즘이라고 판단된다.

 

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드이 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다. 그러려면 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

예시1: 연산횟수 = N

int N = 10000
int cnt = 0;
for(int i = 0; i < N; i++){
	System.out.println("연산 횟수": + cnt++);
}

 

예시2: 연산횟수 = 3N

int N = 10000
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)으로 같다.

 

예시3: 연산 횟수 = N²

int N = 10000
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²로 유지된다.

 

자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다.

---

내용 출처

Do it! 알고리즘 코딩 테스트: 자바 편 | 김종관