[알고리즘] 빅오 표기법 (big-O)

빅오 표기법

빅오 표기법은 점근적 실행 시간을 표기할 때 가장 많이 사용하는 수학적 표기 방법으로, 점근적 실행 시간이란 n이라는 입력값이 무한대로 커질 때의 실행 시간 추이를 의미한다. 점근적 실행 시간을 달리 말하면 '시간 복잡도' 라고 할 수 있다. 
빅오 표기법은 알고리즘 최악의 실행 시간을 표기하며, 가장 많이 사용하는 표기법이다. 

 

다양한 빅오 표기법의 종류

 

빅오 표기법은 왼쪽에서 오른쪽으로 갈수록 효율성이 좋아진다. ( O(1) 이 가장 빠름 )

차례대로 지수함수, 다항함수, 선형함수, 로그함수, 상수함수를 의미한다.

 

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) : 피보나치 수열 

 

🔥 빅오 표기법의 특징

1. 상수항을 무시한다. ( O(N+5) -> O(N) 으로 표기)

2. 계수도 무시한다. ( O(3N) -> O(N) 으로 표기)

3. 최고 차항만 표기한다. ( O(3N^3 + 2N^2) -> O(N^3) 만 표기)