빅오 표기법 편집하기

'''빅오 표기법'''(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-완전 문제의 완전 탐색
==빅오 표기법의 특징==
*최악의 경우를 기준으로 알고리즘의 성능을 분석함.
*상수 계수 및 낮은 차수의 항을 무시하여 대략적인 성능을 표현함.
*알고리즘 간의 성능 비교 및 최적화 시 중요한 기준이 됨.
==예제==
다음은 특정 알고리즘의 빅오 표기법을 설명하는 예제이다.<syntaxhighlight lang="python">
def linear_search(arr, target):
    for i in range(len(arr)):  # O(n)
        if arr[i] == target:
            return i
    return -1
</syntaxhighlight>위 코드에서 최악의 경우 모든 요소를 순회해야 하므로 시간 복잡도는 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.
[[Category:알고리즘]]