복잡도 분석 (Complexity Analysis)
복잡도 분석 (Complexity Analysis)¶
개요¶
알고리즘의 효율성을 측정하는 방법을 학습합니다. Big O 표기법을 이해하고 코드의 시간/공간 복잡도를 분석하는 능력은 알고리즘 학습의 기초입니다.
목차¶
1. 왜 복잡도 분석이 필요한가?¶
실행 시간의 한계¶
실제 실행 시간은 다음에 의존:
- 하드웨어 성능 (CPU, 메모리)
- 프로그래밍 언어
- 컴파일러 최적화
- 입력 데이터 특성
복잡도 분석의 장점¶
1. 하드웨어 독립적
2. 입력 크기에 따른 증가율 파악
3. 알고리즘 간 객관적 비교
4. 확장성(Scalability) 예측
예시: 같은 문제, 다른 알고리즘¶
문제: n개의 숫자에서 최댓값 찾기
방법 1: 순차 탐색 → O(n)
방법 2: 정렬 후 마지막 원소 → O(n log n)
n = 1,000,000일 때:
- 방법 1: ~1,000,000번 비교
- 방법 2: ~20,000,000번 연산
→ 방법 1이 약 20배 빠름
2. Big O 표기법¶
정의¶
Big O: 입력 크기 n이 증가할 때
연산 횟수의 상한(Upper Bound)을 나타냄
f(n) = O(g(n))
→ f(n)은 g(n)의 상수배보다 빠르게 증가하지 않음
표기 규칙¶
1. 상수는 무시
O(2n) = O(n)
O(100) = O(1)
2. 낮은 차수 항은 무시
O(n² + n) = O(n²)
O(n³ + n² + n) = O(n³)
3. 최고 차수 항만 남김
O(3n² + 2n + 1) = O(n²)
주요 복잡도 클래스¶
┌─────────────┬───────────────┬─────────────────────┐
│ 복잡도 │ 이름 │ 예시 │
├─────────────┼───────────────┼─────────────────────┤
│ O(1) │ 상수 │ 배열 인덱스 접근 │
│ O(log n) │ 로그 │ 이진 탐색 │
│ O(n) │ 선형 │ 순차 탐색 │
│ O(n log n) │ 선형 로그 │ 병합 정렬 │
│ O(n²) │ 제곱 │ 버블 정렬 │
│ O(n³) │ 세제곱 │ 플로이드-워셜 │
│ O(2ⁿ) │ 지수 │ 부분집합 열거 │
│ O(n!) │ 팩토리얼 │ 순열 열거 │
└─────────────┴───────────────┴─────────────────────┘
복잡도 비교 그래프¶
연산 수
│
│ O(n!)
│ ╱
│ O(2ⁿ)
│ ╱
│ O(n²)
│ ╱
│ O(n log n)
│ ╱
│ O(n)
│ ╱
│──────O(log n)
│══════O(1)
└───────────────────────────────→ n (입력 크기)
n 크기별 연산 횟수¶
┌──────┬─────────┬─────────┬──────────┬───────────┬────────────┐
│ n │ O(log n)│ O(n) │O(n log n)│ O(n²) │ O(2ⁿ) │
├──────┼─────────┼─────────┼──────────┼───────────┼────────────┤
│ 10 │ 3 │ 10 │ 33 │ 100 │ 1,024 │
│ 100 │ 7 │ 100 │ 664 │ 10,000 │ 10³⁰ │
│ 1000 │ 10 │ 1,000 │ 9,966 │ 1,000,000 │ 10³⁰⁰ │
│ 10⁶ │ 20 │ 10⁶ │ 2×10⁷ │ 10¹² │ ∞ │
└──────┴─────────┴─────────┴──────────┴───────────┴────────────┘
3. 시간 복잡도¶
3.1 O(1) - 상수 시간¶
// C
int getFirst(int arr[], int n) {
return arr[0]; // 항상 1번의 연산
}
int getElement(int arr[], int index) {
return arr[index]; // 배열 크기와 무관
}
// C++
int getFirst(const vector<int>& arr) {
return arr[0];
}
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
# Python
def get_first(arr):
return arr[0]
def get_element(arr, index):
return arr[index]
3.2 O(log n) - 로그 시간¶
// C - 이진 탐색
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
// 매 반복마다 탐색 범위가 절반으로 줄어듦
// n → n/2 → n/4 → ... → 1
// 반복 횟수: log₂(n)
// C++
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
# Python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
3.3 O(n) - 선형 시간¶
// C - 최댓값 찾기
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) { // n-1번 반복
if (arr[i] > max)
max = arr[i];
}
return max;
}
// C++
int findMax(const vector<int>& arr) {
int maxVal = arr[0];
for (int i = 1; i < arr.size(); i++) {
maxVal = max(maxVal, arr[i]);
}
return maxVal;
}
// STL 사용
int findMaxSTL(const vector<int>& arr) {
return *max_element(arr.begin(), arr.end());
}
# Python
def find_max(arr):
max_val = arr[0]
for x in arr[1:]:
if x > max_val:
max_val = x
return max_val
# 내장 함수 사용
def find_max_builtin(arr):
return max(arr)
3.4 O(n log n) - 선형 로그 시간¶
// C - 병합 정렬 (개념)
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // T(n/2)
mergeSort(arr, mid + 1, right); // T(n/2)
merge(arr, left, mid, right); // O(n)
}
}
// T(n) = 2T(n/2) + O(n) = O(n log n)
// C++ - STL 정렬
#include <algorithm>
void sortArray(vector<int>& arr) {
sort(arr.begin(), arr.end()); // O(n log n)
}
# Python
def sort_array(arr):
return sorted(arr) # O(n log n) - Timsort
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort() # in-place 정렬
3.5 O(n²) - 제곱 시간¶
// C - 버블 정렬
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // n-1번
for (int j = 0; j < n - i - 1; j++) { // n-i-1번
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
// C++ - 중첩 반복문
void printPairs(const vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[i] << ", " << arr[j] << endl;
}
}
}
// n × n = O(n²)
# Python
def print_pairs(arr):
n = len(arr)
for i in range(n):
for j in range(n):
print(arr[i], arr[j])
3.6 O(2ⁿ) - 지수 시간¶
// C - 피보나치 (재귀, 비효율적)
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// T(n) = T(n-1) + T(n-2) ≈ O(2ⁿ)
// C++ - 부분집합 생성
void generateSubsets(vector<int>& arr, int index, vector<int>& current) {
if (index == arr.size()) {
// 현재 부분집합 출력
for (int x : current) cout << x << " ";
cout << endl;
return;
}
// 포함하지 않는 경우
generateSubsets(arr, index + 1, current);
// 포함하는 경우
current.push_back(arr[index]);
generateSubsets(arr, index + 1, current);
current.pop_back();
}
// 2ⁿ개의 부분집합 생성
# Python - 부분집합 생성
def generate_subsets(arr):
result = []
n = len(arr)
for i in range(1 << n): # 2^n 반복
subset = []
for j in range(n):
if i & (1 << j):
subset.append(arr[j])
result.append(subset)
return result
4. 공간 복잡도¶
4.1 개념¶
공간 복잡도 = 알고리즘이 사용하는 메모리의 양
구성 요소:
1. 입력 공간: 입력 데이터 저장
2. 보조 공간: 알고리즘 실행에 필요한 추가 메모리
일반적으로 보조 공간만 계산
4.2 O(1) - 상수 공간¶
// C - In-place 교환
void reverseArray(int arr[], int n) {
int left = 0, right = n - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// 변수 3개만 사용 (left, right, temp)
# Python
def reverse_array(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
4.3 O(n) - 선형 공간¶
// C - 배열 복사
int* copyArray(int arr[], int n) {
int* copy = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
copy[i] = arr[i];
}
return copy;
}
// n개 원소를 저장할 추가 메모리 필요
// C++ - 병합 정렬의 병합 과정
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1); // O(n) 추가 공간
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int i = 0; i < k; i++)
arr[left + i] = temp[i];
}
# Python
def copy_array(arr):
return arr[:] # O(n) 공간
4.4 O(log n) - 로그 공간 (재귀 스택)¶
// C - 이진 탐색 (재귀)
int binarySearchRecursive(int arr[], int left, int right, int target) {
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, right, target);
else
return binarySearchRecursive(arr, left, mid - 1, target);
}
// 재귀 깊이: O(log n) → 스택 공간 O(log n)
4.5 시간-공간 트레이드오프¶
┌─────────────────────────────────────────────────────────┐
│ 알고리즘 │ 시간 복잡도 │ 공간 복잡도 │ 특징 │
├───────────────────┼─────────────┼─────────────┼────────┤
│ 병합 정렬 │ O(n log n) │ O(n) │ 안정적 │
│ 퀵 정렬 │ O(n log n) │ O(log n) │ 제자리 │
│ 힙 정렬 │ O(n log n) │ O(1) │ 제자리 │
├───────────────────┼─────────────┼─────────────┼────────┤
│ 피보나치 (재귀) │ O(2ⁿ) │ O(n) │ 비효율 │
│ 피보나치 (메모) │ O(n) │ O(n) │ 공간↑ │
│ 피보나치 (반복) │ O(n) │ O(1) │ 최적 │
└─────────────────────────────────────────────────────────┘
5. 복잡도 분석 예제¶
예제 1: 중첩 반복문¶
// 분석: 이 함수의 시간 복잡도는?
int example1(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // n번
for (int j = 0; j < n; j++) { // n번
count++;
}
}
return count;
}
// 답: O(n²)
// n × n = n²
예제 2: 비대칭 중첩 반복문¶
int example2(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // n번
for (int j = 0; j < i; j++) { // 0, 1, 2, ..., n-1번
count++;
}
}
return count;
}
// 답: O(n²)
// 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)
예제 3: 로그 반복¶
int example3(int n) {
int count = 0;
for (int i = 1; i < n; i *= 2) { // log₂(n)번
count++;
}
return count;
}
// 답: O(log n)
// i: 1, 2, 4, 8, ..., n → log₂(n)번 반복
예제 4: 중첩 로그 반복¶
int example4(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // n번
for (int j = 1; j < n; j *= 2) { // log n번
count++;
}
}
return count;
}
// 답: O(n log n)
// n × log n
예제 5: 연속된 반복문¶
int example5(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // O(n)
count++;
}
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n)
count++;
}
}
return count;
}
// 답: O(n²)
// O(n) + O(n²) = O(n²)
// 최고 차수 항만 남김
예제 6: 조건부 실행¶
int example6(int n, bool flag) {
int count = 0;
if (flag) {
for (int i = 0; i < n; i++) { // O(n)
count++;
}
} else {
for (int i = 0; i < n; i++) { // O(n²)
for (int j = 0; j < n; j++) {
count++;
}
}
}
return count;
}
// 답: O(n²)
// 최악의 경우(worst case)를 고려
예제 7: 재귀 분석¶
int example7(int n) {
if (n <= 1)
return 1;
return example7(n - 1) + example7(n - 1);
}
// 답: O(2ⁿ)
// T(n) = 2T(n-1) + O(1)
// 호출 트리:
// f(4)
// / \
// f(3) f(3)
// / \ / \
// f(2) f(2) f(2) f(2)
// ...
// 레벨당 노드 수: 1, 2, 4, 8, ... = 2ⁿ
6. 실전 분석 팁¶
6.1 코딩 테스트 시간 제한 기준¶
시간 제한 1초 기준 (C/C++):
┌───────────────┬─────────────────────┐
│ 복잡도 │ 최대 입력 크기 │
├───────────────┼─────────────────────┤
│ O(n!) │ n ≤ 10 │
│ O(2ⁿ) │ n ≤ 20 │
│ O(n³) │ n ≤ 500 │
│ O(n²) │ n ≤ 5,000 │
│ O(n log n) │ n ≤ 1,000,000 │
│ O(n) │ n ≤ 10,000,000 │
│ O(log n) │ n ≤ 10¹⁸ │
└───────────────┴─────────────────────┘
Python은 C/C++보다 약 10~100배 느림
→ 위 기준에서 n을 1/10로 줄여서 계산
6.2 자주 쓰는 연산의 복잡도¶
┌──────────────────────────────────────────────────────┐
│ 자료구조/연산 │ 평균 │ 최악 │ 비고 │
├────────────────────┼───────────┼───────────┼────────┤
│ 배열 접근 │ O(1) │ O(1) │ │
│ 배열 탐색 │ O(n) │ O(n) │ │
│ 배열 삽입/삭제 │ O(n) │ O(n) │ 이동 │
├────────────────────┼───────────┼───────────┼────────┤
│ 해시 테이블 접근 │ O(1) │ O(n) │ 충돌 │
│ 해시 테이블 삽입 │ O(1) │ O(n) │ 충돌 │
├────────────────────┼───────────┼───────────┼────────┤
│ 이진 탐색 트리 │ O(log n) │ O(n) │ 편향 │
│ 균형 이진 트리 │ O(log n) │ O(log n) │ AVL 등 │
├────────────────────┼───────────┼───────────┼────────┤
│ 힙 삽입/삭제 │ O(log n) │ O(log n) │ │
│ 힙 최솟값 접근 │ O(1) │ O(1) │ │
└──────────────────────────────────────────────────────┘
6.3 분석 체크리스트¶
□ 모든 반복문의 반복 횟수 파악
□ 중첩 반복문은 곱셈으로 계산
□ 연속된 반복문은 덧셈 (최고 차수만)
□ 재귀 호출은 점화식으로 분석
□ 조건문은 최악의 경우 고려
□ 라이브러리 함수의 복잡도 확인
□ 공간 복잡도도 함께 분석
7. 연습 문제¶
문제 1: 복잡도 계산¶
다음 코드의 시간 복잡도를 구하세요.
void mystery(int n) {
for (int i = n; i >= 1; i /= 2) {
for (int j = 1; j <= n; j *= 2) {
// O(1) 작업
}
}
}
정답 보기
**O(log²n)** - 바깥 반복: i가 n에서 1까지 절반씩 감소 → log n번 - 안쪽 반복: j가 1에서 n까지 2배씩 증가 → log n번 - 총: log n × log n = O(log²n)문제 2: 복잡도 비교¶
n = 1000일 때, 연산 횟수를 비교하세요.
A. O(n)
B. O(n log n)
C. O(n²)
D. O(2^(log n))
정답 보기
A. O(n) = 1,000
B. O(n log n) ≈ 10,000
C. O(n²) = 1,000,000
D. O(2^(log n)) = O(n) = 1,000
2^(log₂ n) = n 이므로 A와 D는 같음
문제 3: 재귀 분석¶
int f(int n) {
if (n <= 1) return 1;
return f(n/2) + f(n/2);
}
정답 보기
**O(n)** 점화식: T(n) = 2T(n/2) + O(1) 마스터 정리 적용: - a = 2, b = 2, f(n) = O(1) - n^(log₂2) = n¹ = n - f(n) = O(1) < n → 케이스 1 - T(n) = O(n)추천 문제¶
| 난이도 | 문제 | 플랫폼 |
|---|---|---|
| ⭐ | 수 정렬하기 | 백준 |
| ⭐ | 수 찾기 | 백준 |
| ⭐⭐ | Two Sum | LeetCode |
| ⭐⭐ | Contains Duplicate | LeetCode |
다음 단계¶
- 02_Arrays_and_Strings.md - 2포인터, 슬라이딩 윈도우
참고 자료¶
- Big-O Cheat Sheet
- VisuAlgo
- Introduction to Algorithms (CLRS)