5-1. 복잡도 - 시간 복잡도, 공간 복잡도, 자료 구조에서의 시간 복잡도

1. 시간 복잡도

시간 복잡도란 알고리즘의 성능을 나타내고 효율성을 평가하는 핵심 지표로, 입력 데이터의 크기에 대해 알고리즘이 실행되는 데 걸리는 시간을 의미한다.

 

1) 빅오 표기법 (Big O Notation)

빅오 표기법은 시간 복잡도를 표현하는 가장 일반적인 방법이다. 입력 크기(n)가 무한대로 커질 때, 실행 시간에 가장 큰 영향을 미치는 최고차항만 남겨 간소화하여 표현한다. 이는 상수항과 영향력이 작은 항을 모두 제거하고, 실행 시간을 지배하는 성장률에 집중하는 것이다.

 

ex) T(n) = 2n^2 + 5n + 100의 시간 복잡도 : O(n^2)

 

2) 시간 복잡도별 속도 비교

표기법	명칭	성장률 (속도)	예시
O(1)	상수 시간	입력 크기와 무관하게 일정	배열에서 인덱스를 통해 원소 접근
O(log n)	로그 시간	n이 증가해도 매우 느리게 증가	이진 탐색
O(n)	선형 시간	n에 정비례하여 증가	배열의 모든 원소를 순차적으로 탐색
O(n log n)	선형 로그 시간	O(n)보다 조금 더 느리게 증가	효율적인 정렬 알고리즘 (Merge Sort, Heap Sort)
O(n^2)	제곱 시간	n의 제곱에 비례하여 급격히 증가	이중 반복문을 사용하는 비효율적인 정렬 (Bubble Sort)
O(2^n)	지수 시간	n이 조금만 커져도 매우 폭발적으로 증가	비효율적인 재귀 함수, 일부 동적 계획법
O(n!)	팩토리얼 시간	n이 매우 작아도 가장 빠르게 증가	외판원 문제(Traveling Salesman Problem)의 완전 탐색

 

 

 

2. 공간 복잡도

공간 복잡도는 알고리즘의 성능을 평가하는 지표 중 하나로, 입력 데이터의 크기에 따라 알고리즘이 실행되는 데 필요한 총 메모리 공간의 양을 의미한다.

 

1) 공간 복잡도의 구성 요소

- 고정 공간 : 입력 데이터의 크기와 무관하게 알고리즘 실행에 필요한 메모리 ex) 상수, 변수 등

- 가변 공간 : 입력 데이터의 크기나 재귀 호출의 깊이 등 실행 중 동적으로 변하는 메모리 ex) 힙, 재귀 호출 스택 등

 

 

 

3. 자료 구조에서의 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	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(1)	O(1)	O(1)
이진 탐색 트리	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드-블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)