점근 표기법에서 ‘점근’ 은 한자 뜻(漸近 차츰 점, 가까울 근)을 보면 알 수 있듯이 수행 시간을 대략적으로 나타내는 방법입니다.
n개의 데이터를 처리하는 A알고리즘은 n^2 + 5n 번 계산하고, B알고리즘은 27n 번 계산한다고 가정해 봅시다.
n = 1 인 경우에는 A알고리즘은 6, B알고리즘은 27 번 계산합니다.
n = 5 인 경우에는 A알고리즘은 50, B알고리즘은 135번 계산합니다.
n = 10 인 경우에는 각각 150, 270번 계산합니다.
여기까지 보면 A알고리즘이 더 빠르다고 생각할 수 있습니다. 하지만 알고리즘 속도의 차이는 데이터가 많아질수록 더 확연히 드러납니다. 데이터가 아주 적을 때에는 퀵정렬보다 삽입 정렬이 더 효율적인 것도 이런 경우입니다.
n을 100까지 키우면, A알고리즘은 10,500 B알고리즘은 2,700 번 계산합니다.
n을 더 키워봅시다.
n = 1000 인 경우에는 각각 1,005,000번, 27,000번 계산합니다.
n이 더 커질수록 차이가 더욱 더 벌어지겠죠.
이렇게 계산을 해보다보면 아래와 같은 결론을 도출할 수 있습니다. 각 문자에 곱해진 계수나, 다른 항보다 최고차항의 차수가 가장 큰 영향을 미친다.
다음 글에서는 이전 글 마지막에 언급했던 빅-오/빅-오메가/빅-세타 표기법에 대해 쓰도록 하겠습니다.