Big-o표기법이란?
- 알고리즘의 “효율성”을 평가하기 위한 분석법입니다.
- 즉, 알고리즘의 성능을 수학적으로 표현해주는 표기법입니다.
- 시간과 공간복잡도를 표현할 수 있습니다.
- 실제 러닝타임을 표시하기보다는 데이터나 사용자의 증가률에 따른 알고리즘의 성능을 예측하는게 목표입니다.
O(1)
언제나 일정한 시간이 걸리는 알고리즘
O(n)
입력 데이터의 크기에 비례해서 철회시간이 걸리는 알고리즘을 표현할때 사용, 데이터와 시간이 같이 증가함
O(n^2)
O(nm)
O(n^3)
O(2^n)
피보나치수열 사용 / 처음엔1로 시작하여 늘어난 면이 2 > 3 > 5 > 8
O(log n) / binary search
한번씩 찾을 때마다 검색해야하는 데이터의 양이 절반씩 떨어지는 알고리즘
O(Sqr+(n))
Big-o 표기법 특징
- 영향력 없는 항 무시합니다.
1 | ex) O(N^2 + 2N + 1) -> O(n^2) |
- Big-O표기법은 상수는 버리고 표현합니다
Big-o 표기법 성능비교
그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같습니다.
faster O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) slower
Big-o 표기법 예제
빅오 표기법의 예제는 어떤 것들이 있는지 정도만 외워두고 알고리즘 공부를 해보면서 이해해 나가면 좋을 것 같습니다.
- O(1): 스택에서 Push, Pop
- P(log N): 이진트리
- O(N): for문
- O(N log N): 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap sort)
- O(N^2): 이중 for문, 삽입정렬(insert sort), 거품정렬(bubble sort), 선택정렬(selection sort)
- O(2^N): 피보나치 수열
자료참고