**자료구조(Data Structure)**란 메모리 공간 상에 데이터를 효율적으로 저장, 조직, 관리하는 구조적 방식입니다. 효율적인 자료구조 선택은 프로그램의 실행 속도와 메모리 사용량을 좌우합니다.
1. 자료구조 및 복잡도 용어 사전 (Glossary)
- ADT (Abstract Data Type, 추상 데이터 타입): 데이터의 구체적인 메모리 구현 방식을 숨기고, 데이터 구조가 지원하는 연산(Operation)의 인터페이스만을 정의한 개념입니다.
- Big-O Notation (빅오 표기법): 알고리즘의 최악의 경우(Worst-Case) 입력 크기 $N$에 따른 연산 횟수의 증가율을 상한선 점근 기호로 표현한 척도입니다.
- Time Complexity (시간 복잡도): 입력값의 크기 $N$에 따라 알고리즘이 완료되는 데 걸리는 총 연산 수행 횟수입니다.
- Space Complexity (공간 복잡도): 알고리즘을 실행할 때 추가로 요구되는 메모리 공간의 양입니다.
2. 주요 시간 복잡도 계층 비교표
| 복잡도 표기 | 명칭 (Name) | 대표적인 알고리즘 / 연산 | $N=1,000$ 시 연산 횟수 |
|---|---|---|---|
| $O(1)$ | 상수 시간 (Constant) | 배열 인덱스 접근, 파이썬 딕셔너리 키 조회 | 1 |
| $O(log N)$ | 로그 시간 (Logarithmic) | 이진 탐색 (Binary Search), 힙 삽입/삭제 | $approx 10$ |
| $O(N)$ | 선형 시간 (Linear) | 배열 전체 순회, 단일 연결 리스트 검색 | 1,000 |
| $O(N log N)$ | 선형 로그 시간 | 병합 정렬 (Merge Sort), 퀵 정렬 평균 | $approx 10,000$ |
| $O(N^2)$ | 이차 시간 (Quadratic) | 이중 루프, 버블 정렬, 선택 정렬 | $1,000,000$ |
| $O(2^N)$ | 지수 시간 (Exponential) | 재귀적 피보나치 수열 calculation | $approx 10^{301}$ |
3. 파이썬 기본 자료구조 연산 시간 복잡도 코드 측정
import time
# O(1) 접근 vs O(N) 검색 실습
data_list = list(range(10_000_000))
data_set = set(data_list)
# 1. List 검색 (O(N))
start = time.time()
exists_list = 9_999_999 in data_list
end = time.time()
print(f"List 'in' 검색 소요 시간: {(end - start)*1000:.3f}ms")
# 2. Set 검색 (O(1))
start = time.time()
exists_set = 9_999_999 in data_set
end = time.time()
print(f"Set 'in' 검색 소요 시간: {(end - start)*1000:.3f}ms")
4. 자주 묻는 질문 (Q&A)
Q. Big-O 표기법에서 계수와 낮은 차수의 항을 무시하는 이유는 무엇인가요? A. 입력 크기 $N$이 무한히 커짐에 따라 최고차항이 연산 시간에 미치는 영향이 절대적이므로, 상한선의 증가 추세를 직관적으로 비교하기 위해 상수 계수와 하위 항을 무시(점근적 분석)합니다.