-
점근적 표기
알고리즘의 효율성을 분석하기 위해 매우 큰 입력을 가정하여 분석하는 데 이 분석을 점근적 분석이라 한다.
극한에 대한 문제가 이러한 점근적 분석의 예이다.
이것의 의미는 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이 커질수록 그 영향력이 작아지고 결국엔 무시할 수 있을만한 수준이 된다는 것을 알 수 있다.
※ 점근적 분석은 계수와 상수를 무시한다.