Growth of Function

 

 

 

0. Asymptotic Notations

 

알고리즘을 만들다 보면 알고리즘을 평가해야 할 때가 많습니다. 너무나 당연한 이야기지만 슈퍼컴에서 돌릴 때와 내 작고 귀여운 5년된 노트북에서 돌릴 때 성능 차이는 당연히 날 것입니다.(아주많이..ㅠ) 따라서 알고리즘의 성능을 평가할 때는 컴퓨터의 성능과는 관계가 없는 방법으로 평가를 하게 됩니다. 이를 Asymptotic Notation(점근표기법)이라고 합니다.

 

 

한국어 이름 '점근'에서 볼 수 있듯이, Asymptotic Notation에서는 'n을 무한대로 보냈을 때 소요되는 시간이 얼마나 걸리는가'를 기준으로 봅니다.

 

예를 들어 어떠한 알고리즘의 시간소요량이 f(n)=5n^2+8n+10이라고 합시다.

이 경우 n을 무한대로 보내면, 5n^2의 값이 8n에 비해서는 매우 클 것입니다. 따라서 8n+2는 무시하고, 5n^2가 f(n)의 asymptotic notation이라고 할 수 있습니다. 

 

 

 

1. Asymptotic Notation의 종류

 

표기법	대략적 의미
f=O(g)	f는 g보다 작거나 같다, f ≤ g
f=o(g)	f는 g보다 작다, f < g
f=Ω(g)	f는 g보다 크거나 같다, f ≥ g
f=ω(g)	f는 g보다 크다, f>g
f=Θ(g)	f는g와 대략 같다, f=g

 

 

 

 

 

 

 

https://velog.io/@honeyricecake/3.-Growth-of-Functions

참고: https://hezma.tistory.com/6