[알고리즘 코딩테스트] 시간 복잡도 표기법 알아보기

 

 

📑 시간 복잡도 정의하기

 

시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟를 말한다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 

 

실제 시간 복잡도를 정의하는 유형은 다음과 같다.

 

📌 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 
📌 빅-세타(θ(n)) : qhxhddlf EO(average case)의 연산 횧수를 나타내는 표기법
📌 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

 

우리는 알고리즘을 풀때 항상 최악일 떄, 즉 데이터의 크기가 가장 클 때를 기준으로 하기 때문에 빅-오 복잡도를 사용해야 한다. 빅오 복잡도는 다음과 같다. 

 

 

출처 : https://velog.io/@welloff_jj/Complexity-and-Big-O-notation

 

 

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

 

 

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

 

시간 복잡도 도출 기준 

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

 

코드를 예로들어 살펴보자. 

 

 

<연산 횟수가 N인 경우>

public class 시간복잡도_판별원리1{
	public static void main(String[] args) {

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

 

 

<연산 횟수가 3N인 경우>

public class 시간복잡도_판별원리2{
	public static void main(String[] args) {

		int N = 100000;
		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++);
		}
		
	}
	
}

 

 

위의 2개의 예제 코드의 연산 횟수는 3배의 차이가 난다. 언뜻 생각하면 큰 차이인 것 같지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다. 

 

 

 

<연산 횟수가N의 제곱인 경우>

public class 시간복잡도_판별원리3{
	public static void main(String[] args) {

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

 

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for문이 전체 코드의 시간 복잡도 기준이 된다. 만약 일반 for문이 10개 더 있다고 해도 이는 도출 원리의 기준 2에 따라 시간 복잡도의 변화 없이 N의 제곱으로 유지된다.