점근 표기법(빅오, 빅오메가, 빅세타)
by hiSon점근표기법
알고리즘의 성능을 표현하는 수학적 표기법이다. 알고리즘의 시간 복잡도(실행시간)나 공간 복잡도를 표현하는 데 사용된다.
알고리즘의 실행시간은 하드웨어나 운영체제 등 여러 영향에 따라 다르게 측정될 수 있다.
실행환경을 동일하게 하는 것은 어렵기 때문에 알고리즘의 효율을 측정하기위해 점근 표기법을 사용한다.
1. 빅 오메가 표기법
최선의 경우 실행시간이나 공간 복잡도의 하한을 나타낸다. 최선의 경우에서 알고리즘의 실행 시간이나 공간 복잡도가 감소하는지를 나타낸다.
f(n) = Ω(g(n))
g(n)을 함수 f(n)의 점근적 하한이라고 한다.
즉 f(n)의 복잡도는 최선의 경우라도 g(n)보다 크거나 같다는 의미이다. f(n)≥g(n)
g(n)보다 더 좋을 수는 없다.
2. 빅 세타 표기법
알고리즘의 실행 시간이나 공간 복잡도의 상한과 하한이 같은 경우를 나타낸다. 알고리즘의 성능이 최악과 최선의 경우에서 동일한 경우에 사용된다.
f(n) = Θ(g(n))
g(n)을 함수 f(n)의 점근적 상한 및 하한이라고 한다.
즉 f(n)의 복잡도가 최선의 경우나 최악의 경우라도 g(n) 범위 내에 있다는 의미이다.
대략 f(n) = g(n)
3. 빅오 표기법(Big-O notaiton)
최악의 경우 실행 시간이나 공간 복잡도의 상한을 나타낸다. 최악의 경우에서 알고리즘의 실행 시간이나 공간 복잡도가 얼마나 증가하는지를 나타낸다.
보통 시간 복잡도를 계산할 때 많이 사용된다.
f(n) = O(g(n))
g(n)을 함수 f(n)의 점근적 상한이라고 한다.
즉 f(n)의 복잡도는 최악의 경우라도 g(n)보다 작거나 같다는 의미이다. (f(n) ≤ g(n))
g(n)보다 더 나쁠 수는 없다
빅오 표기법으로 시간복잡도 계산 방법
1. 상수는 전부 1로 생각한다.
2. 같은 n에 대해서는 가장 큰 영향력을 미치는 식을 대표로 한다.
->4n+3일 경우 x4와 +3을 무시하고 n으로 표현
3. 제곱수가 가장 큰 것을 제외하고 나머지는 무시한다.
->n^3+4n+200일 경우 n^3
4. log는 상수 1보다 크고 n보다는 작다
5. n에 관한 식이 곱하기로 연결되어있으면 하나로 취급하고, 더하기로 연결되어있으면 따로 취급하고 더 큰것만 표현한다.
6. 다른 변수끼리는 더하기라도 따로 취급한다.
7. n제곱보다는 2의 n제곱이 더 크다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
빅오 표기법 예제
| O(1) | 스택의 Push, Pop |
| O(log n) | 이진트리 |
| O(n) | for문 |
| O(nlogn) | 퀵 정렬, 병합정렬, 힙 정렬 |
| O(n^2) | 이중 for문, 삽입정렬, 거품정렬(버블정렬), 선택정렬 |
| O(2^n) | 피보나치 수열 |
참고
블로그의 정보
개발 보석함
hiSon