점근적 표기법 ( asymptotic notation)

* 점근적 표기법 이란?

상수 계수와 중요하지 않은 항목을 제거한것 !

점근적 표기법에는 3가지가 있다.

- big-ThetaΘ 표기법

> 보통 상수 인자와 낮은 차원의 항목은 생략하고 사용한다. 예를들어 시간이 6n^2 + 100n + 300이라고 가정하면, 

계수인 6과 저차원 항목인 100n+300을 생략한 n^2만 실행시간으로 치는것이다. 

big-세타 표기법을 사용하는건, 실행시간에 대해 점근적으로 근접한 한계값이 있다고 표현하는것이다. 

점근적으로 ! 라는 말을 쓰는 이유는, 큰 값의 n에 대해서만 적용되기 때문이다. 근접한 한계값이라는 말은, 위, 아래로 상수값 내에서 실행시간을 좁힐 수 있다는 뜻이다. 

https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation- 

Big-θ (빅 세타) 표기법 (개념 이해하기) | 알고리즘 | Khan Academy

 

- big-O 표기법

> 점근적 상한선 표기법. "실행 시간은 최대한 이만큼 커지지만, 더 천천히 커질 수도 있다. !" 는 의미.

이는 충분히 큰 입력 크기에 대하여 실행 시간에 상한값을 두고 제한한다. 

증가율에 따라 함수를 종류대로 나열하면 다음과 같다.

상수함수 -> 로그 함수 -> 선형 함수 -> 2차형 함수 -> 다항 함수 -> 지수 함수

* 로그 함수에서 밑이 작은 함수가 밑이 큰 함수 보다 더 빠르게 증가한다. 

예를들어 순서대로 나열해보면 다음과 같다.

64 -> log8​n -> log2​n -> 4n -> nlog6​n -> nlog2n -> 8n^2 -> 6n^3 -> 8^2n

 

- big-OmegaΩ 표기법

> 점근적 하한선을 표현하기 위한 표기법이다. 그 이유는, 점근적 하한선은 충분히 큰 입력 크기에서 실행시간을 밑에서 제한하기 때문.