점근 표기법

점근 표기법 (Asymptotic Notation)은 알고리즘의 효율성을 분석하고 비교하는 데 사용되는 수학적 표기법입니다. 특히 입력 크기가 충분히 큰 경우에 알고리즘의 실행 시간이나 메모리 사용량과 같은 자원 사용량이 어떻게 증가하는지를 나타내는 데 유용합니다. 점근 표기법은 정확한 실행 시간을 측정하는 것이 아니라, 입력 크기에 따른 증가율에 초점을 맞춥니다. 이를 통해 알고리즘의 성능을 보다 추상적으로 평가하고, 서로 다른 알고리즘을 비교하여 더 효율적인 알고리즘을 선택하는 데 도움을 줍니다.

점근 표기법은 주로 다음 세 가지 종류로 나뉩니다.

• 빅오 표기법 (Big O notation): 최악의 경우, 즉 상한(upper bound)을 나타냅니다. 알고리즘의 실행 시간이 특정 함수보다 '결코' 더 나빠지지 않는다는 것을 의미합니다. 예를 들어, O(n)은 입력 크기 n에 비례하여 실행 시간이 증가하는 알고리즘을 나타냅니다.

• 빅 오메가 표기법 (Big Omega notation): 최선의 경우, 즉 하한(lower bound)을 나타냅니다. 알고리즘의 실행 시간이 특정 함수보다 '항상' 더 좋아지지 않는다는 것을 의미합니다. Ω(n)은 입력 크기 n에 비례하여 실행 시간이 최소한 증가하는 알고리즘을 나타냅니다.

• 빅 세타 표기법 (Big Theta notation): 상한과 하한이 동일한 경우, 즉 평균적인 경우를 나타냅니다. 알고리즘의 실행 시간이 특정 함수의 상수배 범위 내에 있다는 것을 의미합니다. Θ(n)은 입력 크기 n에 비례하여 실행 시간이 증가하는 알고리즘이며, 그 증가율이 n과 동일한 차수를 가짐을 의미합니다.

점근 표기법은 알고리즘 분석 외에도 자료 구조, 데이터베이스, 운영체제 등 다양한 컴퓨터 과학 분야에서 널리 사용됩니다. 알고리즘의 복잡도를 간결하게 표현하고, 성능을 예측하는 데 중요한 도구입니다.