CS학습2026년 8월 19일

Big-O 표기법: 알고리즘 효율성을 나타내는 지표

Big-O 표기법은 알고리즘의 입력 크기에 따른 실행 시간 또는 공간 복잡도를 나타내는 수학적 표기법입니다. 알고리즘의 성능을 비교하고, 효율적인 알고리즘을 선택하는 데 도움을 줍니다. 특히 입력 데이터의 크기가 커질수록 알고리즘의 효율성이 중요해지기 때문에 Big-O 표기법은 필수적인 개념입니다.

송민성4분 읽기

1. 개념

Big-O 표기법은 알고리즘의 *최악의 경우* 성능을 설명하는 데 사용됩니다. 구체적으로, 입력 크기(n)가 증가함에 따라 알고리즘의 실행 시간 또는 사용하는 메모리 공간이 어떻게 증가하는지를 나타냅니다. Big-O는 알고리즘의 정확한 실행 시간을 측정하는 것이 아니라, 입력 크기가 매우 커질 때의 *증가 추세*를 분석하는 데 초점을 맞춥니다.

2. 왜 사용하는가

알고리즘 성능 비교: 여러 알고리즘의 효율성을 객관적으로 비교할 수 있습니다.
병목 지점 파악: 코드에서 성능 저하를 일으키는 부분을 찾아 개선할 수 있습니다.
확장성 예측: 입력 데이터 크기가 커질 때 알고리즘이 어떻게 동작할지 예측하여 시스템의 확장성을 고려할 수 있습니다.
효율적인 알고리즘 선택: 문제 해결에 적합한 알고리즘을 선택하여 최적의 성능을 얻을 수 있습니다.

3. 동작 원리

Big-O 표기법은 점근적 표기법(asymptotic notation)의 일종입니다. 점근적 표기법은 입력 크기가 무한대로 커질 때 함수의 증가율을 나타냅니다.

가장 흔히 사용되는 Big-O 표기법은 다음과 같습니다.

O(1) - 상수 시간(Constant Time): 입력 크기에 관계없이 실행 시간이 일정합니다.
O(log n) - 로그 시간(Logarithmic Time): 입력 크기가 증가함에 따라 실행 시간이 로그 함수적으로 증가합니다. (이진 탐색 등)
O(n) - 선형 시간(Linear Time): 입력 크기가 증가함에 따라 실행 시간이 선형적으로 증가합니다. (단순 반복문 등)
O(n log n) - 선형 로그 시간(Linear Logarithmic Time): (병합 정렬, 퀵 정렬 등)
O(n^2) - 제곱 시간(Quadratic Time): 입력 크기가 증가함에 따라 실행 시간이 제곱으로 증가합니다. (이중 반복문 등)
O(2^n) - 지수 시간(Exponential Time): 입력 크기가 증가함에 따라 실행 시간이 지수적으로 증가합니다. (피보나치 수열 재귀적 구현 등)
O(n!) - 팩토리얼 시간(Factorial Time): 가장 느린 알고리즘 중 하나입니다. (모든 순열 생성 등)

4. 코드 예제

python

# O(n) - 선형 시간
def find_max(arr):
    max_val = arr[0]
    for i in range(1, len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

# O(n^2) - 제곱 시간
def find_duplicates(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                duplicates.append(arr[i])
    return duplicates

5. 시간 복잡도 또는 성능 특성

Big-O 표기법은 최악의 경우를 기준으로 하지만, 평균 시간 복잡도와 최적 시간 복잡도도 고려할 수 있습니다.

최악의 경우(Worst-case): 모든 입력에 대해 가장 오래 걸리는 경우
평균의 경우(Average-case): 일반적인 입력에 대해 예상되는 실행 시간
최선의 경우(Best-case): 가장 빠르게 실행되는 경우

6. 실무 사용 사례

데이터베이스 쿼리 최적화: 쿼리 실행 계획을 분석하여 Big-O 표기법을 기반으로 성능을 개선합니다.
API 응답 시간 개선: 알고리즘의 복잡도를 줄여 API 응답 시간을 단축합니다.
대용량 데이터 처리: 효율적인 알고리즘을 선택하여 대용량 데이터 처리 성능을 향상시킵니다.
웹 애플리케이션 성능 최적화: 사용자 경험을 개선하기 위해 웹 애플리케이션의 성능을 최적화합니다.

7. 주의할 점

상수 무시: Big-O 표기법은 상수항을 무시합니다. O(2n)과 O(n)은 동일하게 취급됩니다. 중요한 것은 입력 크기가 커질 때의 증가 추세입니다.
숨겨진 상수: Big-O 표기법은 숨겨진 상수를 고려하지 않습니다. O(n) 알고리즘이라도 숨겨진 상수가 크면 실제 성능이 나쁠 수 있습니다.
공간 복잡도: Big-O 표기법은 시간 복잡도뿐만 아니라 공간 복잡도(알고리즘이 사용하는 메모리 공간)를 나타낼 수도 있습니다.
실제 측정: Big-O 표기법은 이론적인 분석이지만, 실제 성능은 하드웨어, 운영체제, 프로그래밍 언어 등 다양한 요인에 영향을 받습니다.

8. 핵심 정리

Big-O 표기법은 알고리즘의 효율성을 평가하는 강력한 도구입니다. 알고리즘을 선택하고 성능을 개선하는 데 활용하여 더 나은 소프트웨어를 개발할 수 있습니다. 알고리즘의 시간 복잡도를 이해하고, 입력 데이터 크기에 따른 성능 변화를 예측하는 것은 매우 중요합니다.