빅오 표기법이란?

빅오 표기법이란?

알고리즘의 효율성을 표기해주는 표기법, 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용

시간 복잡도는 시간의 효율성을, 공간 복잡도는 메모리의 효율성을 의미

왜 빅오(Big-O) 표기법을 사용하지?

알고리즘의 최소한의 성능이 보장되도록 최악의 실행 시간을 표기한다. 때문에 가장 많이 사용된다.

특징

상수항을 무시한다.

• O(N+1)의 복잡도는 상수를 무시해 O(N)으로 표기한다.

계수를 무시한다.

• O(5N)의 복잡도는 계수를 무시해 O(N)으로 표기한다.

최고차항만 표기한다.

• O(3N^3+2N^2+N+5)의 복잡도는 O(N^3)으로 표기한다.

빅오 표기법 종류

O(1)

가장 빠르다. 대표적으로 Queue의 삽입/삭제, Stack의 삽입/삭제, 배열의 인덱스 접근과 같은 연산이 이와 같다.

 

O(log N)

연산이 한 번 씩 실행될 때마다 데이터의 양이 절반으로 감소된다. 대표적으로 B tree의 검색/삽입/삭제 연산이 이와 같다.

O(N)

입력 값에 따라서 실행시간이 선형적으로 증가한다. 1중 for문, 배열의 탐색, 해시테이블의 전체 탐색, 트리의 전체순회 연산이 이와 같다.

O(N log N)

입력 값에 따라서 실행시간이 log N의 곱으로 증가한다. Merge sort, Heap sort, Quick sort, 분할 정복 알고리즘이 이와 같다.

O(N^2)

입력 값에 따라서 실행시간이 제곱으로 증가한다. 2중 for문, Bubble sort, Selection sort이 이와 같다.

O(2^N)

입력 값에 따라서 실행시간이 지수적으로 급격히 증가한다. 재귀(피보나치 수열, 하노이 탑)이 이와 같다.