시간 복잡도( time complexity) 는 프로그램이 실행되고 어떠한 알고리즘을 통과할때 완료하는 시간을 뜻한다.
시간 복잡도를 표기하는 방법은 크게 3가지로 나누게 되며 기호는 오메가, 쎄타, 오가 있다. 대소문자에 따라서 리틀 오메가, 리틀 오표기법도 있지만 각각 함수의 기울기의 하한선과 상한선을 여유있게 표기하고 상한선과 하한선이 될수 없다는 의미를 포함 하고 있을 뿐이기 때문에 많이 쓰이지 않는다
Ω |
빅 오메가 |
알고리즘 최고의 성능을 표기. |
θ |
빅 쎄타 |
알고리즘 대략의 성능을 표기. |
O |
빅 오(Big-oh) |
알고리즘 최악의 성능을 표기 |
이중에 가장 많이 쓰이는 표기법은 빅 오 표기법으로 최악의 상황에서 이 정도 까지는 성능을 보장한다는 의미를 갖고 있다.
시간 복잡도를 표기할때 계수나 상수는 무시하게되는데 O(1)이나 O(10000)은 같다고 보게 되는데 1이나 10000이나 입력되는 값에 따라 알고리즘의 속도가 변화 없기 때문에 무시된다.
O(n), O(100n), O(n-1)의 경우도 같다고 보게 되는데 n의 값이 무한데로 커졌을때 -1이나 계수는 무시할수 있다고 보기 때문이다.
간단하게 빅오 표기법을 사용하는 방법은
첫번째로 입력값(n)이 무엇인지를 확인한다.
두번째로 수행 연산 횟수를 n의 식으로 표현한다.
세번째로 가장 차수가 높은 항만 남기고 그 아래 차수와 상수는 지운다.
주의할점으로 반복문이 두개가 나란히 있는 경우 더 높은 차수의 for문을 알고리즘 성능으로 사용하고 상수가 곱해져 있고 옆에 n이 더 있더라도 최고 차수만 사용한다.
'Algorithm' 카테고리의 다른 글
| Dynamic Programming(동적 계획법) (0) | 2014.07.17 |
|---|