점근 표기법

점근 표기법(Asymptotic Notation)은 알고리즘의 성능을 수학적으로 표현하는 방법이다. 우리가 어떤 코드를 실행할 때 실제 걸리는 시간은 컴퓨터의 사양, 언어, 환경 등에 따라 달라질 수 있다. 그렇기 때문에 절대적인 “실행 시간” 대신, 입력 크기가 커질 때 알고리즘의 효율성이 어떻게 변하는가를 기준으로 성능을 평가한다. 이때 사용하는 표현 방식이 바로 점근 표기법이다.

점근 표기법은 간단히 말해 “입력값이 커질 때 알고리즘의 실행 시간이 어떤 함수 형태로 증가하는가”를 나타내는 방법이다. 수학적으로는 함수의 증가 양상을 비교하는 개념에서 비롯되었지만, 프로그래밍에서는 알고리즘의 성장률을 표현하는 수단으로 쓰인다. 우리가 지금까지 “이 알고리즘은 N번 반복한다”, “이건 N²번 연산이 필요하다”라고 말했던 것이 바로 점근 표기법을 사용한 분석이다.

점근 표기법에는 대표적으로 빅오(Big-O) 표기법과 빅오메가(Big-Ω) 표기법이 있다. 빅오 표기법은 최악의 경우(worst case)를 기준으로, 알고리즘이 수행해야 하는 최대 연산량을 나타낸다. 반면 빅오메가 표기법은 최선의 경우(best case)를 기준으로, 가장 빠르게 실행될 때의 연산량을 표현한다. 예를 들어 “이 알고리즘은 O(N)의 시간 복잡도를 가진다”라고 하면, 입력 크기가 N일 때 최악의 경우에 N에 비례하는 시간이 걸린다는 뜻이다. 반대로 “Ω(1)”이라면, 최선의 경우에는 한 번의 연산만으로 답을 얻을 수 있다는 의미다.

예를 들어 배열 안에서 특정 숫자가 존재하는지 찾는 문제를 생각해보자.

def is_number_exist(number, array):
    for element in array:
        if number == element:
            return True
    return False

print(is_number_exist(3, [3, 5, 6, 1, 2, 4])) # True
print(is_number_exist(7, [3, 5, 6, 1, 2, 4])) # False

이 함수는 배열을 앞에서부터 하나씩 순회하며 찾고자 하는 숫자와 같은지 비교한다. 만약 찾는 숫자가 배열의 첫 번째 원소라면, 한 번의 비교만으로 True를 반환하고 함수가 종료된다. 이때는 최선의 경우에 해당하므로 Ω(1)의 시간 복잡도를 가진다.

하지만 찾는 숫자가 배열의 맨 끝에 있거나, 존재하지 않는 경우라면 어떨까? 이 경우에는 배열의 모든 원소를 확인해야 하므로, 배열의 길이가 N이라면 N번의 비교 연산이 필요하다. 즉, 최악의 경우에는 O(N)의 시간 복잡도를 가진다.

이처럼 알고리즘의 실행 시간은 입력값의 구성이나 순서에 따라 달라질 수 있다. 어떤 경우에는 빠르게 끝날 수도 있지만, 다른 경우에는 오래 걸릴 수도 있다. 따라서 알고리즘을 분석할 때는 보통 최악의 상황을 기준으로 성능을 평가한다.

그 이유는 명확하다. 대부분의 입력이 최선의 경우일 가능성은 매우 낮고, 실제 프로그램이 다양한 상황에서 안정적으로 동작하려면 최악의 상황에서도 감당 가능한 수준의 성능을 보장해야 하기 때문이다. 그래서 알고리즘 분석에서는 빅오 표기법(Big-O)이 가장 널리 사용된다.

다시 말해, 빅오 표기법은 “이 알고리즘이 얼마나 빠른가?”가 아니라, “입력이 커질수록 얼마나 느려질 수 있는가?”를 보여주는 지표다.

정리하자면, 점근 표기법은 알고리즘의 효율성을 수학적으로 표현하는 방법이며, 빅오(Big-O)는 최악의 경우, 빅오메가(Big-Ω)는 최선의 경우를 나타낸다. 그리고 실무나 코딩 테스트에서는 대부분의 상황을 대비하기 위해 빅오 표기법을 사용한다. 결국 우리가 고민해야 할 것은 “이 알고리즘은 입력이 커질 때 어디까지 버틸 수 있는가”이며, 점근 표기법은 그 답을 가장 명확하게 보여준다.