빅 오 표기법 (Big - O notation)

빅오 표기법은 점근적 묘사 방법으로 , 대문자 O에 괄호를 하고 안에 계수를 뺀 차수가 가장 큰 항을 넣어주면 된다. 시간 복잡도의 효율성이 좋은 순으로 나열하면,

이렇게 나열이 가능하다.

이것을 그래프로 보면,

이렇게 기울기가 많이 차이나는 것을 볼 수 있다.

빅오 표기법의 대표적인 예는 다음과 같다.

1. O(1) : 스택에서 Push,Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬, 병합 정렬, 힙 정렬
5. O(n^2) : 이중 for문, 삽입정렬, 거품정렬, 선택정렬
6. O(2^n) : 피보나치 수열