알고리즘...4

점근적 표기

알고리즘의 효율성을 분석하기 위해 매우 큰 입력을 가정하여 분석하는 데 이 분석을 점근적 분석이라 한다.

 

극한에 대한 문제가 이러한 점근적 분석의 예이다.

 

이것의 의미는 n이 충분히 커짐에 따라 n의 비율로 증가한다는 것이다.

 

추가적으로 n와 10n, 2n^2의 예를 들면 다음과 같다.

n	10n	2n^2
1	10	2
2	20	8
10	100	200
1,000	10,000	20,000
10,000	100,000	2,000,000
100,000	1,000,000	200,000,000
1,000,000	10,000,000	2,000,000,000,000
10,000,000	100,000,000	200,000,000,000,000
...	...	...
10^10	10^11	2*10^20
10^20	10^21	2*10^40

 

예제에서 확인할 수 있다시피 n 앞의 계수는 초기에는 큰 영향을 주지만 n이 커질수록 그 영향력이 작아지고 결국엔 무시할 수 있을만한 수준이 된다는 것을 알 수 있다.

 

※ 점근적 분석은 계수와 상수를 무시한다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘