Big O·Ω·Θ 표기법으로 알고리즘 성장률 경계 읽기

성능의 절대값 대신 성장률을 본다

점근적 표기법은 알고리즘 성능을 수학적 경계로 표현하는 방식이다. 설계, 최적화, 용량 계획에서 같은 비용 증가율을 말하기 위한 공통 언어가 되며, 비용함수를 상한·하한·정확 경계로 나눠 복잡도를 다룬다.

입력이 충분히 커지는 구간에서는 상수 계수와 저차항보다 증가율이 중요하다. 하드웨어나 언어에 따른 상수 비용 차이는 일단 분리하고, 입력 규모가 커질 때 무엇이 병목이 되는지에 집중한다.

상한을 표현하는 Big O

f(n) ∈ O(g(n)) ⇔ ∃ c>0, n0 such that ∀ n≥n0, f(n) ≤ c·g(n).

Big O는 충분히 큰 n에서 비용함수의 상한을 보장한다. 최악 또는 임의 경우의 비용을 다룰 때 쓰며, 과대평가될 수 있지만 과소평가 위험은 낮다. 최악 시간, 용량 상한, SLA 상한 예산을 잡는 데 적합하다.

피할 수 없는 비용을 보는 Big Ω

f(n) ∈ Ω(g(n)) ⇔ ∃ c>0, n0 such that ∀ n≥n0, f(n) ≥ c·g(n).

Big Ω는 비용의 하한을 보장한다. 베스트케이스나 필연적인 최소 비용을 논의할 때 사용하며, 과소평가 위험은 없지만 과대평가 가능성은 있다. 성능 개선의 한계와 이론적 최소 자원 요구량을 도출하는 근거가 된다.

증가율이 일치할 때의 Big Θ

f(n) ∈ Θ(g(n)) ⇔ f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n)).

Big Θ는 상한과 하한이 같은 증가율로 수렴한다는 뜻이다. 대표 성장률 등급을 확정할 수 있으므로 알고리즘 클래스를 구분하거나 대규모 입력에서의 스케일링 특성을 판단할 때 쓴다.

성장률은 충분히 큰 n을 기준으로 1 < log n < n < n log n < n^2 < 2^n < n!처럼 비교할 수 있다. 더 엄격한 비교가 필요하면 비타이트 경계인 little-o와 little-ω도 사용한다. o는 엄격한 상한, ω는 엄격한 하한을 뜻한다.

비용함수에서 운영 판단까지

분석은 먼저 문제 크기를 어떻게 정의할지 정하는 일에서 시작한다. 레코드 수 n, 차원 d, 제약 k처럼 파라미터를 두고, 비교·할당·메모리 접근·IO 호출 가운데 무엇을 기본 연산으로 볼지 정한다.

이후 반복문과 재귀 구조를 전개해 T(n)을 만들고, 지배항을 추출한다. 저차항과 상수항을 제거하면서 로그·다항·지수 항을 구분한다. c, n0를 명시해 O와 Ω 경계를 각각 증명하고, 두 결과가 맞으면 Θ로 통합한다. 극한비교, 수학적 귀납, 분할정복의 마스터 정리가 이 단계에 활용된다.

최악·평균·amortized(평균화) 복잡도는 서로 분리해 적어야 하며, 데이터 분포와 접근 패턴에 대한 가정도 함께 남겨야 한다. 작은 n에서는 캐시, 분기 예측, IO 지연 같은 상수 요인이 결과를 바꿀 수 있으므로 실측으로 보정하고 임계점 n0를 확인한다.

⤢✕

분석 결과는 O·Ω·Θ 복잡도만으로 끝나지 않는다. 임계점 n0, 설계와 용량 계획에 쓸 가이드, 검증이 성립하는 전제조건까지 함께 출력해야 운영 판단에 사용할 수 있다.

경계 표기별 판단 기준

표기법	경계 의미	확장성 예측 적합성	일관성·안정성	운영 편의·증명 난이도
O	충분히 큰 n에서의 상한 보장	보수적 예측에 적합	과소추정 위험 낮음	비교적 용이
Ω	충분히 큰 n에서의 하한 보장	낙관적 한계 파악에 적합	과대평가 가능	비교적 용이
Θ	상·하한이 같은 정확 경계	대표 성장률 확정에 최적	예측 안정성 높음	중간~높음

설계와 운영에서 복잡도를 쓰는 자리

용량 계획에서는 O 기준의 상한 부하 예측으로 CPU, 메모리, 스토리지 프로비저닝 규모를 산정하고 트래픽 피크를 위한 버퍼 용량을 확보할 수 있다.

알고리즘과 자료구조를 선택할 때는 해시맵 평균 Θ(1)과 트리맵 Θ(log n)의 차이, B-Tree와 Hash 인덱스의 선택을 함께 검토한다. 정렬 알고리즘을 O(n^2)에서 O(n log n)으로 바꾸는 판단도 같은 방식으로 설명된다.

SLA·SLO에서는 최악 경로의 O 경계를 바탕으로 타임아웃, 큐 크기, 배치 크기를 설정한다. 경계 초과 위험에는 서킷 브레이커와 백프레셔 정책을 연결할 수 있다.

분산 환경에서는 셔딩의 키스페이스 균등성 가정 아래 평균 복잡도를 검증하고, 맵리듀스나 스파크 잡은 단계별 O 분석으로 shuffle 병목을 찾는다. 성능 회귀 테스트에도 입력 크기 스윕을 적용해 O 추정의 변화를 감지하고, 성장률 기준을 릴리스 게이트에 넣을 수 있다.

성장률 개선이 남기는 효과

O(n^2)에서 O(n log n)으로 전환하면 n=1,000,000에서 연산량은 약 1e12에서 2e7로 감소하며, 약 50,000배 축소된다. 동일 하드웨어에서 처리량은 수십~수백 배 개선될 수 있고, 클라우드 비용 70% 이상 절감 사례도 기대할 수 있다. 피크 부하에서는 타임아웃·재시도 비율과 오류율, 스로틀링 이벤트를 줄이는 방향으로 이어진다.

수치 외에도 설계 의사결정의 일관성을 확보하고 부서 간 커뮤니케이션을 위한 표준 언어를 만들 수 있다. 성능 리스크를 조기에 발견해 기술부채를 예방하고, 튜닝 우선순위를 분명히 하는 데 도움이 된다.

신규 설계와 리팩터링 모두에서 Θ 수준의 목표를 세우고 O 상한을 관리해야 한다. 최악·평균·amortized 복잡도를 구분한 뒤 실측과 결합할 때, 이론적 분석은 운영 관점에서도 신뢰할 수 있는 기준이 된다.