시간 복잡도와 점근적 분석: Big-O·Theta·Omega의 실무 기준
시간 복잡도와 점근적 분석의 비용 모델, Big-O·Big-Theta·Big-Omega 표기, 용량 계획과 성능 설계 활용 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
입력이 커질 때 무엇이 병목이 되는지 판단하는 법
시간 복잡도는 입력 크기 n에 따라 실행 시간 함수 T(n)이 어떻게 증가하는지 보는 분석이다. 상수항과 낮은 차수항을 걷어내면, 구현 세부사항보다 알고리즘 구조가 성능에 미치는 영향을 비교하기 쉬워진다.
점근적 분석(Asymptotic Analysis)은 n → ∞에서 지배항이 보이는 경향을 다룬다. 하드웨어, 캐시, 분기 예측 같은 구현 수준의 차이는 이 단계에서 노이즈 비중을 낮춘다.
Big-O, Big-Theta, Big-Omega는 같은 성능 문제를 서로 다른 경계로 설명한다.
- Big-O는 상한(Upper Bound)이다.
c > 0,n0 ≥ 1이 존재하여 모든n ≥ n0에서T(n) ≤ c·g(n)이면 성립한다. 최악 사례나 상한 보증이 필요할 때 쓴다. - Big-Theta는 정확 경계(Tight Bound)다.
c1, c2 > 0,n0 ≥ 1이 존재하고c1·g(n) ≤ T(n) ≤ c2·g(n)을 만족할 때 성장률을 정확히 특성화한다. - Big-Omega는 하한(Lower Bound)이다.
c > 0,n0 ≥ 1에 대해T(n) ≥ c·g(n)을 만족하면 된다. 최소 비용이나 알고리즘이 도달할 수 있는 최선의 한계를 표현한다.
분석 대상은 최악·평균·최선 사례로 나뉜다. 각각 Tworst(n), Tavg(n), Tbest(n)으로 정의하며, 평균 사례는 확률적 입력 분포를 가정해야 도출할 수 있다.
비용 모델과 입력 가정이 분석의 출발점이다
기본적인 분석은 RAM 모델을 가정하고 비교, 할당, 메모리 접근 같은 기본 연산의 비용을 상수로 둔다. 캐시, 브랜치, I/O는 1차 분석에서 제외한다. 다만 계산 중심인지 I/O 중심인지, 어느 정도 정밀도가 필요한지, 상수를 보정할 수 있는 환경인지에 따라 비용 모델은 달라질 수 있다.
입력의 정렬도, 중복도, 그래프 밀도 같은 특성과 분포 가정도 함께 명시해야 한다. 평균 사례는 이 가정 위에서만 의미를 갖는다. 보안·실시간 시스템처럼 최악 사례 방어가 필요한 환경과, 배치·분석 파이프라인처럼 평균 사례 최적화가 유효한 환경은 같은 복잡도 표기를 보더라도 판단 기준이 다르다.
점근 환산에서는 지배항만 남기고 상수배와 하위항을 제거한다. 다항식은 최고차항을 우선하며, 성장률은 log n < n < n log n < n^2 < 2^n 순으로 비교한다. 재귀식은 마스터 정리나 재귀 트리로 환산하고, 확률적 알고리즘에는 기대값 기반 평균 분석을 적용한다.
시간과 공간은 별개로 볼 수 없다. 해시 테이블은 공간 O(n)을 사용하는 대신 조회 O(1) 기대를 얻는 선택이며, 캐시 지역성도 같이 고려해야 한다. 병렬 환경에서는 Work-Span, PRAM 모델로 T1(총 작업)과 T∞(임계 경로)를 분석하고, Amdahl/Gustafson 법칙으로 확장성을 예측한다.
경계 표기가 의사결정에 쓰이는 방식
| 기준 | Big-O (상한) | Big-Theta (정확 경계) | Big-Omega (하한) |
|---|---|---|---|
| 성능 평가 | 최악 비용 상한 보증, 리스크 노출 억제 | 성장률 동등성 판정, 설계 비교 기준 | 최소 비용 한계 파악, 낙관적 기대치 설정 |
| 확장성 | 보수적 용량 계획, 버스트 대비 유리 | 평균적 확장 동작 예측 | 데이터 특성 좋을 때의 잠재 확장성 |
| 일관성 | 입력 변동에도 보수적 일관성 유지 | 입력 분포가 안정적일 때 높은 일관성 | 분포 변화에 민감, 일관성 낮음 |
| 안정성 | SLO 위반 방지에 기여 | 이론적 균형, 실무 안정성은 분포 의존 | 낙관치 위험, 방어적 운영에는 부적합 |
| 운영 편의 | 커뮤니케이션 용이, 경영진 보고 적합 | 알고리즘 전문가 간 비교 용이 | 연구·하한 증명에 유용, 실무 소통 난이도 |
Big-O는 상한 보증과 위험 관리에 적합해 서비스 SLO/SLA 설계에 쓰기 좋다. Big-Theta는 설계 대안을 비교할 때 실질적으로 성장률이 같은지 판단하는 기준선이 된다. Big-Omega는 하한·불가능성 증명이나 데이터 친화적 최선 사례를 확인할 때 유용하다.
코드 리뷰부터 용량 계획까지 이어지는 분석
코드 리뷰와 설계 승인에서는 먼저 n이 레코드 수인지, 노드 수인지, 입력 길이인지 정하고 입력 분포 가정을 남긴다. 핵심 루프와 재귀의 연산 수를 세어 T(n)을 구성한 뒤 지배항을 산출한다. 요구사항에 맞는 O·Θ·Ω 표기를 고르고 근거를 문서화한다. 샘플 입력으로 벤치마크를 실행해 상수와 캐시 효과를 보정하고, 목표 복잡도를 충족하지 못하면 자료구조 교체, 알고리즘 변경, 캐싱 같은 대안을 게이팅에 올릴 수 있다.
데이터베이스에서는 인덱스와 조인 전략의 차이가 곧 복잡도 차이다. B-Tree 탐색은 O(log n), 해시 인덱스는 O(1) 기대이며, 범위 질의에서는 B-Tree가 우위다. 해시 조인은 O(n + m), 정렬-병합 조인은 O(n log n + m log m), 중첩 루프 조인은 O(n·m)이다. 통계가 실제 데이터와 어긋나면 평균 사례 가정도 무너질 수 있으므로 히스토그램과 샘플링으로 실행 계획을 보정한다.
마이크로서비스와 큐 기반 시스템에서는 요청 라우팅과 큐 연산의 복잡도가 용량 계획에 연결된다. 일관 해싱은 O(1) 기대이고 재배치 비용은 O(k/n)이지만, 분산 키 스큐가 발생하면 평균 사례가 붕괴할 수 있다. 우선순위 큐 힙은 O(log n), 단순 큐는 O(1)이며, 지연에 민감한 워크로드에서는 자료구조 교체를 검토할 수 있다. O(n log n)에서 O(n)으로 개선하면 n=10^7에서 이론상 약 23배, 상수 영향을 반영하면 체감 3~10배 지연 감소를 기대할 수 있다.
배치·스트리밍 파이프라인에서는 전체 정렬 O(n log n) 대신 Quickselect 기대 O(n)과 소규모 힙 정렬 O(k log k)을 조합해 Top-K를 계산할 수 있다. 슬라이딩 윈도우 집계를 증분 계산으로 바꾸면 윈도우당 O(w)에서 O(1) 기대로 전환된다. 메모리를 초과하는 경우에는 런 길이와 버퍼 크기를 포함한 I/O 패턴을 함께 최적화하며 외부 정렬 O(n log n)을 다룬다.
분석과 검증을 반복하는 흐름
분석 결과를 운영 판단에 연결하려면 비용 모델 정의, 경계 목표 선택, 경험 검증을 반복하는 루프가 필요하다. 표기 자체만 문서에 남기기보다 가정, 적용 범위, 리스크, 개선 권고를 함께 결과물로 남겨야 한다.
O(n log n)에서 O(n)으로 전환하면 n=10^7에서 이론상 ~23배, 실측 3~10배 처리량 개선을 기대할 수 있다. 동일 하드웨어 기준으로 배치 작업 시간은 50~80% 단축되고 클러스터 노드는 20~40% 축소될 수 있다. 사전 분석과 보정 루프를 도입하면 p95 지연 예측 오차는 30~60% 감소할 수 있다.
표준 표기와 가정을 문서화하면 리뷰 일관성이 높아지고, 최악 사례 중심의 상한 분석은 SLO 위반 위험을 낮춘다. 조직 안에서 성능을 설명하는 언어가 통일되면 협업 효율도 높아진다. 평균 사례 최적화와 최악 사례 방어 사이의 균형을 잡고, 상수·캐시·I/O를 보정하는 절차를 병행하는 것이 조직적 적용의 기반이다.