02. 시간복잡도

알고리즘을 사용하는 이유는 최적화, 그 중에서도 속도와 메모리라고 볼 수 있습니다.

 

시간 복잡도는 이 중 속도에 붙은 개념인데,

 

단순하게 보면 입력크기에 대한 연산 횟수의 최대값입니다.

단순하진 않은데

 

가장 단순한 예시인 1차원 배열의 탐색법을 생각해보면

 

 

1을 찾는다면 1번 비교, 8을 찾는다면 8번 비교를 하게 됩니다.

 

그럼 이 1차원 탐색의 시간 복잡도는 1~8이라고 보면 될까요?

 

만약에 길이가 100, 1000, 1억이 된다면 복잡도는 1억인걸까요?

 

말도 안되죠. 그렇기 때문에 빅 오 표기법이라는 방법을 도입했습니다.

(위는 사실 절대시간이라는 표기법입니다..)

 

알고리즘의 탐색횟수를 방정식으로 정리한 후에 최고차항만 표기하는 것이죠.

 

위 알고리즘의 경우 O(x)라고 볼 수 있습니다.

 

그럼 왜 이런 표기법을 쓰는걸까요?

 

위 같은 절대 시간의 경우 상황에 따라 너무 다양한 시간이 나올 수 있습니다.

 

그래서 최악의 경우만 표현하기 위해 빅 오 표기법이라는 방법을 만든 것입니다.

 

원리는 간단합니다.

 

해당 알고리즘의 연산횟수를 방정식으로 나타낸 후에 

 

1. 특정 시간 x부터 항상 f(x) <= C*g(x)를 만족

2. C는 상수

 

위 두조건을 만족하는 g(x)가 있다면 O(g(x))라고 표현합니다.

 

이 g(x)는 지수함수 > 다항함수 > 로그함수 순으로 정해집니다.

 

근데 이거 어디에 써먹냐구요?

 

데이터의 양에 따라 사용 가능한 알고리즘의 가닥을 잡을 수 있습니다.

 

컴퓨터가 1초에 사용가능한 연산의 개수를 1억개로 봅니다.

 

그리고 시간 복잡도에 따라 반복해서 연산이 가능한 횟수를 종류별로 정리하면

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	1,000,000
O(N)	10,000,000~20,000,000
O(logN)	1,000,000,000

 

데이터의 개수가 10,000,000개 라면 O(N)의 시간복잡도를 가진 알고리즘을 후보에 둬야겠죠.

 

그렇기 때문에 알고리즘에 따른 시간복잡도를 아는 것이 중요합니다.

 

마무리

시간복잡도에 대해서 알아봤습니다.

 

복잡하고 어렵지만 가장 중요한 부분입니다.

 

다음 글은 코딩테스트에 필요한 파이썬 문법에 대해 알아보겠습니다. ㅎ