[자료구조] 복잡도

자료구조란?

자료구조(Data Structure)는 데이터를 효율적으로 저장, 수정, 삭제, 탐색할 수 있도록 도와주는 데이터의 집합 및 구조입니다. 알고리즘과 함께 사용되며, 문제를 해결하는 기반이 됩니다.

 

---

복잡도란?

복잡도는 알고리즘이나 자료구조가 사용하는 시간(연산량)과 공간(메모리)을 측정하는 기준입니다.

 

1. 시간 복잡도(Time Complexity)

• 입력 크기(n)에 따라 알고리즘이 실행되는 데 걸리는 시간

 

2. 공간 복잡도(Space Complexity)

• 알고리즘이 실행될 때 필요로 하는 메모리 양

int a[1004]; // 1004개의 int → 1004 * 4 byte = 4016 byte

 

빅오(Big-O) 표기법

• 가장 영향력이 큰 항만을 남기고 상수와 하위 항을 제거한 표현법

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

 

---

자료구조에서의 평균 시간복잡도

자료구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)
스택(stack)	O(n)	O(n)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블(hash table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리(BST)	O(logn)	O(logn)	O(logn)	O(logn)
AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)
레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)

 

 

자료구조에서의 최악 시간복잡도

자료구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)
스택(stack)	O(n)	O(n)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(n)	O(n)
해시 테이블(hash table)	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리(BST)	O(logn)	O(logn)	O(logn)	O(logn)
AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)
레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)

✅ BST는 불균형하게 구성될 경우 O(n)이 될 수 있으므로 균형 잡힌 트리 구조(AVL, Red-Black)를 사용하는 것이 중요합니다.

---

마무리

복잡도 분석은 알고리즘의 효율성과 실행 가능성 판단의 기준이 됩니다. 적절한 자료구조 선택과 복잡도 고려는 프로그램 성능을 극대화하는 핵심 요소입니다.