1. 시간 복잡도 정의하기
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
시간 복잡도 유형
1. 빅-오메가 Ω(n) : 최선일 때의 연산 횟수를 나타낸 표기법
2. 빅-세타 θ(n) : 보통일 때의 연산 횟수를 나타낸 표기법
3. 빅-오 O(n) : 최악일 때의 연산 횟수를 나타낸 표기법
ex) 만약 1~100 사이의 숫자에서 무작위로 정한 하나의 숫자를 찾는 코드를 작성한다고 할 때 유형에 따른 시간 복잡도는 아래와 같다.
빅-오메가 표기법의 시간 복잡도는 1번
빅-세타 표기법의 시간 복잡도는 N/2 이므로 50번
빅-오 표기법의 시간 복잡도는 N 이므로 100번
2. 코딩 테스트에서 사용하는 시간 복잡도 유형
코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. 다양한 테스트 케이스를 수행하여 모든 케이스를 통과해야만 합격으로 판단하기 때문에 최악일 때를 염두해야 한다.
ex) N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오. - 시간 제한 2초, 1 <= N <= 1,000,000
정렬 부분의 학습을 완료하여 버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n^2), O(nlogn) 임을 알고 있다고 가정했을 때
알고리즘 적합성 평가
- 버블 정렬 = (1000000)^2 = 1000,000000000 > 200000000 -> 부적합 알고리즘
- 병합 정렬 = 1000000 * log(1000000) = 약 20000000 < 200000000 -> 적합 알고리즘
버블 정렬은 약 10억 번의 연산 횟수가 필요하므로 이 문제를 풀기에 적합한 알고리즘이 아니라고 판단할 수 있다. 병합 정렬은 약 2000만 번의 연산 횟수로 답을 구할 수 있으므로 문제를 풀기에 적합한 알고리즘이라고 판단할 수 있다.
이와 같이 시간 복잡도 분석으로 사용할 수 있는 알고리즘을 선택할 수 있고 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다.
3. 시간 복잡도를 바탕으로 코드 로직 개선하기
시간 복잡도 도출 기준
1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
i )
public class 시간복잡도_원리1 {
public static void main(String[] args) {
int N = 10000;
int cnt = 0;
for (int i=0; i<N; i++){
System.out.println("연산 횟수: "+ cnt++);
}
}
}public class 시간복잡도_원리2 {
public static void main(String[] args) {
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) 이다.
ii )
public class 시간복잡도_원리3 {
public static void main(String[] args) {
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 (int j=0; j<N; j++){
System.out.println("연산 횟수: "+ cnt++);
}
for (int j=0; j<N; j++){
System.out.println("연산 횟수: "+ cnt++);
}
}
}
}시간복잡도_원리3 클래스 내에는 for문안에 3개의 for문이 있지만 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드의 시간 복잡도는 O(n^2) 이다.
