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

점근표기법(빅오 표기법, Big-O notation)이란?

☞input된 데이터의 개수가 n개일때, 걸리는 시간을 수식으로 표현하여

수식중 알고리즘이 작동하는데 걸리는 시간에 가장 큰 영향을 미치는 부분만

Big-O notation에 사용하고 나머지 부분은 제거한다. 이때 상수 또한 모두 제거한다

n은 매우 큰 수라고 가정하고 n만 Big-O notation에 사용한다.

자료의 크기가 작으면(상수), 알고리즘에 따라 걸리는 시간 차이가 크지 않기 때문이다

시간 뿐만 아니라, 공간의 사용량을 나타낼 때도 사용된다.

(n이 무한대로 커진다고 생각한다면, 상수는 먼지에 지날뿐..)

 

'최악의 경우를 대비하여 코드 구현을 하기 위해 필요한 개념이다'

 

빅 오 표기법 읽는법

-O(n) 빅오 의 n

-빅 오 of n 

-O(n^2) 빅오 n제곱

-빅 오 of n제곱 의 방식으로 읽으면 된다.

 

작성방법 예시

작동 시간	Big - O 표기법
10n + 30	O(n)
5n^2 + 100n + 70	O(n^2)
8logn + 6	O(logn)
30logn + n^3	O(n^3)

 

점근 표기법

 

 

Big - O notation 의 종류와 소요시간 예시

 

데이터수│표기법	O(1)	O(n)	O(n^2)	O(n^3)	O(logn)
10개	5초	1초	1초	1초	1초
100개	5초	10초	100초	1,000초	2초
1,000개	5초	100초	10,000초	1,000,000초	3초

O(1) :자료의 길이(크기)에 상관없이 걸리는 시간이 항상 일정한 알고리즘을 표시

O(n) : 자료의 크기에 비례하여 시간이 늘어난다.

O(n^2) : 자료의 크기 제곱에 비례하여 시간이 늘어난다.

O(n^3) : 자료의 크기 세제곱에 비례하여 시간이 늘어난다.

O(logn) : 실행을 할 때마다, 경우의 수가 절반으로 줄어든다.

 

이 외에도 O(2^n) 등의 표기법이 생길 수도 있다.

알고리즘을 보고 그때 그때 표기법을 채택한다.

 

시간복잡도는 작성한 코드별 빅 오 표기법을 매긴 후,

(모두 더하여) 가장 큰 영향을 미치는

빅 오 표기법을 시간복잡도로 채택한다.

 

예)10n^2 + logn + 20  ☞ O(n^2) + O(logn) ☞ O(n^2)

 

공간 복잡도에도 같은 표기법을 사용하여 적용한다.

대상이 '시간' 이 아닌 사용된 '공간'을 중심으로 표기법을 사용한다.