시간복잡도 - 시간 복잡도 유형(빅오메가, 빅세타, 빅오), 시간 복잡도 도출 기준

시간복잡도

알고리즘에서 시간복잡도란 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

보통 1억번의 연산을 1초로 간주하여 예측한다.

 

 

 

시간 복잡도 유형

빅-오메가 : 최선일 때 연산 횟수를 나타낸 표기법

빅-세타 : 보통일 때 연산 횟수를 나타낸 표기법

빅-오 : 최악일 때 연산 횟수를 나타낸 표기법

 

이 중 코딩 테스트에서는 빅-오 표기법을 염두에 두고 풀어야 한다.

다양한 테스트 케이스를 수행해야 하므로 최악의 상황을 고려해야 한다.

 

빅-오 표기법의 시간 복잡도는 다음과 같다.

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)

출처 하루코딩

 

 

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외함.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨.

 

for(int i = 0; i < 100000; i++) {
	System.out.println(i);
}
for(int i = 0; i < 100000; i++) {
	System.out.println(i);
}
for(int i = 0; i < 100000; i++) {
	System.out.println(i);
}

위 코드의 시간복잡도는 O(n)이 된다.

한 포문의 연산횟수는 n번이므로 총 3n번이 되지만

시간 복잡도 도출 기준 중 상수는 무시한다는 기준에 따라 시간복잡도는 그냥 O(n)이 된다.

상수를 무시하는 이유는 상수는 너무나도 작은 수이기 때문에 큰 영향을 끼치지 않아 무시해도 된다.

 

 

 

for(int i = 0; i < 100000; i++) {
    for(int j = 0; j < 1000000; j++) {
    	System.out.println(i);
    }
}

위 코드는 중첩 포문을 사용했기 때문에 O(n^2)의 시간복잡도를 갖는다.

아래에 일반 for문이 여러개가 더 있더라도

시간 복잡도 기준 중 가장 많이 중첩된 반복문을 기준으로 도출한다는 기준에 따라

위 코드의 시간 복잡도는 변함없이 O(n^2)이 된다.

 

일반 포문이 몇개가 더 있든 이중 포문에 비해선 턱없이 작다.

그동안은 생각없이 이중 포문을 막 썼는데

앞으로 코드 짤때는 시간복잡도를 고려해서 작성해야겠다는 생각이 들었다.