알고리즘의 시간을 표현하기(시간복잡도 / Time Complexity)

알고리즘은 효율적으로 짤수록 시간과 자원이 굉장히 줄어드는 효과를 볼 수 있다.

 

그리고 이러한 알고리즘이 수행하는데 걸리는 시간의 상한선 하한선을 시간복잡도로 표현할 수 있다.

 

시간복잡도가 낮을수록 해당 알고리즘이 더욱 효율적이라고 볼 수 있다.

 

시간복잡도에서 알고리즘의 실행시간 상한선은 Big-O 표기법을 사용해 나타낸다.

 

O(1)	상수의 형태
O(log n)	로그 형태	이진 탐색
O(n)	선형 형태	선형 탐색
O(n long n)	선형로그 형태	퀵정렬, 병합정렬(합병), 힙정렬
O(n^c)	다차 형태	선택정렬, 버블정렬, 삽입정렬

 

해당 표에서는 O(1)가 가장 빠르고 O(n^c)가 가장 오래 걸린다.

 

이러한 시간 복잡도는 대략적인 큰 숫자를 비교하는 것을 기본으로 한다.

 

이유는 작은 수를 하나하나 헤아리는 것은 전체 데이터의 처리 시간에 큰 영향을 주지 않기 때문이다.

 

Big-O의 반대 개념도 있다.

 

알고리즘 실행시간의 하한선은 Big-Omega(Ω)를 사용해 나타낸다.

 

Big-Omega는 알고리즘 배열 상태가 최적일 때 최소한의 실행에 걸리는 최적의 시간을 나타내는 것과 같다.

 

Ω(1)		선형탐색, 이진탐색(한 번에 찾는 경우)
Ω(log n)
Ω(n)		배열 안의 모든 숫자 세기
Ω(n log n)
Ω(n^2)

 

해당 표에서는 Ω(1)가 가장 빠르고 Ω(n^2)가 가장 오래 걸린다.

 

다만 빅 오메가는 알고리즘 설계시 빅오에 비해 중요성이 덜할 수 밖에 없는 그건 바로 항상 최적의 조건으로 데이터들이 정렬되어 있는 것이 아니기 때문이다.

 

그리고 시간의 하한선과 상한선이 같은 경우가 있는데 이 경우엔 Big-Theta(θ)라고 써준다.