시간복잡도 분석으로 알고리즘 확장성 판단하기

입력이 커질수록 드러나는 알고리즘의 비용

알고리즘 선택과 시스템 용량 계획에서는 입력 크기가 변할 때 실행 시간이 어떤 비율로 늘어나는지 파악해야 한다. 시간복잡도 분석은 이 성장률을 정량화해 설계 단계에서 병목을 찾고, 확장성 목표를 검토하는 기준을 제공한다.

시간복잡도는 입력 크기 n에 대한 실행 시간의 점근적 성장률을 나타낸다. 상수 계수와 하위 항은 제거하고 지배적인 성장 차수로 비교한다. 이때 n이 레코드 수인지, 그래프의 정점·간선 수인지, 문자열 길이인지 먼저 분명히 해야 한다. 비교, 교환, 해시, 산술처럼 무엇을 기본 연산으로 볼지도 함께 정한다.

표기법은 상한을 뜻하는 O, 하한의 Ω, 동치를 나타내는 Θ, 엄격 비교를 위한 o와 ω를 사용한다. 분석 결과에는 최악, 평균, 최선 중 어느 경우를 말하는지도 드러나야 한다.

점근 표기만으로는 충분하지 않은 이유

지배항은 성장률을 비교하는 일관된 기준이지만, 작은 입력에서는 상수 비용이나 메모리 계층의 영향이 더 클 수 있다. 빅오가 실제 판단에 유효해지는 임계점도 고려 대상이다.

기본 비용 모델로는 단위 연산 비용이 균일하다고 가정하는 RAM 모델을 많이 쓴다. 그러나 실제 환경에서는 캐시와 메모리 계층, I/O를 반영하는 External Memory 모델, 병렬성을 다루는 PRAM 모델처럼 문제에 맞는 모델을 골라야 한다. 데이터 지역성, 분기 예측, 캐시 미스는 실제 실행 시간에 영향을 준다.

입력 분포와 적대적 입력 가능성도 분석 범위에 넣는다. 동적 배열 확장이나 해시 재해싱처럼 개별 연산의 비용이 흔들리는 경우에는 연속 연산의 평균 비용을 보는 상각 분석이 필요하다. 확률적 알고리즘은 기대 시간과 분산을 제시하고, Tail-risk가 있다면 보호 조치를 검토한다.

해시 테이블은 평균적으로 O(1)이지만 최악에는 O(n)이 될 수 있다. 균형 트리는 O(log n) 연산을 제공해 일관성 측면에서 장점이 있다. 동시성 환경에서는 락 경합과 컨텐션이 유효 복잡도를 악화시킬 수 있으므로 락-프리, 샤딩, 배치 전략도 함께 고려한다.

재귀식에서 성장률을 끌어내는 방법

분할정복 알고리즘은 보통 T(n)=aT(n/b)+f(n) 형태의 재귀식으로 표현한다. 이 식을 세운 뒤 마스터 정리의 적용 조건인 정수 a, b, 다항형 f(n)을 확인한다.

조건이 맞지 않으면 재귀 트리나 치환법을 사용한다. 아크라–바지라니(최신 정보 확인 필요) 같은 대안도 활용할 수 있다. 반복 구조는 루프 횟수와 합을 계산해 성장률을 정리하며, 확률적·랜덤화 알고리즘은 기대값과 분산을 분석 대상으로 삼는다.

복잡도 등급이 운영에 미치는 차이

복잡도 등급	성능(소규모 n)	확장성(대규모 n)	일관성(입력 민감도)	안정성(스파이크 대응)	운영 편의
O(1)	매우 우수	매우 우수	매우 높음	매우 높음	단순 운영
O(log n)	우수	우수	높음	높음	인덱스/트리 관리 필요
O(n)	보통	양호	보통	보통	스트리밍/배치 적합
O(n log n)	보통	양호	보통	보통	정렬/분산 셔플 비용 관리
O(n^2)	취약	부적합	높음	취약	입력 제한·프루닝 필요
O(2^n)/O(n!)	매우 취약	불가	매우 높음	매우 취약	근사/휴리스틱 전환 필요

⤢✕

비용 모델이 맞지 않으면 모델 선택부터 다시 검토한다. 지배항을 잘못 판단했거나 상수 영향을 과도하게 무시했다면 실측 결과로 보정한다.

운영 경로에서 복잡도를 점검하는 자리

백엔드와 데이터베이스에서는 인덱스 유무에 따라 검색이 O(log n)에서 O(n)으로 바뀔 수 있다. 다중 컬럼 인덱스의 선택성을 평가하고, NLJ·Hash·Merge 조인의 복잡도 차이와 통계 최신화 상태를 함께 본다. 페이지네이션은 LIMIT/OFFSET 대신 커서 기반 방식을 적용할 수 있다.

ETL, MapReduce, Spark 같은 배치·분산 처리에서는 정렬과 셔플의 O(n log n) 비용이 병목이 되기 쉽다. 파티셔닝, 프루닝, 프리-어그리게이션으로 n을 줄이고, 외부 정렬과 I/O 모델도 반영한다. 스필과 디스크 정렬의 임계점을 산정한 뒤 메모리를 조정한다.

프론트엔드와 모바일에서는 중첩 루프와 DOM 재계산을 피하는 방식으로 O(n^2)를 O(n)으로 낮출 수 있다. 가상 스크롤과 배치 업데이트를 적용하고, Diffing과 검색 경로에는 해시 또는 트라이를 도입한다. 디바운스와 스로틀은 호출 수를 줄이는 수단이다.

분석 결과를 실측과 연결하기

분석은 문제를 정식화하는 단계에서 시작한다. 입력 크기, 기본 연산, 입력 분포, SLO를 정하고 최악·평균·상각 가운데 어떤 결과를 목표로 할지 결정한다.

그다음 루프 카운팅, 재귀식, 마스터 정리로 Θ 결과를 도출하고 사용한 모델과 가정을 기록한다. 마지막으로 입력을 두 배로 확장하는 테스트를 수행하면서 p50/p95를 수집한다. 캐시, GC, I/O처럼 측정을 교란하는 요인은 통제한다.

O(n^2)에서 O(n log n)으로 교체하면 동일 트래픽에서 인스턴스를 30~60% 절감할 수 있는 사례가 있다. 지연시간은 p95 300ms에서 120ms 수준으로 개선될 수 있으며, 이는 샘플 기준이고 워크로드에 의존한다. 가정과 경계값을 명시하는 습관은 리그레션을 예방하고, 용량 계획과 코스트 모델링의 정확도를 높인다.

실행 시간을 이용한 경험적 복잡도 추정

전제조건: Python 3.10+ (표준 라이브러리), macOS/Linux/Windows, 터미널 실행.

import time, statistics, math

def work_linear(n):
    s = 0
    for i in range(n):
        s += i
    return s

def work_nlogn(n):
    s, m = 0, 1
    while m < n:
        for i in range(n):
            s += i
        m *= 2
    return s

def work_quadratic(n):
    s = 0
    limit = int(math.sqrt(n))  # 안전 실행을 위한 축소
    for i in range(limit):
        for j in range(limit):
            s += i + j
    return s

def time_fn(fn, n, repeats=5):
    times = []
    for _ in range(repeats):
        t0 = time.perf_counter()
        fn(n)
        times.append(time.perf_counter() - t0)
    return statistics.median(times)

models = {
    "O(1)": lambda n: 1,
    "O(log n)": lambda n: math.log(n or 1, 2),
    "O(n)": lambda n: n,
    "O(n log n)": lambda n: n * math.log(n or 1, 2),
    "O(n^2)": lambda n: n ** 2,
}

def guess_complexity(ns, ts):
    # 최소제곱 오차로 모델 적합
    errors = {}
    for name, f in models.items():
        xs = [f(n) for n in ns]
        # 단순 선형 회귀: t ≈ a * x
        denom = sum(x*x for x in xs) or 1e-12
        a = sum(x*t for x, t in zip(xs, ts)) / denom
        preds = [a * x for x in xs]
        err = math.sqrt(sum((p - t)**2 for p, t in zip(preds, ts))) / (sum(ts)/len(ts))
        errors[name] = err
    return sorted(errors.items(), key=lambda kv: kv[1])

def demo(fn, label):
    ns = [2_000, 4_000, 8_000, 16_000, 32_000]
    if label == "quadratic":
        ns = [500, 1_000, 2_000, 3_000, 4_000]
    ts = [time_fn(fn, n) for n in ns]
    ranking = guess_complexity(ns, ts)
    print(f"\n{label} ns={ns}")
    print(f"times={['%.4f' % t for t in ts]}")
    print("fit:", ranking[:3])

if __name__ == "__main__":
    demo(work_linear, "linear")
    demo(work_nlogn, "nlogn")
    demo(work_quadratic, "quadratic")

인터프리터의 상수 비용, 캐시, CPU 부하에 따른 노이즈가 있으므로 이 코드는 상대 비교와 경향 파악 용도로 사용한다. 핵심 경로의 O(n^2) 및 지수적 알고리즘을 제거하고 자료구조 선택을 계속 점검해야 예측 가능한 확장성을 확보할 수 있다.