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

빅 오 표기법 (Big-O notation)

개념

알고리즘의 효율성을 분석하는 표기법이다. 컴퓨터의 사양과 환경에 따라 실행 속도는 각각 다르기 때문에 빅오 표기법은 러프하게 알고리즘의 성능을 측정한다. 가장 큰 항을 살리고 그보다 작은 항, 계수, 상수는 모두 무시하며, 상수항만 있다면 O(1)로 표기한다. 시간을 측정하는 시간 복잡도(Time Complexity)와 메모리 사용을 측정하는 공간 복잡도(Space Complexity)가 있다. 알고리즘을 구현하기 전에 조건을 보고 시간 복잡도와 공간 복잡도를 예측하여 가능한 알고리즘을 미리 추측할 수 있다.

시간복잡도

• 입력한 값 N에 따른 알고리즘의 최악의 경우 실행 시간을 나타낸다.

공간복잡도

• 입력한 값 N에 따른 메모리 사용량을 나타낸다.

순위	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(N²)	차수 시간
O(2^N)	지수 시간

 

활용

• O(N³)의 시간복잡도를 가지는 알고리즘은 1,000,000,000회 (10억)

• O(N²)의 시간복잡도를 가지는 알고리즘은 1,000,000회 (100만)

• O(N)의 공간복잡도를 가지는 알고리즘은 4byte*1000 = 4KB

• O(N²)의 공간복잡도를 가지는 알고리즘은 4byte*1000² = 4MB