복잡도 ( Complexity )
1) 복잡도란?
복잡도는 알고리즘이 문제를 해결하는 데 소요되는 리소스를 추상적으로 측정하는 방법
2) 복잡도의 종류
종류 | 의미 | 측정 단위 |
시간 복잡도 | 실행에 걸리는 시간 | 연산 횟수 |
공간 복잡도 | 사용하는 메모리 양 | 저장 공간 |
3) 시간복잡도 (Time Complexity)
입력 크기 n에 대해, 알고리즘이 수행하는 연산의 수를 수학적으로 표현한 것입니다.
예시
아래 코드는 n번 반복하므로 O(n)입니다.
for (int i = 0; i < n; i++) {
System.out.println(i);
}
이중 반복문이라 총 n * n번 → O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(i + ", " + j);
}
}
4) 공간복잡도 (Space Complexity)
알고리즘이 문제를 해결하는 동안 사용하는 메모리 공간의 양
예시
배열 n개의 공간이 필요 → O(n)
int[] arr = new int[n];
정수 하나 → O(1) (상수 공간)
int sum = 0;
5) 복잡도의 중요성
입력이 작을 땐 어떤 알고리즘이든 잘 돌아갑니다.
하지만 입력 크기가 커질수록, 복잡도가 높은 알고리즘은 느려지거나 메모리를 초과하게 됩니다.
예) O(n) → 1,000,000 입력도 처리 가능
O(n²) → 1,000 입력도 힘들 수 있음
6) 시간 복잡도의 시각적 비교

위 그래프는 입력 크기(n)가 커질수록 시간 복잡도별 알고리즘의 실행량 차이를 시각적으로 보여줍니다.
복잡도 | 특징 | 예시 |
O(1) | 입력 크기와 무관 | 배열 인덱스 접근 |
O(n) | 선형 증가 | 단일 반복문 |
O(n log n) | 느린 곱셈 형태 증가 | 병합 정렬, 힙 정렬 |
O(n²) | 급격한 증가 | 이중 for문, 브루트포스 |
O(2ⁿ) | 폭발적으로 증가 | 재귀적 백트래킹 (예: 부분 집합 생성) |
7) 공간 복잡도의 시각적 비교

위 그래프는 입력 크기 n에 따라 알고리즘이 사용하는 메모리(공간)가 어떻게 증가하는지를 보여줍니다.
복잡도 | 설명 | 예시 |
O(1) | 상수 공간. 입력 크기와 무관 | 단일 변수 사용 |
O(log n) | 느리게 증가 | 재귀 호출 깊이 (이진 탐색 등) |
O(n) | 입력에 비례 | 배열, 큐 등 |
O(n²) | 급격히 증가 | 2차원 배열, 플로이드 워셜 등 |
8) 시간복잡도 VS 공간복잡도
시간복잡도는 '얼마나 빨리 끝나느냐' (BFS가 유리)
공간복잡도는 '얼마나 적은 메모리로 하느냐' (DFS가 유리)
둘 중 어느것을 우선시 하느냐에 따라 BFS를 사용할지, DFS를 사용할지 판단해야합니다.
예)
메모리 부족한 임베디드 시스템 → DFS 유리
최단 경로를 빠르게 찾아야 하는 게임 AI → BFS 유리
'Algorithm > 이론' 카테고리의 다른 글
순열 / 조합 / 부분집합 (0) | 2025.05.02 |
---|---|
재귀함수 (Recursion) (0) | 2025.05.02 |
DFS 깊이 우선 탐색 (스택 방식) (0) | 2025.05.01 |
DFS 깊이 우선 탐색 (재귀방식) (0) | 2025.05.01 |
BFS 너비 우선 탐색 (0) | 2025.04.30 |