시간 복잡도와 표기법

시간 복잡도

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

일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.

시간 복잡도 정의하기

• 빅-오메가 : 최선일 때(Best case)의 연산 횟수를 나타낸 표기법
• 빅-세타 : 보통일 때(Average case)의 연산 횟수를 나타낸 표기법
• 빅-오 : 최악일 때(Worst case)의 연산 횟수를 나타낸 표기법

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 하나?

빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.

시간 복잡도 계산

아래의 코드는 연산 횟수에서 큰 차이를 보이는 것 같지만 코딩 테스트에서 상수는 무시하기 때문에 시간 복잡도는 두 경우 모두 O(n)으로 같다.

// 연산 횟수 N
for (int i = 0; i < 100; i++) {
	...
}

// 연산 횟수 3N
for (int i = 0; i < 100; i++) {
	...
}
for (int i = 0; i < 100; i++) {
	...
}
for (int i = 0; i < 100; i++) {
	...
}

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

아래 코드의 연산 횟수를 N^2이다.

for 문이 10개가 더 있더라도 시간 복잡도의 변화 없이 N^2로 유지된다.

for ( int i = 0; i < 100; i++) { 
	for ( int j = 0; j < 100; j++) {
    	...
    }
}

코딩 테스트에서 시간 초과가 발생했다면 가장 많이 중첩된 반복문을 찾아서 개선해야 한다.