빅 오 표기법 1

빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다.

원소수에 따라 단계가 비례하며 증가한다면 O(N) 빅 오 엔 으로 표기한다. 이를 선형 시간 이라고도 부른다.

 

원소수가 어떻든 단계가 1이면 O(1)빅 오 일(상수 시간 이라고도 부른다), 단계가 4이면 O(4) 으로 표기한다.

 

이진 검색에선 O(log N)오 로그 앤으로 표기한다.

즉, 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 방법이다.

ex) O(log 4)란 사실 O(log 2^4) 라는 뜻이다. 결국 최종적으로 2로 2단계란 뜻이다.

 

가장 효율적인 순서론 O(1) > O(log N) > O(N) 이다.

 

원소개수(N)	O(N)	O(log N)
8	8	3
16	16	4
32	32	5
64	64	6
128	128	7
256	256	8
512	512	9
1024	1024	10