빅오 표기법

빅오 표기법(Big-O Notation)은 알고리즘의 시간 복잡도와 공간 복잡도를 분석하는 데 사용되는 수학적 표기법이다. 주어진 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타내며, 최악의 경우 성능을 분석하는 데 주로 사용된다.

개요

빅오 표기법은 알고리즘의 성능을 대략적으로 분석할 때 활용되며, 주요 목적은 입력 크기가 커질수록 실행 시간이 어떻게 변화하는지를 평가하는 것이다. 빅오 표기법은 상수 계수를 무시하고, 가장 높은 차수의 항만을 고려하여 표현된다.

주요 시간 복잡도

빅오 표기법에서 자주 사용되는 시간 복잡도는 다음과 같다.

• O(1) - 상수 시간 (Constant Time)
  • 입력 크기와 관계없이 실행 시간이 일정함.
  • 예시: 배열에서 특정 인덱스의 값을 조회하는 연산

• O(log n) - 로그 시간 (Logarithmic Time)
  • 입력 크기가 증가할 때 실행 시간이 로그 형태로 증가함.
  • 예시: 이진 탐색 (Binary Search)

• O(n) - 선형 시간 (Linear Time)
  • 입력 크기에 비례하여 실행 시간이 증가함.
  • 예시: 배열의 모든 요소를 순회하는 연산

• O(n log n) - 선형 로그 시간 (Linearithmic Time)
  • 입력 크기에 로그 값을 곱한 형태로 실행 시간이 증가함.
  • 예시: 병합 정렬 (Merge Sort), 퀵 정렬 (Quick Sort) 평균 및 최적의 경우

• O(n²) - 이차 시간 (Quadratic Time)
  • 입력 크기의 제곱에 비례하여 실행 시간이 증가함.
  • 예시: 버블 정렬 (Bubble Sort), 선택 정렬 (Selection Sort)

• O(2ⁿ) - 지수 시간 (Exponential Time)
  • 입력 크기에 대해 지수적으로 실행 시간이 증가함.
  • 예시: 피보나치 수열의 재귀적 계산

• O(n!) - 팩토리얼 시간 (Factorial Time)
  • 입력 크기가 커질수록 실행 시간이 매우 빠르게 증가함.
  • 예시: 외판원 문제(Travelling Salesman Problem, TSP)와 같은 NP-완전 문제의 완전 탐색

빅오 표기법의 특징

• 최악의 경우를 기준으로 알고리즘의 성능을 분석함.
• 상수 계수 및 낮은 차수의 항을 무시하여 대략적인 성능을 표현함.
• 알고리즘 간의 성능 비교 및 최적화 시 중요한 기준이 됨.

예제

다음은 특정 알고리즘의 빅오 표기법을 설명하는 예제이다.

def linear_search(arr, target):
    for i in range(len(arr)):  # O(n)
        if arr[i] == target:
            return i
    return -1

위 코드에서 최악의 경우 모든 요소를 순회해야 하므로 시간 복잡도는 O(n)이다.

관련 개념

• 세타(Θ) 표기법 - 평균적인 경우의 실행 시간을 나타냄.
• 오메가(Ω) 표기법 - 최선의 경우의 실행 시간을 나타냄.
• 공간 복잡도 - 알고리즘이 사용하는 메모리의 증가율을 분석함.

같이 보기

• 시간 복잡도
• 공간 복잡도
• 알고리즘 분석
• NP-문제

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
• Knuth, D. E. (1997). The Art of Computer Programming. Addison-Wesley.