[3장] 빅 오 표기법

'배열에 N개 원소가 있으면 선형 검색으로 N단계가 필요하다' 라는 장황한 설명을 제끼고
일관된 언어로 표현하기 위해 형식화현 표기법이 빅 오 표기법.

3.1 빅 오 : 원소가 N개일 때 몇 단계가 필요할까?
O(N) : 알고리즘에 N단계 필요 (선형 시간 알고리즘이라고도 부른다)
O(1) : 알고리즘에 1단계 필요 (상수 시간 알고리즘이라고도 부른다)

ㅇ상수시간 알고리즘에 관하여 O(1) 
설명은 1단계라고 써놨지만 정확히 말하면 원소의 갯수(N)에 관계없이 항상 일정한 단계가 걸림을 뜻한다.
즉, 항상 100만 단계가 걸려도 빅 오 표기상 O(1) 인 것.


3.2 빅 오의 본질
O(1)에서 봤듯이 빅 오 표기법은 단순히 몇 단계가 걸리는지를 나타낸다기보단(물론 보여주긴 하지만;;)
본질적으론 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.

즉, O(1)은 1단계일수도 있고 100만 단계일수도 있지만 데이터의 갯수와 무관하게 성능이 일정하다는 뜻이고
O(N)은 데이터 갯수와 비례하여 성능이 변한다는 뜻이다.

  3.2.1 O(1) vs O(N)
    얼핏 보기엔 O(1)이 무조건 효율적일거같지만
    O(1)이 사실 100만단계를 뜻하고 있다면?
    적어도 N이 100만개 이하라면 O(N)이 더 효율적이다.

  3.2.2 최선/최악의 시나리오
    선형 검색에서 운이 좋다면 1단계만에 원하는 값을 검색해낼 수도 있다. 
    즉, 최선의 시나리오는 O(1)이 될 수도 있는것.

    하지만 통상 빅 오 표기법은 최악의 시나리오를 기준으로 한다.
    최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 알면 
    최악을 대비함과 동시에 알고리즘 선택에 중요한 영향을 미칠 수 있기 때문이다.

3.3 O(logN) 로그시간 복잡도
여기서 logN = log_2(N) 을 뜻한다(아래첨자 2를 생략한 형태)
즉, 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 뜻한다.
이진검색이 정확히 여기에 속함