[알고리즘] 시간 복잡도 & 공간 복잡도

데이터가 조금만 커져도 어떤 코드는 쏜살같이 실행되고, 어떤 코드는 한참을 버벅대죠. 그 차이를 설명해주는 개념이 바로 복잡도입니다. 복잡도는 크게 두 가지로 나뉩니다. 실행 시간과 관련된 시간 복잡도, 그리고 메모리 사용량과 관련된 공간 복잡도입니다.

 

1. 시간 복잡도 - 얼마나 오래 걸리는 지

시간 복잡도란 입력값의 크기 n에 따라 연산이 몇 번 수행되는지를 나타내는 척도입니다. 실제 실행 시간(몇 초)은 컴퓨터 사양마다 달라지기 때문에, 우리는 "입력이 n일 때 로직이 몇 번 반복되는가"를 기준으로 삼습니다.

이를 표현하는 방법이 바로 빅오(Big-O) 표기법입니다. 예를 들어 배열에서 특정 값을 하나씩 순서대로 비교한다면, 최악의 경우 n번 비교해야 하므로 O(N)이라고 씁니다. 반면 해시 테이블처럼 키만 알면 바로 접근 가능한 구조는 O(1), 즉 입력 크기와 무관하게 상수 번만 연산하면 됩니다.

 

빅오 표기법에서 자주 등장하는 복잡도를 느린 것부터 빠른 순서로 나열하면 다음과 같습니다.

 

O(1)	상수 시간	입력 크기와 상관없이 항상 동일
O(log n)	로그 시간	매우 빠름 (이진 탐색)
O(n)	선형 시간	입력 크기만큼 증가
O(n log n)	로그 선형	정렬 알고리즘
O(n²)	제곱 시간	이중 반복문
O(2ⁿ)	지수 시간	매우 느림

 

 

그래프를 보면 O(N²)이 입력이 조금만 커져도 얼마나 폭발적으로 증가하는지 한눈에 보입니다. O(1)과 O(log N)은 입력이 아무리 커도 거의 증가하지 않아 이상적인 복잡도로 꼽힙니다.

 

• n ≤ 10⁶ → O(n) 가능
• n ≤ 10⁵ → O(n log n) 가능
• n ≤ 10³ → O(n²) 가능
• n ≤ 20 → 완전탐색 가능

 

 

2. 공간 복잡도 - 메모리를 얼마나 차지하는 지

공간 복잡도는 프로그램이 실행될 때 필요한 메모리의 양입니다. 변수 하나를 선언하는 것도 공간을 차지하고, 재귀 함수가 호출될 때마다 스택 프레임이 쌓이는 것도 포함됩니다.

예를 들어 Java에서 int[] a = new int[1004]; 라고 선언하면, int 하나가 4바이트이므로 이 배열은 1004 × 4 = 4,016바이트, 약 4KB를 차지합니다. 이처럼 입력 크기 n에 비례해서 배열을 만들면 공간 복잡도가 O(N)이 되고, 크기가 고정된 변수 몇 개만 쓴다면 O(1)이 됩니다.

 

3. 자료구조별 복잡도 비교

시간 복잡도를 이야기할 때 평균적인 경우와 최악의 경우를 구분하는 것이 중요합니다. 이진 탐색 트리(BST)를 예로 들면, 잘 균형 잡혀 있을 때는 O(log N)이지만 한쪽으로 치우친 최악의 구조에서는 O(N)까지 떨어질 수 있습니다. 반면 AVL 트리는 스스로 균형을 유지하기 때문에 항상 O(log N)을 보장합니다.

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(N)	O(N)
스택	O(N)	O(N)	O(1)	O(1)
큐	O(N)	O(N)	O(1)	O(1)
이중 연결 리스트	O(N)	O(N)	O(1)	O(1)
해시 테이블	O(1) → O(N)	O(1) → O(N)	O(1) → O(N)	O(1) → O(N)
이진 탐색 트리	O(log N) → O(N)	O(log n) → O(N)	O(log N) → O(N)	O(log N) → O(N)
AVL 트리	O(log N)	O(log N)	O(log N)	O(log N)

 

해시 테이블 

평균적으로는 모든 연산이 O(1)이라 압도적으로 빠릅니다. 하지만 해시 충돌이 심하게 발생하면 최악의 경우 O(N)까지 떨어집니다. HashMap을 쓸 때 키 설계를 신경 써야 하는 이유입니다.

 

이진 탐색 트리(BST)

이론적으로는 O(log N)이지만, 정렬된 순서대로 삽입하면 트리가 일직선 연결 리스트 꼴이 되어 O(N)으로 퇴화합니다. 이 문제를 해결하기 위해 삽입, 삭제 때마다 스스로 균형을 조정하는 AVL 트리나 레드-블랙 트리 같은 균형 트리가 등장했습니다. Java의 TreeMap이 내부적으로 레드-블랙 트리를 사용하는 것이 대표적인 예입니다.

 

배열의 접근 속도

배열은 인덱스만 알면 바로 해당 메모리 주소를 계산할 수 있어 접근이 O(1)입니다. 반면 삽입, 삭제 시에는 원소를 밀거나 당겨야 하므로 O(N)이 됩니다. 데이터를 많이 추가하거나 제거한다면 연결 리스트가 특정 위치를 자주 읽는다면 배열이 유리합니다.

 

 

---