3장 빅 오 표기법

앞선 장에서 여러 효율성을 N 또는 N+1 단계와 같은 표기법을 사용했지만 이러한 방법은 너무 장황하기 때문에 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기위해 형식화된 표현법을 빅 오 표기법 이라 부른다

---

3.1 빅 오

기본적으로 선형검색의 경우 최악의 경우 N단계가 필요한 기법이고 이를 빅 오 표기법으로 표시하면 

 

                                                                          O(N) 

위와 같이 나타낸다. O(N)은 알고리즘에 N단계가 필요하다는 뜻이다.

또한 읽기와 같이 데이터의 갯수와 상관없이 항상 일정한 단계(읽기의 경우 1단계)가 필요한경우는

                                                                          O(1)

위와 같이 표기한다. O(1)같은 경우는 배열의 원소의 개수와 상관없이 항상 같은 단계를 필요로 하기때문에 "가장 빠른" 알고리즘 유형으로 분류하고 상수시간을 갖는 알고리즘이라 부르기도 한다.

 

3.2 빅 오의 본질

※ 데이터의 개수와 상관없이 항상 3단계가 걸리는 알고리즘? --> O(3)?  (X)

 

ㄴ위의 질문에 답을 하기 위해선 빅 오의 본질을 이해해야 한다. 빅 오는 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻하기 때문에 O(1) 과 O(3)을 구분지어야 할 필요가 없다( 둘 다 데이터의 개수와 상관없이 항상 같은 단계를 필요로 한다는 뜻) 그러므로 통합적으로 O(1)로 표기한다.

별도의 명시가 없는 일반적인 경우의 빅 오는 항상 최악의 시나리오를 의미한다.(선형검색의 최선의 시나리오는 O(1)의 결과를 도출하지만 일반적인 표기법 대로면 최악의 시나리오인 O(N)으로 표기한다.)

3.3 세 번재 유형의 알고리즘( O(logN))

앞서 다루었던 이진검색 같은 경우에는 데이터의 양이 두배로 늘어날때마다 하나의 단계가 추가되는 구조였다. 이를 빅 오표기법으로 나타낸다면

                                                                             O(logN)

위와 같이 표기한다. 빅 오에서 로그를 표시할땐 로그뒤 첨자 2를 생략하여 표시한다.

로그시간의 복잡도를 가진다는것은 로그 계산법과 같이 N이 8이라 가정했을때

log(2)8 = 3 즉 3단계가 필요한 알고리즘이다 라고 칭할 수 있다. 즉 O(N)과 비교했을때 훨씬 효율적인 알고리즘이라는 것을 알 수 있다 이해를 돕기 위해 표를 활용해 O(N)과 O(logN)을 비교했다.

N	O(N)	O(logN)
8	8	3
16	16	4
32	32	5
64	64	6
128	128	7
256	256	8
512	512	9
1024	1024	10