시간 복잡도 핸드북

1. 생성 배경

현대의 소프트웨어 및 알고리즘 설계에서, 입력 크기 증가에 따른 성능 예측과 자원 최적화가 필수적이다. 시간 복잡도는 이러한 예측을 수학적·이론적으로 지원하며, 개발자와 연구자가 알고리즘을 비교·선택·개선할 수 있는 기준을 제공한다¹.

2. 시간 복잡도의 개요

알고리즘이 수행하는 기본 연산 횟수를 입력 크기 $n$의 함수로 표현하며, 특히 $n$이 커질 때의 점근적 성장률을 분석한다.

• 최악 사례 복잡도(worst-case): 입력 중 가장 시간이 오래 걸리는 경우의 연산 수
• 평균 사례 복잡도(average-case): 모든 가능한 입력에 대한 평균 연산 수
• 상수 계수 및 낮은 차수 항 무시: $O(f(n))$ 표기법에서는 상수 계수와 낮은 차수 항은 생략한다¹.

3. 주요 표기법

• Big O (빅-오): 상한(upper bound), 최악 사례 복잡도
• Big Ω (빅-오메가): 하한(lower bound), 최선 사례 복잡도
• Big Θ (빅-쎄타): 상·하한 동시 만족, 평균 사례 복잡도

4. 대표적 시간 복잡도 클래스

분류	표기법	설명	예시 알고리즘
상수 시간	$O(1)$	입력 크기 독립적	배열 원소 접근, 스택 pop()
로그 시간	$O(\log n)$	문제 크기 절반 축소 반복	이진 탐색
선형 시간	$O(n)$	입력 전체 순회	최댓값 탐색, 단순 순회
선형 대수 로그 시간	$O(n\log n)$	정렬·분할 정복	병합 정렬, 퀵정렬 평균
이차 시간	$O(n^2)$	중첩 반복문	버블 정렬, 삽입 정렬
지수 시간	$O(2^n)$	모든 부분집합 탐색	순열 생성, 0-1 배낭 문제 브루트포스

(위 표: Wikipedia “Time complexity” 중 “Table of common time complexities” 참조¹)

5. 상세 개념 및 분석 기법

5.1 상수·로그·선형·다항식·지수

1. 상수 시간 $O(1)$
   • 연산 횟수가 입력 크기와 무관
2. 로그 시간 $O(\log n)$
   • 매 단계 문제 크기 절반으로 축소
3. 선형 시간 $O(n)$
   • 입력을 한 번 순회
4. 다항식 시간 $O(n^k)$
   • $k$차 항 지배, P 클래스(실행 가능)
5. 지수 시간 $O(2^n)$
   • 부분집합·완전 탐색, NP-hard 문제

5.2 암호화된 분석: Amortized Analysis

단일 연산의 최악 사례만 보는 것은 과도히 비관적일 수 있으며, 금융의 ‘할부(amortization)’ 개념처럼 연산들을 묶어 평균 비용을 분석한다².

• Aggregate Analysis: 총 비용을 연산 개수로 나눔
• Accounting Method: 각 연산에 ‘크레딧’을 부여하여 고비용 연산 충당
• Potential Method: 자료구조에 잠재 에너지(potential)를 정의해 비용 변화 측정

실습 예: 동적 배열에서 삽입 시, 크기 초과 시 점진적 배열 복사는 $O(n)$이지만, 전체 삽입 연산 당 상수 시간으로 평균화 가능².

6. 구조 및 사용법 가이드

1. 알고리즘 설계 단계
   • 먼저 문제 특성과 입력 패턴 파악
   • 지배적 연산(가장 빈번·비용 큰 연산) 식별
2. 시간 복잡도 도출
   • 코드 흐름 분석: 반복문·재귀 호출·분할 정복
   • 점근 표기 적용: 상수·차수·로그 항 결정
3. 비교·최적화
   • 여러 알고리즘 간 Big O 비교
   • 고차 복잡도(예: $O(n^2)$)→저차(예: $O(n\log n)$) 대체 검토
   • 필요 시 암호화된 분석으로 평균 비용 검증
4. 실무 적용
   • 대규모 데이터 처리엔 $O(n\log n)$ 이하 권장
   • 실시간 시스템엔 $O(1)$·$O(\log n)$ 추구
   • 동적·예측 불가 입력엔 암호화된 분석 고려

핵심 메시지: 시간 복잡도는 알고리즘 효율의 이론적 토대로, 최악·평균·암호화된 분석을 통해 실제 성능을 예측하고 최적화할 수 있다.

⁂

Footnotes

1. https://en.wikipedia.org/wiki/Time_complexity ↩ ↩² ↩³

2. https://en.wikipedia.org/wiki/Amortized_analysis ↩ ↩²