알고리즘 시간 복잡도

연산의 횟수를 점근적 표기법을 통해 추상적으로 표현하는 것을 시간복잡도 라고합니다.

표기는 대문자 O를 이용해서 표기 코드의 시간복잡도는 최악의 경우의 수를 가정하고 부릅니다.

코드의 시간복잡도는 연산 중에서 가장 복잡한 시간복잡도를 기준으로 합니다.

Ex) 1

int sum = 0;
for(int i = 0; i < 10; i++) {
	sum += i;
}
 //위와 같은 연산을 했을때 연산은 총 10번 실행됩니다. 

int sum = 0;
for(int i = 0; i < N; i++) {
	sum += i;
}
// 위와 같은 연산을 했을때 연산은 총 N번 실행됩니다.

위 코드처럼 N번실행되는 경우 O(N)이라고 표기합니다.

Ex) 2

int a = 5;
System.out.println("a");

예제 2번 같은 경우 시간복잡도를 어떻게 표기할까요?

연산의 과정이 위처럼 상수일 경우에는 O(1)이라고 합니다.

Ex) 3

int a = ?; //(1 ~ 10)
int[] arr = {1,2,3,4,5,6,7,8,9,10};
for(int i = 0; i < arr.length; i++) {
	if (a == arr[i]) break;
}

a가 1일 경우에는 for문이 한 번만 실행되고 O(1) 종료되지만 10일 경우 10번까지 다 돕니다. O(N)

a가 어떤 수일지 모르기 때문에, 이러한 경우 최악의 경우를 생각해서 위 코드의 시간복잡도는 O(N)입니다.

Ex) 4

int sum = 0;
for(int i = 0; i < N; i++) { // O(N)
	sum += i;
}

int sum2 = 0;
for(int i = 0; i < N; i++) {. //O(N^2)
	for(int j = 0; j < N: j++) {
		sum2 += j;
	}
}

위처럼 하나의 코드에 연산을 2번 하는 코드가 있을 때 첫 번째 for문은 O(N)이고, 두 번째 for문은 O(N^2)입니다.

위 코드는 O(N^2)가 더 복잡한 시간복잡도 이기 때문에 시간복잡도가 O(N^2)이라고 합니다.

위 이론을 문제에 어떻게 활용될까?

보통 for문을 1억 번 도는데 1초 정도 시간이 걸린다고 합니다.

문제를 풀 때 제한시간이 1초인 경우 N의 범위에 따라 문제를 해결할 수 있는 시간복잡도에 대해서 알 수 있습니다.

 

💡 제한시간이 1초일 때 N의 범위에 따른 문제를 해결할 수 있는 시간복잡도

N ≤ 10 ⇒ O(N!), O(N^2), O(3^N)

N ≤ 20 ⇒ O(2^N)

N ≤ 100 ⇒ O(N^4)

N ≤ 500 ⇒ O(N^3)

N ≤ 1,000~2000 O(N^2), O(N^2 logN)

N ≤ 100,000 O(NlogN)

N ≤ 10,000,000 O(N)

 

보통 위와 같이 N의 범위가 주어지면 해당 시간복잡도 내에 문제를 해결해야 정답을 맞힐 수 있습니다.