시간 복잡도와 Big-O 표기법

시간복잡도란?

알고리즘의 성능을 측정하는 방법이다. 실제로 걸리는 시간이 아니라, 이 알고리즘이 입력되는 데이터의 양에 따라 얼마나 많은 단계를 거쳐야 하는지의 비율을 말한다.

 

빅오(Big-O) 란?

시간 복잡도를 표기하는 방법 중 대표적으로 쓰이는 표기법이다. 입력되는 데이터의 개수를 n이라고 하면 O(n) 같이 표기한다.

 

참고로, 10개, 100개 데이터에 따른 성능 차이는 미미하다. 하지만, 100000개, 100000000개의 경우를 보면 성능 차이가 눈에 띄게 난다. 그러니 적은 양의 데이터의 경우는 고려하지 않는다. 또 빅오는 대충 이런 비율로 증가할 것이다~ 라는 의미에서 사용되므로 일정하게 증가하는 상수항은 의미가 없어 표기하지 않는다.(n*n-1 이나 n*n 이나 의미는 같으니...)

 

또 알고리즘에 따라 best case, average case,  worst case 가 있을 수 있다. 배열의 경우에 선형검색을 하는데, 첫 번째 칸에 데이터가 있다면 best 고 맨 끝에 있는 경우라면 worst 다. best는 일어날 확률이 극히 낮고, average 는 모든 경우에 적용할 수 없다. 따라서 시간복잡도는 보통 worst case 로 말한다.

 

대표적인 표기법

O(1) - constance time

한 단계만 거치면 되므로 데이터가 증가해도 성능에 변화가 없음.

 

O(n)

데이터가 1개씩 증가할 때마다 단계가 1개씩 추가된다. n개면 n번의 단계를 거쳐야 하는 셈.

 

O(n*m)

n번의 단계가 m번 반복되는 것.

 

O(n^2)

n번의 단계가 각 회차 때 n번 더 반복되는 것.

 

O(n^3)

n번의 단계가 각 회차때 n번 반복되는데, 이 회차에서도 또 한번 더 n번 반복되는 것.

 

O(2^n) - exponential time

피보나치 수열의 재귀호출처럼, 각 단계는 2가지의 하위 단계가 있고 하위 단계도 그 아래 2가지 하위 단계를 가지는 구조. 자료구조 중 트리를 생각해보자. 아래로 내려갈 수록 레벨에 따른 노드들이 많아지는데, 이진트리의 경우 레벨에 따른 노드 개수를 2^n-1 로 구할 수 있었다. 상수항은 버린다고 했으니 2^n 으로 표기하는 것.

 

O(m^n) - expoenetial time

위 처럼 각 단계의 하위 단계가 m 개라면 O(m^n) 으로 표현.

 

O(log n)

단계를 거칠 때마다 해야되는 작업이 반절로 줄어드는 구조. 이진 검색을 생각하면 된다.

 

O(sqrt(n))

square root 는 제곱근을 말한다.