Big-Oh Notation

- 데이터의 수 n 과 그에 따른 시간복잡도 함수 T(n)을 구하는 위하여 Big-Oh 표기법을 사용한다.

- 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다.

- 데이터 수의 증가에 따른 연산횟수의 증가 형태를 표현.

예)

    T(n) = n² +3n + 1, 이식에서 가장 영향력이 큰 T(n) = n² 로 표현한다.

다음 표는 n² 이 차지하는 비율을 정리한 것이다.

결국,  T(n) = n² +3n + 1 의 빅오는 n² 이며, n 의 증가 및 감소에 따른 T(n)의 변화 정도가 n²의 영향을 가장 많이 받는 것을 나타냄. 

O(n²) 표기, Big-Oh of n² (빅오 오브 n² )

대표적인 Big-Oh

O(1)

    : 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘

O( log n )

    : 로그형 빅-오, 데이터 수의 증가에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘, 이상적인 유형

O(n)

    : 선형 빅-오, ㄷ이터의 수와 연산횟수가 비례하는 알고리즘

O( n log n)

    : 선형로그형 빅-오, 데이터의 수가 두배로 늘어날때, 연산횟수는 두배 조금 넘게 증가하는 알고리즘

O( n² )

    : 데이터의 수의 제곰에 해당하는 연산횟수를 요구하는 알고리즘, 중첩 반복문 연산으로 바람직하지 못한 형태

O( n³ )

    : 데이터 수의 세제곱에 해당하는 연산횟수를 요구하는 알고리즘, 삼중 중첩 반복문 연산으로 무리가 있는 알고리즘

O(2n)

    : 지수형 빅-오, 사용하기에 매무 무리가 있는 알고리즘

* log 간단 설명

a^x=b 일때, x=log_ab 를 만족, 여기서 a를 로그의 '밑', b를 로그이 '진수'라 함.

예)

    2⁴=16 일때, 4=log₂16 입니다.

    로그의 밑 10일겨우 생략 가능 합니다.  log₁₀x 는 log x 라고 표현.