점근 분석(Asymptotic Analysis)이란?
점근 분석(asymptotic analysis)은 입력 크기를 기준으로 알고리즘의 성능을 가늠할 수 있게 해주는 핵심 기법입니다. 여기서 중요한 점은 실행 시간을 정확히 계산하는 것이 아니라, 실행 시간과 입력 크기 사이의 관계를 찾는 것입니다. 즉, 입력 크기가 커질 때 실행 시간이 어떤 패턴으로 변화하는지에 주목해야 합니다.
공간 복잡도(space complexity) 역시 같은 원리로 접근합니다. 이 경우의 목표는 알고리즘을 완료하기 위해 메인 메모리가 얼마나 사용되는지를 나타내는 관계식 또는 함수를 구하는 것입니다.
점근적 거동(Asymptotic Behavior)
함수 f(n)의 점근적 거동(asymptotic behavior)이란 n이 커짐에 따라 f(n)이 어떻게 증가하는지를 의미합니다. 작은 입력값은 고려 대상에서 제외되며, 우리의 관심사는 큰 입력값이 주어졌을 때 알고리즘이 얼마나 많은 시간을 소요하는지 파악하는 것입니다.
예를 들어, f(n) = c × n + k 형태의 함수는 선형 시간 복잡도(linear time complexity)를 나타냅니다. 반면 f(n) = c × n2 + k 형태의 함수는 이차 시간 복잡도(quadratic time complexity)를 나타냅니다.
알고리즘 분석의 세 가지 경우
알고리즘의 성능 분석은 일반적으로 다음의 세 가지 경우로 나누어 살펴볼 수 있습니다.
1. 최선의 경우(Best Case)
실행 시간의 하한(lower bound)을 계산하는 경우입니다. 가장 유리한 조건에서 알고리즘이 어떻게 동작하는지를 보여주며, 실제 환경에서 자주 발생하지 않을 수 있다는 점을 유의해야 합니다.
2. 평균적인 경우(Average Case)
실행 시간의 상한과 하한 사이 영역을 계산하는 경우입니다. 이때 수행되는 연산 횟수는 최솟값도 최댓값도 아니며, 무작위 입력에 대한 현실적인 성능을 예측하는 데 유용합니다.
3. 최악의 경우(Worst Case)
실행 시간의 상한(upper bound)을 계산하는 경우입니다. 최대 개수의 연산이 수행되는 상황을 다루며, 알고리즘 성능의 상한선을 보장하기 때문에 실무에서 가장 널리 참고되는 지표입니다.
