안녕하세요 오늘으 알고리즘 문제를 풀다보면 꼭 알아야하는 시간복잡도에 대하여 알아보겠습니다
✔ 실제 시간 복잡도를 정의하는 3가지 유형이 있습니다
💡 시간 복잡도 유형
- 빅-오메가(Big-Ω) = 최선일 때 연산 횟수
- 빅-세타(Big-θ) = 보통일 때 연산 횟수
- 빅-오(Big-O) = 최악일 때 연산 횟수
public class Ex {
public static void main(String[] args) {
//1~100사이의 랜덤값 선택
int randomNum = (int)(Math.random()*100);
for (int i = 0; i <100 ; i++) {
if(i==randomNum) {
System.out.println(i);
System.out.println(randomNum);
break;
}
}
}
}위 코드를 보면 시간 복잡도 유형을 이해하기 쉬울 수 있습니다.
- 빅 오메가는 최선이기 때문에 randomNum이 0 일때 for문에서 1번에 찾아짐
- 빅 세타는 보통이기 때문에 100/2 ⇒ 50번을 for문을 돌렸을 때 나온다
- 빅 오는 최악이기 때문에 for문 100번 돌렸을 때 마지막에 답이 찾아질 때 이다.
우리는 코딩테스트를 준비할 때 빅 오 를 기준으로 잡고 풀어야 합니다.
왜냐하면 문제를 접근하고 풀이할때 항상 최악의 상황을 염두해둬야 하기 때문입니다.
실제 코딩테스트에서는 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야 합격하기 때문입니다.
각각의 시간복잡도는 데이터 크기(n)의 증가에 따라 성능(수행시간)이 다르다는 것을 그래프를 통해 확인할 수 있습니다.
Ex) 시간복잡도 활용하기
1) 수 정렬하기
N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오
(제한시간 2초)
2) 입력
1번째 줄에 수의 개수 N(1< N 1,000,000) 번째 줄부터는 N개의 줄에 숫자가 있다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
- 조건
- 제한시간 2초 → 2억번 이하의 연산 횟수로 문제를 해결해야 한다.
- 연산 횟수 계산 방법
- 알고리즘 시간복잡도 * 데이터의 크기
위 공식을 사용하여 내가 사용한 알고리즘이 문제에 적합한지 판단해보자
→ 버블 정렬 ⇒ 1,000,000^2 > 1,000,000,000,000 > 200,000,000(부적합)
→ 병합 정렬 ⇒ 1,000,000log(1,000,000) = 2,000,000 (적합)
이런 식으로 각 알고리즘의 시간복잡도 공식을 대입해보면 알 수 있습니다.
시간복잡도를 바탕으로 코드 로직 작성하기
- 상수는 시간복잡도 계산에서 제외한다 ( 2O(n) -> O(n)) 과 동일
- 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준이 된다.
- 연산 횟수가 N인 경우
package 알고리즘;
public class Ex {
public static void main(String[] args) {
int N = 1000000;
int cnt = 0;
for (int i = 0; i <N ; i++) {
System.out.println("연산 횟수 : " + cnt++);
}
}
}
연산횟수 N(1,000,000)
- 연산 횟수가 3N인 경우
package 알고리즘;
public class Ex {
public static void main(String[] args) {
int N = 1000000;
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,000,000)번 이다 그렇다면 3N 이지만
상수는 제외하기 때문에 그냥 연산 횟수는 N 으로 처리한다.
결국 시간복잡도 빅 오는 ⇒ O(n)으로 다 똑같이 처리한다.
알고리즘 공부를 꾸준히 하면서 더 많은 내용을 추가하고 작성하겠습니다.
[23.12.24 수정 전]
ref : Do it 알고리즘 코딩테스트 자바