복잡도

복잡도 ( 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) 시간 복잡도의 시각적 비교

output (1).png

 

위 그래프는 입력 크기(n)가 커질수록 시간 복잡도별 알고리즘의 실행량 차이를 시각적으로 보여줍니다.

복잡도  특징 예시
O(1) 입력 크기와 무관 배열 인덱스 접근
O(n) 선형 증가 단일 반복문
O(n log n) 느린 곱셈 형태 증가 병합 정렬, 힙 정렬
O(n²) 급격한 증가 이중 for문, 브루트포스
O(2ⁿ) 폭발적으로 증가 재귀적 백트래킹 (예: 부분 집합 생성)

 

 

 

 

7) 공간 복잡도의 시각적 비교

 

output (2).png

 

위 그래프는 입력 크기 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