시간 복잡도와 공간 복잡도
시간·공간 복잡도의 의미와 Big-O, Big-Ω, Big-θ 표기법의 차이, Big-O를 주로 쓰는 이유를 정리한다.
시리즈 · 자료구조 · 알고리즘1 / 13
- 시간 복잡도와 공간 복잡도
- 재귀 함수와 꼬리 재귀 최적화
- 연결 리스트(Linked List)
- 스택과 큐: 원형 큐 구현과 덱
- 해시 테이블: 해시 함수와 충돌 처리
- 트리와 이진 탐색 트리
- 힙(Heap)과 우선순위 큐
- 균형 이진 탐색 트리: AVL, Red-Black, B-Tree
- 그래프: 인접 행렬과 인접 리스트
- 최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*
- 최소 신장 트리(MST): Kruskal, Prim, Union-Find
- 정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지
- Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap
시간 복잡도
알고리즘의 절대적인 실행 시간이 아니라, 수행하는 데 연산이 몇 번 이루어지는지를 나타낸 것이다. 입력 데이터의 개수 n에 대한 함수로 표현하며 T(n)이라고 표기한다.
공간 복잡도
프로그램을 실행해 완료하는 데 필요한 자원 공간의 양이다. 총 공간 요구는 고정 공간과 가변 공간의 합이다.
S(P) = c + Sp(n)- 고정 공간(c): 입력과 출력의 횟수나 크기와 관계없이 필요한 공간이다. 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수가 여기에 속한다.
- 가변 공간(Sp(n)): 특정 인스턴스에 따라 크기가 달라지는 구조화 변수와, 함수가 순환 호출을 할 때 추가로 필요한 공간이다.
예를 들어 함수 내부에서 변수를 선언하고 그 함수를 재귀로 n번 호출하면, 호출마다 스택 프레임이 쌓이므로 공간 복잡도는 O(n)이다.
시간 복잡도는 “얼마나 빠르게 실행되는가”, 공간 복잡도는 “얼마나 많은 자원이 필요한가”에 대한 답이다.
점근적 표기법
Big-Ω (빅 오메가)
하한을 나타낸다. 실행 시간이 적어도 이만큼은 걸린다는 뜻이다.
Big-O (빅 오)
상한을 나타낸다. 실행 시간이 아무리 커져도 이보다 빠르게 증가하지는 않는다는 뜻이다.
Big-θ (빅 세타)
Big-O와 Big-Ω를 둘 다 만족하는 경우, 즉 상한과 하한이 같은 차수로 묶이는 경우를 의미한다.
Big-O를 사용하는 이유
- “실행 시간은 최대 이만큼 커지지만 더 천천히 커질 수도 있다”는 상한만 보장하면 되므로 다루기 편하다. 가장 딱 맞는 표현은 아닐 수 있어도 틀린 말은 아니다.
- 알고리즘을 평가할 때는 보통 최악의 경우에도 성능이 보장되는지가 중요하다.
- 실제 업계에서는 Big-O를 Big-θ처럼, 즉 가장 타이트한 상한을 가리키는 의미로 쓴다.
O(1)은 O(N)보다 무조건 빠른가
그렇지 않다. Big-O 표기법은 상수를 생략한다. 100단계를 거치는 연산도 O(100)이 아니라 O(1)로 표시한다.
따라서 n이 작을 때는 상수가 큰 O(1) 알고리즘이 O(N) 알고리즘보다 느릴 수 있다. Big-O는 n이 충분히 커졌을 때의 증가 추세를 비교하는 도구이다.