주요 자료구조의 시간복잡도

 

 

들어가며

프로그래밍 초창기에는 시간도 중요했지만, 공간도 매우 중요했습니다. 지금처럼 고사양 메모리와 하드디스크를 저렴한 가격에 살 수 없었기 때문이죠. 그당시에는 용량이 충분한 메모리도 없었습니다. 따라서 변수와 함수를 선언하거나 사용할 때도 불필요한 부분을 만들지 않았으며 프로그램 실행파일의 용량도 중요했죠. 컴퓨터가 발전하면서 지금은 공간에 대한 제약은 거의 없다고해도 무방합니다. 그러니 더욱 시간에 대한 중요도가 올라가기도 했죠. 시간복잡도는 빅오(Big-O)라는 표현방식을 대부분 사용합니다. 어떤 알고리즘이 실행되는데 가장 최악의 조건인 상태로 얼마나 걸리냐를 판단하는 지표입니다. 주로 사용하는 자료구조에 대한 시간복잡도를 알아보겠습니다.

다음은 주요 자료구조의 연산별 시간복잡도입니다.

 

---

 

배열 (Array)

	평균	최악
접근 (Access)	O(1)	O(1)
탐색 (Search)	O(n)	O(n)
삽입 (Insert)	O(n)	O(n)
삭제 (Delete)	O(n)	O(n)

• 배열은 인덱스를 이용한 접근이 O(1) 로 빠름.
• 중간 삽입/삭제 시 요소들을 이동해야 하므로 O(n).

 

---

 

연결 리스트 (Linked List)

	평균	최악
접근 (Access)	O(n)	O(n)
탐색 (Search)	O(n)	O(n)
삽입 (Insert)	O(1)	O(1)
삭제 (Delete)	O(1)	O(1)

• 단일 연결 리스트는 특정 노드에 대한 접근이 O(n) (순차 탐색 필요).
• 그러나 처음(head)이나 끝(tail)에서 삽입/삭제는 O(1).

 

---

 

해시 테이블 (Hash Table)

	평균	최악
접근 (Access)	-	O(n)
탐색 (Search)	O(1)	O(n)
삽입 (Insert)	O(1)	O(n)
삭제 (Delete)	O(1)	O(n)

• 해시 충돌이 발생하면 O(n) (모든 항목이 같은 버킷에 할당된 경우).
• 적절한 해싱과 충돌 해결 기법(체이닝, 개방 주소법 등)을 사용하면 평균적으로 O(1).

---

 

이진 탐색 트리 (Binary Search Tree, BST)

	평균	최악
접근 (Access)	O(log n)	O(n)
탐색 (Search)	O(log n)	O(n)
삽입 (Insert)	O(log n)	O(n)
삭제 (Delete)	O(log n)	O(n)

• 트리가 균형을 이루면 O(log n).
• 한쪽으로 치우친 경우(편향 트리) O(n).

✅ 균형 이진 탐색 트리 (AVL, Red-Black Tree) → O(log n) 보장.

 

---

 

힙 (Heap)

	평균	최악
접근 (Access)	O(1)	O(1)
삽입 (Insert)	O(log n)	O(log n)
삭제 (Delete)	O(log n)	O(log n)

• 최소/최대 힙에서 최솟값/최댓값 접근은 O(1).
• 삽입/삭제 시 힙 속성을 유지해야 하므로 O(log n).
  
  

---

 

스택 (Stack)

	평균	최악
접근 (Access)	O(n)	O(n)
탐색 (Search)	O(n)	O(n)
삽입 (Push)	O(1)	O(1)
삭제 (Pop)	O(1)	O(1)

• LIFO (Last In, First Out) 구조.
• 삽입/삭제는 top에서만 수행되므로 O(1).
• 임의 접근이나 탐색은 선형 탐색이 필요하므로 O(n).
  
  

---

 

큐 (Queue)

	평균	최악
접근 (Access)	O(n)	O(n)
탐색 (Search)	O(n)	O(n)
삽입 (Enqueue)	O(1)	O(1)
삭제 (Dequeue)	O(1)	O(1)

• FIFO (First In, First Out) 구조.
• 삽입(Enqueue)과 삭제(Dequeue)는 O(1).
• 탐색 및 임의 접근은 O(n).
  
  

---

 

우선순위 큐 (Priority Queue)

	평균	최악
접근 (Access)	O(1)	O(1)
삽입 (Enqueue)	O(log n)	O(log n)
삭제 (Dequeue)	O(log n)	O(log n)

• 우선순위가 높은 요소가 먼저 나가는 Heap 기반 큐.
• 힙(Heap)으로 구현하면 삽입/삭제 O(log n).
• 최댓값/최솟값 조회는 O(1).
  
  

---

 

덱 (Deque, Double-Ended Queue)

	평균	최악
접근 (Access)	O(n)	O(n)
탐색 (Search)	O(n)	O(n)
앞쪽 삽입 (Push front)	O(1)	O(1)
뒤쪽 삽입 (Push back)	O(1)	O(1)
앞쪽 삭제 (Pop front)	O(1)	O(1)
뒤쪽 삭제 (Pop back)	O(1)	O(1)

• 양쪽에서 삽입/삭제 가능.
• std::deque 사용 시 O(1) 보장.

 

---

 

그래프 (Graph)

	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
저장 공간	O(V²)	O(V + E)
간선 확인 (Check Edge)	O(1)	O(degree)
인접 노드 탐색	O(V)	O(degree)

• V: 정점 개수, E: 간선 개수.
• 탐색 알고리즘:
  • BFS, DFS: O(V + E)
  • 다익스트라: O((V + E) log V) (우선순위 큐 사용)

 

---

 

정리

• 빠른 접근: 배열 O(1), 해시 테이블 O(1)
• 빠른 삽입/삭제: 연결 리스트 O(1), 해시 테이블 O(1)
• 정렬된 데이터 탐색: 이진 탐색 트리 O(log n)
• 최솟값/최댓값 유지: 힙 O(log n)
• 문자열 검색: 트라이 O(m)
• 그래프 탐색: DFS/BFS O(V + E)