asymptotic notation(점근 표기법)

1. asymptotic notation

: 알고리즘의 효율성을 표기위한 방법으로 상수 계수와 중요하지 않은 항목들을 제거한 것이다. 

 

2. growth rate

: n 값이 일정하게 증가함에 따라 늘어나는 시간을 확인한다. 

: c < logn < n < nlogn < n^2 <  n^3 < 2^n

 

3.

- Big-Oh

: f(n) <= c*g(n)

 

- Big-Omega

: f(n) >= c*g(n)

 

- Big-Theta

: c1*g(n) <= f(n) <= c2*g(n)

 

4. 예시

2n = O(n^2)

n^2 = Ω(n)

2^n = O(8^n)

3n^2+2n+1 = O(n^2)

 

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

점근적 표기법 (개념 이해하기) | 알고리즘 | Khan Academy