알고리즘 복잡도 분석 가이드
알고리즘 복잡도 분석 가이드
1. 빅오 표기법(Big-O Notation) 기본 개념
빅오 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 표현하는 수학적 표기법입니다. 입력 크기 n에 대해 알고리즘이 실행되는 최악의 경우(worst case)를 나타냅니다.
1.1 주요 시간 복잡도 (빠른 순서)
- O(1) - 상수 시간: 입력 크기와 관계없이 일정한 시간
- O(log n) - 로그 시간: 입력이 증가해도 실행 시간은 천천히 증가
- O(n) - 선형 시간: 입력 크기에 비례하여 증가
- O(n log n) - 선형 로그 시간: 효율적인 정렬 알고리즘
- O(n²) - 이차 시간: 중첩 반복문
- O(n³) - 삼차 시간: 3중 중첩 반복문
- O(2ⁿ) - 지수 시간: 매우 느림
- O(n!) - 팩토리얼 시간: 극도로 느림
1.2 공간 복잡도
알고리즘이 실행되는 동안 사용하는 메모리 공간을 나타냅니다. 입력 공간과 보조 공간(auxiliary space)을 합한 것입니다.
2. 알고리즘 유형별 복잡도
2.1 정렬 알고리즘
| 알고리즘 | 최선 | 평균 | 최악 | 공간 복잡도 | 안정성 |
|---|---|---|---|---|---|
| 버블 정렬 | O(n) | O(n²) | O(n²) | O(1) | 안정 |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | O(1) | 불안정 |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | O(1) | 안정 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | O(n) | 안정 |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) | O(log n) | 불안정 |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | O(1) | 불안정 |
| 카운팅 정렬 | O(n+k) | O(n+k) | O(n+k) | O(k) | 안정 |
| 기수 정렬 | O(d×n) | O(d×n) | O(d×n) | O(n+k) | 안정 |
효율성 비교:
- 일반적인 경우: 병합 정렬, 퀵 정렬이 가장 효율적 (O(n log n))
- 거의 정렬된 데이터: 삽입 정렬이 효율적 (O(n))
- 정수 범위가 제한적: 카운팅 정렬이 가장 빠름 (O(n))
2.2 검색 알고리즘
| 알고리즘 | 시간 복잡도 | 공간 복잡도 | 전제 조건 |
|---|---|---|---|
| 선형 검색 | O(n) | O(1) | 없음 |
| 이진 검색 | O(log n) | O(1) | 정렬된 배열 |
| 해시 테이블 | O(1) 평균 | O(n) | 해시 함수 필요 |
| 이진 검색 트리 | O(log n) 평균, O(n) 최악 | O(n) | 균형 트리 권장 |
효율성 비교:
- 정렬된 데이터: 이진 검색이 가장 효율적
- 빈번한 검색: 해시 테이블이 가장 빠름
- 동적 데이터: 균형 이진 검색 트리 사용
2.3 그래프 알고리즘
| 알고리즘 | 시간 복잡도 | 공간 복잡도 | 용도 |
|---|---|---|---|
| DFS (깊이 우선 탐색) | O(V+E) | O(V) | 경로 탐색, 사이클 검출 |
| BFS (너비 우선 탐색) | O(V+E) | O(V) | 최단 경로 (가중치 없음) |
| 다익스트라 | O((V+E) log V) | O(V) | 최단 경로 (양수 가중치) |
| 벨만-포드 | O(VE) | O(V) | 최단 경로 (음수 가중치) |
| 플로이드-워셜 | O(V³) | O(V²) | 모든 쌍 최단 경로 |
| 프림 | O(E log V) | O(V) | 최소 신장 트리 |
| 크루스칼 | O(E log E) | O(V) | 최소 신장 트리 |
V: 정점 수, E: 간선 수
2.4 동적 프로그래밍
동적 프로그래밍의 복잡도는 문제에 따라 다르지만, 일반적으로:
- 시간 복잡도: O(상태 개수 × 전이 비용)
- 공간 복잡도: O(상태 개수) 또는 최적화 시 O(필요한 이전 상태 수)
대표적인 예시:
- 피보나치 수열: O(n) 시간, O(n) 또는 O(1) 공간
- 배낭 문제 (0/1 Knapsack): O(nW) 시간, O(nW) 공간
- 최장 공통 부분 수열 (LCS): O(mn) 시간, O(mn) 공간
2.5 분할 정복
분할 정복 알고리즘의 시간 복잡도는 마스터 정리(Master Theorem)로 분석합니다.
T(n) = aT(n/b) + f(n) 형태에서:
- 병합 정렬: T(n) = 2T(n/2) + O(n) = O(n log n)
- 이진 검색: T(n) = T(n/2) + O(1) = O(log n)
3. JavaScript 내장 메소드 복잡도
3.1 배열(Array) 메소드
| 메소드 | 시간 복잡도 | 설명 |
|---|---|---|
push() |
O(1) | 배열 끝에 추가 |
pop() |
O(1) | 배열 끝에서 제거 |
shift() |
O(n) | 배열 앞에서 제거 (인덱스 재조정) |
unshift() |
O(n) | 배열 앞에 추가 (인덱스 재조정) |
splice() |
O(n) | 중간 삽입/삭제 |
slice() |
O(n) | 부분 배열 복사 |
concat() |
O(n+m) | 두 배열 합치기 |
indexOf() |
O(n) | 선형 검색 |
includes() |
O(n) | 선형 검색 |
find() |
O(n) | 조건 만족하는 첫 요소 |
findIndex() |
O(n) | 조건 만족하는 첫 인덱스 |
filter() |
O(n) | 조건 만족하는 모든 요소 |
map() |
O(n) | 각 요소 변환 |
reduce() |
O(n) | 누적 연산 |
forEach() |
O(n) | 각 요소 순회 |
some() |
O(n) | 하나라도 조건 만족 |
every() |
O(n) | 모두 조건 만족 |
sort() |
O(n log n) | 정렬 (V8: Timsort) |
reverse() |
O(n) | 배열 뒤집기 |
join() |
O(n) | 문자열로 합치기 |
flat() |
O(n×d) | 배열 평탄화 (d: 깊이) |
3.2 문자열(String) 메소드
| 메소드 | 시간 복잡도 | 설명 |
|---|---|---|
charAt() |
O(1) | 인덱스로 문자 접근 |
substring() |
O(n) | 부분 문자열 추출 |
slice() |
O(n) | 부분 문자열 추출 |
indexOf() |
O(n×m) | 문자열 검색 |
includes() |
O(n×m) | 문자열 포함 여부 |
split() |
O(n) | 문자열 분할 |
replace() |
O(n) | 문자열 치환 (첫 번째) |
replaceAll() |
O(n×m) | 문자열 전체 치환 |
toLowerCase() |
O(n) | 소문자 변환 |
toUpperCase() |
O(n) | 대문자 변환 |
trim() |
O(n) | 공백 제거 |
concat() |
O(n+m) | 문자열 합치기 |
repeat() |
O(n×k) | 문자열 반복 (k: 반복 횟수) |
n: 문자열 길이, m: 검색 패턴 길이
3.3 객체(Object) 연산
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| 프로퍼티 접근 | O(1) |
obj.key 또는 obj[key]
|
| 프로퍼티 추가 | O(1) | obj.newKey = value |
| 프로퍼티 삭제 | O(1) | delete obj.key |
Object.keys() |
O(n) | 모든 키 배열로 반환 |
Object.values() |
O(n) | 모든 값 배열로 반환 |
Object.entries() |
O(n) | 키-값 쌍 배열로 반환 |
Object.assign() |
O(n) | 객체 복사/병합 |
in 연산자 |
O(1) | 프로퍼티 존재 확인 |
hasOwnProperty() |
O(1) | 자체 프로퍼티 확인 |
3.4 Set 메소드
| 메소드 | 시간 복잡도 | 설명 |
|---|---|---|
add() |
O(1) | 요소 추가 |
delete() |
O(1) | 요소 삭제 |
has() |
O(1) | 요소 존재 확인 |
clear() |
O(n) | 모든 요소 삭제 |
forEach() |
O(n) | 모든 요소 순회 |
size |
O(1) | 요소 개수 |
3.5 Map 메소드
| 메소드 | 시간 복잡도 | 설명 |
|---|---|---|
set() |
O(1) | 키-값 추가 |
get() |
O(1) | 값 조회 |
delete() |
O(1) | 키-값 삭제 |
has() |
O(1) | 키 존재 확인 |
clear() |
O(n) | 모든 요소 삭제 |
forEach() |
O(n) | 모든 요소 순회 |
keys() |
O(1)* | 키 이터레이터 (순회 시 O(n)) |
values() |
O(1)* | 값 이터레이터 (순회 시 O(n)) |
entries() |
O(1)* | 엔트리 이터레이터 (순회 시 O(n)) |
size |
O(1) | 요소 개수 |
3.6 정규표현식(RegExp)
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
test() |
O(n×m) ~ O(n) | 패턴 매칭 여부 |
exec() |
O(n×m) ~ O(n) | 매칭 결과 반환 |
match() |
O(n×m) ~ O(n) | 모든 매칭 찾기 |
복잡도는 정규표현식 엔진과 패턴에 따라 다름
4. 효율적인 코드 작성 가이드
4.1 배열 처리 최적화
❌ 비효율적:
// O(n²) - 중복 제거
const arr = [1, 2, 2, 3, 3, 4];
const unique = arr.filter((item, index) => arr.indexOf(item) === index);
✅ 효율적:
// O(n) - Set 사용
const arr = [1, 2, 2, 3, 3, 4];
const unique = [...new Set(arr)];
4.2 검색 최적화
❌ 비효율적:
// O(n) - 배열 검색
const arr = [1, 2, 3, 4, 5];
const exists = arr.includes(3); // 매번 선형 검색
✅ 효율적:
// O(1) - Set 검색
const set = new Set([1, 2, 3, 4, 5]);
const exists = set.has(3); // 상수 시간
4.3 문자열 연결 최적화
❌ 비효율적:
// O(n²) - 문자열 반복 연결
let result = "";
for (let i = 0; i < arr.length; i++) {
result += arr[i]; // 매번 새 문자열 생성
}
✅ 효율적:
// O(n) - join 사용
const result = arr.join("");
4.4 객체 vs Map 선택
객체 사용:
- 고정된 키 집합
- JSON 직렬화 필요
- 단순한 키-값 저장
Map 사용:
- 빈번한 추가/삭제
- 임의의 키 타입 (객체, 함수 등)
- 순서 유지 필요
- 크기 확인 빈번
4.5 시간-공간 트레이드오프
메모이제이션 예시:
// 시간 복잡도: O(2ⁿ) → O(n)
// 공간 복잡도: O(1) → O(n)
const memo = new Map();
function fibonacci(n) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fibonacci(n - 1) + fibonacci(n - 2);
memo.set(n, result);
return result;
}
5. 복잡도 분석 실전 팁
5.1 코드에서 복잡도 파악하기
- 단순 반복문: O(n)
for (let i = 0; i < n; i++) {
// O(1) 작업
}
- 중첩 반복문: O(n²)
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// O(1) 작업
}
}
- 반으로 줄이는 반복: O(log n)
let i = n;
while (i > 1) {
i = Math.floor(i / 2);
}
- 분할 정복: O(n log n)
function mergeSort(arr) {
if (arr.length <= 1) return arr;
// 분할: O(log n) 단계
// 병합: 각 단계에서 O(n)
}
5.2 최적화 우선순위
- 알고리즘 선택: 올바른 자료구조와 알고리즘 선택이 가장 중요
- 불필요한 작업 제거: 중복 계산, 불필요한 반복 제거
- 적절한 자료구조: 작업에 맞는 자료구조 사용
- 캐싱/메모이제이션: 반복 계산 피하기
- 코드 수준 최적화: 마지막 단계
5.3 주의사항
- 빅오는 최악의 경우를 나타냄 (평균/최선의 경우도 고려 필요)
- 상수 계수는 무시되지만 실제로는 중요할 수 있음
- 입력 크기가 작으면 복잡한 알고리즘이 오히려 느릴 수 있음
- 실제 측정이 이론적 분석보다 정확할 수 있음