최종 업데이트: 2026-06-23

빅오 성장률

빅오(Big-O) 표기법은 알고리즘의 자원 요구량이 입력 크기에 따라 어떻게 증가하는지를 분류합니다. 특정 기계에서의 실행 시간을 측정하는 대신, 성장의 형태를 포착합니다. n이 두 배가 될 때 작업량도 두 배가 됩니까, 아니면 네 배가 됩니까? 아래의 여섯 가지 복잡도는 교과서와 기술 면접에서 가장 자주 접하는 클래스입니다.

6가지 주요 복잡도 클래스

O(log n) — 로그. 각 단계마다 남은 작업의 일정 비율이 제거됩니다. 10억 개의 요소가 정렬된 배열에서 이진 탐색은 단 30번의 비교만으로 충분합니다. 각 단계마다 탐색 공간을 절반으로 줄이기 때문입니다. 균형 이진 탐색 트리(BST) 조회와 많은 분할 정복 점화식이 여기에 해당합니다.

O(n) — 선형. 작업량이 입력 크기에 정비례하여 증가합니다. 배열을 한 번 순회하여 최댓값을 찾거나, 문자열에서 문자를 세거나, 목록의 모든 요소를 읽는 작업이 선형입니다. 선형 알고리즘은 일반적으로 효율적으로 간주됩니다.

O(n log n) — 선형 로그. 정렬에서 가장 흔한 복잡도입니다. 병합 정렬, 힙 정렬, Timsort(Python과 Java에서 사용)는 모두 O(n log n)으로 실행되며, 이는 비교 기반 정렬의 이론적 하한이기도 합니다. $n = 10^6$에서 약 2,000만 번의 연산에 해당하므로 실제로 충분히 빠릅니다.

O(n²) — 이차. 입력에 대한 두 개의 중첩 반복문이 특징입니다. 버블 정렬, 삽입 정렬, 순진한 행렬 곱셈이 모두 O(n²)의 최악 경우를 가집니다. $n = 10^4$에서는 1억 번의 연산이 필요하고, $n = 10^6$에서는 1조 번이 되어 대규모 데이터에는 비실용적입니다.

O(2ⁿ) — 지수. 요소가 하나 추가될 때마다 작업량이 두 배가 됩니다. 순진한 재귀 피보나치 알고리즘은 부분 문제를 지수적으로 재계산하며, 집합의 모든 부분집합에 대한 무차별 열거도 $2^n$으로 증가합니다. n = 40에서 이 수는 1조를 초과합니다.

O(n!) — 계승. 일상적인 알고리즘 분석에서 가장 빠르게 성장하는 클래스입니다. 외판원 문제(TSP)의 무차별 대입 방식은 가능한 모든 순열을 열거하며, 순열의 수는 $n!$개입니다. n = 20에서 이 수는 200경을 초과합니다.

n = 20에서의 계산 예시

$\log_2 20 \approx 4.32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86.4$

$20^2 = 400 \quad\quad 2^{20} = 1{,}048{,}576 \quad\quad 20! \approx 2.43 \times 10^{18}$

n = 20에서 O(n log n)과 O(n!)의 비율은 약 $10^{16}$으로, 빠른 정렬과 우주의 나이보다 긴 대기 시간의 차이입니다.

실용적 지침

소규모 n에서는 상수와 캐시 효과가 중요하지만, n이 커질수록 복잡도가 지배적입니다. 단순 연산을 가정할 때 O(n²)이 현대 하드웨어에서 불편해지기 시작하는 대략적인 임계값은 n = 10,000입니다. n = 10^6 이상에서는 일반적으로 O(n log n) 이하의 알고리즘이 필요합니다. 지수 및 계승 알고리즘은 실제 입력에 대해 근사 알고리즘, 동적 프로그래밍, 또는 가지치기 전략이 필요합니다.

입력 공간의 이진 표현을 다루는 경우 진법 변환기가 유용합니다.