알고리즘 복잡도와 O-Notation
1. 개요
가. 정의
알고리즘 복잡도(complexity) 는 입력 크기(n)에 따라 알고리즘이 소모하는 자원의 양으로, 연산 횟수를 재는 시간 복잡도와 메모리를 재는 공간 복잡도로 구분한다. O-Notation(빅오) 은 입력이 충분히 커질 때의 증가율(점근적 상한, asymptotic upper bound) 을 표기하는 방법이다.
복잡도를 실제 실행 시간(초)이 아니라 연산 횟수의 증가율로 측정하는 이유가 중요하다. 실행 시간은 CPU 성능·언어·컴파일러에 따라 달라져 알고리즘 자체의 우열을 판단할 수 없지만, "입력이 2배가 되면 연산은 몇 배가 되는가"는 하드웨어와 무관한 알고리즘 고유의 성질이기 때문이다. 그래서 O-Notation은 상수항·저차항을 버리고 가장 지배적인 항의 증가율만 남긴다 — 예컨대 3n²+5n+7은 n이 커지면 n² 항이 지배하므로 O(n²)로 표기한다.
나. 점근 표기법의 종류
O 하나만 있는 것이 아니라, 상한·하한·정확한 한계를 각각 표기하는 세 기호가 있다. 실무에서는 최악의 경우를 보장하는 것이 설계 안전성 측면에서 중요하므로 상한을 나타내는 O를 가장 널리 쓴다.
| 표기 | 의미 | 관점 |
|---|---|---|
| O (빅오) | 점근적 상한 | 최악(worst) — 성능 보장 |
| Ω (빅오메가) | 점근적 하한 | 최선(best) |
| Θ (빅세타) | 상·하한 일치 | 정확한 증가율(average) |
2. O-Notation 유형 및 연산량
아래 그래프는 입력 크기 n이 커질 때 각 복잡도의 연산량이 어떻게 벌어지는지를 보여준다. n이 작을 때는 차이가 미미하지만, n이 커지면 O(n²) 이상은 급격히 발산해 사실상 실행 불가능해진다. 바로 이 큰 n에서의 차이가 알고리즘 선택을 좌우한다.
{
"type": "line",
"data": {
"labels": ["1","2","4","8","16","32","64"],
"datasets": [
{ "label": "O(1)", "data": [1,1,1,1,1,1,1], "borderColor": "#0e9f6e", "tension": 0.2 },
{ "label": "O(log n)", "data": [0,1,2,3,4,5,6], "borderColor": "#2f6fed", "tension": 0.2 },
{ "label": "O(n)", "data": [1,2,4,8,16,32,64], "borderColor": "#f59e0b", "tension": 0.2 },
{ "label": "O(n log n)", "data": [0,2,8,24,64,160,384], "borderColor": "#8b5cf6", "tension": 0.2 },
{ "label": "O(n^2)", "data": [1,4,16,64,256,1024,4096], "borderColor": "#e11d48", "tension": 0.2 }
]
},
"options": {
"plugins": { "legend": { "position": "bottom" }, "title": { "display": true, "text": "입력 크기(n) 대비 연산량 증가" } },
"scales": { "y": { "title": { "display": true, "text": "연산 횟수" } } }
}
}
각 유형은 알고리즘의 동작 구조에서 비롯된다. 왜 그 복잡도가 나오는지를 이해하면 코드만 봐도 복잡도를 가늠할 수 있다.
- O(1) 상수: 입력 크기와 무관하게 일정한 연산. 해시 조회·배열 인덱스 접근처럼 한 번에 위치를 계산하는 경우다.
- O(log n) 로그: 매 단계마다 탐색 범위를 절반으로 줄이는 구조. 이진 탐색이 대표적이며, n이 백만이어도 약 20번이면 끝난다.
- O(n) 선형: 입력을 한 번 훑는 구조. 순차 탐색·합계 계산이 그렇다.
- O(n log n) 선형로그: 데이터를 분할한 뒤(log n 단계) 각 단계에서 전체를 훑는(n) 구조. 병합·퀵 정렬 같은 효율적 정렬의 하한이다.
- O(n²) 제곱: 이중 반복문으로 모든 쌍을 비교하는 구조. 버블·삽입 정렬이 해당하며, n이 커지면 급격히 느려진다.
- O(2ⁿ) 지수: 매 단계 경우의 수가 2배로 분기하는 구조. 메모이제이션 없는 재귀 피보나치·부분집합 열거가 그렇다.
- O(n!) 계승: 모든 순열을 시도하는 구조. 외판원 문제(TSP)의 완전탐색이 대표로, n=20만 되어도 계산 불가다.
| 유형 | 명칭 | 구조 원리 | 예시 |
|---|---|---|---|
| O(1) | 상수 | 직접 접근 | 해시 조회, 배열 인덱스 |
| O(log n) | 로그 | 범위 절반씩 축소 | 이진 탐색 |
| O(n) | 선형 | 한 번 순회 | 순차 탐색 |
| O(n log n) | 선형로그 | 분할+순회 | 병합·퀵 정렬 |
| O(n²) | 제곱 | 이중 반복(모든 쌍) | 버블·삽입 정렬 |
| O(2ⁿ) | 지수 | 2배씩 분기 | 부분집합, 재귀 피보나치 |
| O(n!) | 계승 | 모든 순열 | 외판원 완전탐색 |
증가율: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
3. 케이스 분석
같은 알고리즘도 입력의 상태에 따라 성능이 달라지므로, 최선·평균·최악을 구분해 분석한다. 예를 들어 퀵 정렬은 피벗이 매번 중앙값에 가까우면 평균 O(n log n)이지만, 이미 정렬된 배열에서 피벗을 잘못 고르면 분할이 한쪽으로 치우쳐 최악 O(n²) 이 된다. 설계에서는 보통 최악의 경우(O) 를 기준으로 삼아야 실서비스에서 성능이 보장된다.
| 케이스 | 표기 | 의미 |
|---|---|---|
| 최선(Best) | Ω | 가장 빠른 입력에서의 성능 |
| 평균(Average) | Θ | 기대 성능 |
| 최악(Worst) | O | 보장 상한 — 설계 기준 |
4. 고려사항 및 시사점
- 큰 n에서 복잡도가 성능을 지배: 소규모 데이터에서는 상수 차이가 커 O(n²)이 O(n log n)보다 빠를 수도 있으나, 대용량에서는 점근 복잡도가 절대적이다. 데이터 규모에 맞는 알고리즘 선택이 관건이다.
- 시간·공간 트레이드오프: 복잡도는 시간과 공간 사이에서 교환된다. 예컨대 캐싱·메모이제이션은 메모리(공간)를 더 써서 반복 계산(시간)을 줄인다 — 재귀 피보나치를 메모이제이션하면 O(2ⁿ)이 O(n)으로 줄어드는 것이 대표 사례다.
- 점근 분석의 한계 보완: 상수항·하드웨어·캐시 지역성·상수 배수는 무시되므로, 실제 튜닝 시에는 프로파일링으로 실측을 병행한다.
- 연계·전망: 다항시간(P)에 풀리는지 여부는 P-NP 등 계산 복잡도 이론의 핵심 주제이며, TSP처럼 O(n!)인 NP-난해 문제는 근사·휴리스틱·동적계획법으로 현실적 해를 구한다. 복잡도 분석은 알고리즘 선택·최적화의 기본 척도다.
한 줄 요약: O-Notation은 입력 크기에 따른 알고리즘의 최악 증가율(점근 상한) 을 하드웨어 독립적으로 표기하며, O(1)→O(log n)→O(n)→O(n log n)→O(n²)→O(2ⁿ)→O(n!) 순으로 성능이 급격히 나빠지고, 시간·공간 트레이드오프와 큰 n에서의 지배성을 고려해 알고리즘을 선택한다.