Zokipedia
Hahwul Logo
Updated November 06, 2025

[Example] 알고리즘 복잡도

Edit this page

효율적이고 확장 가능한 소프트웨어를 만들려면 알고리즘 복잡도를 이해하는 것이 필수입니다. 이 글은 엄밀한 정의와 함께 실무 팁, 흔한 함정, 일상적으로 활용할 수 있는 참조 공식을 한데 모았습니다.

무엇을 측정하나요?

  • 시간 복잡도: 선택한 계산 모델(보통 워드 크기 w = Θ(log n)인 단위 비용 RAM 모델)에서 입력 크기 n에 따라 실행 시간이 어떻게 증가하는가
  • 공간 복잡도: n에 따른 메모리 사용량(피크 또는 추가 공간)
  • 입력 크기: 항목 수 n, 수치의 비트 길이, 그래프의 정점/간선 수 (V, E) 등. 어떤 입력 모델을 쓰는지 항상 명시하세요.

현실적인 주의사항: 같은 점근 복잡도라도 상수, 메모리 지역성, 병렬성, 하드웨어 효과에 따라 실제 실행 시간은 크게 달라질 수 있습니다.

점근 표기법(정의)

f(n), g(n)이 충분히 큰 n에 대해 음이 아닌 함수라고 하겠습니다.

  • Big-O(상한): f(n) = O(g(n)) \iff \exists c>0,\, n_0\ge 1:\ \forall n\ge n_0,\ 0 \le f(n) \le c\,g(n)

  • Big-Ω(하한): f(n) = \Omega(g(n)) \iff \exists c>0,\, n_0:\ \forall n\ge n_0,\ f(n) \ge c\,g(n)

  • Big-Θ(타이트한 경계): f(n) = \Theta(g(n)) \iff f(n)=O(g(n))\ \text{and}\ f(n)=\Omega(g(n))

  • little-o(엄격히 더 작음): f(n) = o(g(n)) \iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0

  • little-ω(엄격히 더 큼): f(n) = \omega(g(n)) \iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty

최악/평균/분할 상환(암ORTized) 경계는 모두 위 표기법으로 표현합니다. 어떤 경우인지 반드시 명시하세요.

자주 쓰는 복잡도 등급(예시 포함)

  • 상수: O(1) — 배열 인덱싱, 스택 push/pop(동적 배열은 분할 상환)
  • 역 아커만: O(α(n)) — 사실상 상수; 경로 압축 + 랭크 합치기의 유니온-파인드
  • 로그: O(log n) — 이진 탐색, 균형 BST의 높이, 2로 나누는 루프
  • 다중 로그: O((\log n)^k) — 다단 인덱스 구조 등
  • 부분 선형: O(√n) — 소인수 시험 상한, 2D 그리드 반경 탐색
  • 선형: O(n) — 단일 패스, 카운팅; 인접 리스트의 BFS는 O(V+E)
  • 선형로그: O(n \log n) — 병합 정렬, 힙 정렬, 평균적 퀵정렬
  • 다항(제곱/세제곱 등): O(n^2), O(n^3), O(n^k) — 독립 차원의 중첩 루프; 고전적 행렬 곱셈 O(n^3)
  • 거의 선형(키 범위 제한): O(n + k) — 작은 정수 범위의 카운팅/기수 정렬; k는 키 범위
  • 준다항: O(2^{(\log n)^c}) — 일부 근사/무작위성 제거 결과
  • 지수: O(c^n) — 부분집합 전수조사, Held–Karp로 정확 TSP O(n^2 2^n)
  • 팩토리얼: O(n!) — 순열 열거

참고: 빠른 곱셈 O(n^{\log_2 3})(Karatsuba), 빠른 행렬 곱 O(n^\omega)(ω < 2.373, 이론적).

최악/평균/분할 상환

  • 최악: 크기 n인 입력 중 가장 느린 경우의 경계
  • 평균: 입력 분포에 대한 기대 복잡도(분포를 명시해야 함)
  • 분할 상환: 가끔 비싼 연산이 있어도 일련의 연산 평균 비용
    • 예: 동적 배열 두 배 확장. n번 append의 총 이동은 < 2n, 따라서 append의 분할 상환 비용은 O(1).
\text{Amortized cost} = \frac{\text{Total cost over } n \text{ ops}}{n}

실측과 추정

복잡도를 실험적으로 검증하는 방법:

  • 워크로드 분리
    • I/O와 로깅 제외, 순수 계산만 측정
    • 워밍업(JIT, 캐시) 후 여러 번 반복 측정
  • 문제 크기 n 변화
    • 로그 스텝(예: n = 2^k)으로 증가, 충분한 데이터 포인트 확보
    • n \log n 후보는 T(n)/n과 \log n을 비교(평평하면 n \log n 가능성)
  • 로그–로그 플롯
    • (x, y) = (\log n, \log T(n))에 직선을 피팅. 기울기 ≈ 다항 차수. s \approx \frac{\log T(n_2) - \log T(n_1)}{\log n_2 - \log n_1}
  • 통계 처리
    • 중앙값 또는 절사 평균 사용, 분산 보고
    • 이상치 제거, CPU 고정, 스로틀링 회피
  • 공간 프로파일링
    • 피크 사용량, 할당 횟수, 원소당 오버헤드 추적
    • GC/할당기 메타데이터, 단편화 고려

주의: 데드 코드 제거, 분기 예측, 프리패치, 캐싱 등으로 마이크로벤치마크가 왜곡될 수 있습니다. 가능하면 프로파일러와 카운터로 검증하세요.

자료구조 요약(일부 연산)

  • 정적 배열
    • 인덱스: O(1)
    • 탐색: 선형 O(n), 정렬+이진 탐색이면 O(log n)
    • 중간 삽입/삭제: 시프트로 O(n)
  • 동적 배열(분할 상환 두 배 확장)
    • 뒤에 추가: 분할 상환 O(1), 리사이즈 순간 최악 O(n)
    • 중간 삽입/삭제: O(n)
  • 단/양방향 연결 리스트
    • 앞에 삽입: O(1), 꼬리 포인터 있으면 뒤에 삽입: O(1), 탐색: O(n), 임의 인덱스: O(n)
  • 스택/큐/데크
    • Push/Pop/Enqueue/Dequeue: 구현에 따라 분할 상환 또는 최악 O(1)
  • 해시 테이블(체이닝/오픈 어드레싱)
    • 평균: 탐색/삽입/삭제 O(1)(건전한 로드 팩터)
    • 최악: O(n)(적대적 충돌)
    • 리사이즈: 가끔 O(n); 연산당 분할 상환 상수
  • 정렬 맵/셋(균형 BST: Red–Black, AVL, B-트리)
    • 탐색/삽입/삭제: O(log n); 전/후임자: O(log n); 순회: O(n)
  • 힙(이진 힙)
    • 최소값: O(1); 삽입: O(log n); 추출: O(log n); 힙 빌드: O(n)
    • decrease-key: O(log n)(피보나치 힙은 분할 상환 O(1)이나 상수 큼)
  • 서로소 집합(유니온–파인드)
    • 경로 압축 + 랭크/사이즈 합치기: 연산당 분할 상환 O(α(n))
  • 트라이/접두 트리(알파벳 크기 σ)
    • 삽입/조회: 키 길이 L에 대해 O(L); 메모리는 커질 수 있음(분기 σ)
  • 블룸 필터
    • 멤버십 테스트(삭제 없음): 시간 O(k), 공간 O(m), 거짓 양성 허용 p \approx \left(1 - e^{-kn/m}\right)^k,\quad k_{\text{opt}} = \frac{m}{n}\ln 2,\quad p_{\min} \approx (0.6185)^{m/n}

그래프 표현:

  • 인접 리스트: 공간 O(V+E); BFS/DFS O(V+E)
  • 인접 행렬: 공간 O(V^2); 간선 존재 확인 O(1)

대표 그래프 알고리즘 비용:

  • BFS/DFS: O(V+E)
  • 다익스트라(음수 가중치 없음): 이진 힙 O((V+E)\log V), 피보나치 힙 O(E + V \log V)
  • 0–1 BFS: 데크로 O(V+E)
  • MST: 크루스칼 O(E \log V), 프림(이진 힙) O(E \log V)

정렬과 선택:

  • 비교 기반 정렬 하한: Ω(n \log n)
  • 병합/힙 정렬: O(n \log n); 퀵정렬: 평균 O(n \log n), 최악 O(n^2)
  • 카운팅/기수 정렬: 키 범위 k에 대해 O(n + k)
  • Quickselect(k번째 순서 통계): 평균 O(n), 최악 O(n^2); median-of-medians로 최악 O(n)

점화식과 핵심 공식

합과 근사:

  • 1부터 n까지의 합: \sum_{i=1}^{n} i = \frac{n(n+1)}{2}

  • 기하급수열: \sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1}\quad (r \ne 1)

  • 조화수: H_n = \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + \Theta\!\left(\frac{1}{n}\right) 여기서 γ는 오일러–마스케로니 상수입니다.

  • 로그 팩토리얼 / 스털링 근사: \log n! = \Theta(n \log n),\quad n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}

점화식 예:

  • 이진 탐색: T(n) = T(n/2) + \Theta(1) \ \Rightarrow\ T(n)=\Theta(\log n)

  • 병합 정렬: T(n) = 2T(n/2) + \Theta(n) \ \Rightarrow\ T(n)=\Theta(n \log n)

  • Karatsuba 곱셈: T(n) = 3T(n/2) + O(n) \ \Rightarrow\ T(n)=O\!\left(n^{\log_2 3}\right)\approx O(n^{1.585})

  • Strassen 행렬 곱: T(n) = 7T(n/2) + O(n^2) \ \Rightarrow\ T(n)=O\!\left(n^{\log_2 7}\right)\approx O(n^{2.807})

마스터 정리(분할 정복): T(n) = a\,T(n/b) + f(n),\ a\ge 1,\ b>1 \\ T(n) = \begin{cases} \Theta\!\left(n^{\log_b a}\right) & \text{if } f(n)=O\!\left(n^{\log_b a - \epsilon}\right) \\ \Theta\!\left(n^{\log_b a}\log n\right) & \text{if } f(n)=\Theta\!\left(n^{\log_b a}\right) \\ \Theta\!\left(f(n)\right) & \text{if } f(n)=\Omega\!\left(n^{\log_b a + \epsilon}\right)\ \text{and regularity holds} \end{cases}

Akra–Bazzi(일반형 직관): 다음 꼴 T(x) = \sum_{i=1}^{k} a_i\,T(b_i x) + g(x) 에서 p를 찾아 \sum a_i b_i^p = 1 을 만족하게 합니다. 그러면 T(x) = \Theta\!\left(x^p\left(1 + \int_{1}^{x} \frac{g(u)}{u^{p+1}}\,du\right)\right)

병렬성: 작업량과 경로 길이

T1을 총 작업량(1코어), T∞를 span/임계 경로(무한 코어)라고 할 때, 프로세서 P개에서는:

  • 하한: T_P \ge \max\!\left(\frac{T_1}{P},\ T_{\infty}\right)
  • 암달의 법칙(고정 작업량, 병렬 가능 비율 P_f): S(N) = \frac{1}{(1-P_f) + \frac{P_f}{N}}
  • 거스타프손의 법칙(스케일된 작업량): S(N) = N - (1-P_f)(N-1)

시사점: 고도로 병렬적인 하드웨어에서는 작업량을 줄이는 것 못지않게 의존성(경로 길이, span)을 줄이는 설계가 중요합니다.

메모리 계층과 I/O 인지

  • 같은 O(n)이라도 지역성, 블록 전송 수에 따라 실제 시간은 수배 차이가 날 수 있습니다.
  • 캐시 인지/캐시 무감 알고리즘은 L1/L2/LLC/DRAM/디스크 사이 전송을 줄이도록 설계합니다.
  • 외부 메모리(I/O) 모델에서는 블록 크기 B, 메모리 크기 M을 두고 캐시 미스와 스캔 수를 최소화하는 게 목표입니다.

흔한 함정

  • 상수·메모리 무시: 무작위 접근의 O(n)이 연속 접근의 O(n \log n)보다 느릴 수 있음
  • 기준 불일치 비교: A의 평균과 B의 최악을 비교
  • 분포 가정 실수: 해시는 해시 함수/로드 팩터 관리가 중요, 적대 입력에선 O(n)으로 붕괴
  • 분할 상환과 최악의 혼동: 동적 배열 append는 연산 하나하나가 보장 O(1)이 아님
  • 작은 n의 현실: 저차항이 지배, 작은 입력엔 단순 알고리즘이 유리
  • 벤치마크 과최적화: JIT, 분기 예측, 데드 코드 제거, 워밍업의 영향을 간과
  • I/O/네트워크 무시: 많은 시스템이 CPU가 아니라 I/O 또는 지연(latency)에 묶임

실무 체크리스트

  1. 입력 모델과 크기 매개변수를 정의하세요(n, V, E, 키 범위 k, 문자열 길이 L 등).
  2. 의미 있는 복잡도 목표(최악/평균/분할 상환)를 선택하고 근거를 제시하세요.
  3. 시간·공간·단순성의 자료구조 트레이드오프를 고려하세요.
  4. 수학(점화식, 경계)과 측정(여러 n, 로그–로그 피팅)으로 모두 검증하세요.
  5. 메모리 거동(피크, 지역성, 할당)과 병렬 확장성(span)을 점검하세요.
  6. 회귀를 막을 수치/모니터링(예산, CI 성능 테스트)을 추가하세요.

수학 부록(참고)

  • 로그의 합: \sum_{i=1}^{n} \log i = \log n! = \Theta(n \log n)

  • 제곱/세제곱의 합: \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6},\quad \sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2

  • n^a와 n \log n 비교:

    • a > 1이면 n^a = ω(n \log n).
    • a = 1이면 n \log n = ω(n).

정확한 표기, 현실적인 측정, 자료구조 트레이드오프 감각을 갖추면 알고리즘을 자신 있게 분석·비교·개선할 수 있습니다.