Total
Search
시간 복잡도 비교
•
각 자료구조는 평균적인 경우(Average case)와 최악의 경우(Worst case)가 다를 수 있으므로, 보통 평균적/균등 분포 상황을 가정한 결과를 주로 표시
자료구조/알고리즘 | 검색(Search) | 삽입(Insertion) | 삭제(Deletion) |
순차 탐색(Linear Search) | O(n) | - | - |
이진 탐색(Binary Search) | O(log n) | - | - |
이진 탐색 트리(BST) (균형X, 일반) | 평균: O(log n)
최악: O(n) | 평균: O(log n)
최악: O(n) | 평균: O(log n)
최악: O(n) |
2-3-4 트리 (균형 트리) | O(log n) | O(log n) | O(log n) |
레드-블랙 트리(Red-Black Tree) (균형 트리) | O(log n) | O(log n) | O(log n) |
B-트리(B-Tree) | O(log n) | O(log n) | O(log n) |
해시 테이블(Hash Table) | 평균: O(1)
최악: O(n) | 평균: O(1)
최악: O(n) | 평균: O(1)
최악: O(n) |
요약
1.
순차 탐색(Linear Search)
•
검색: O(n)
•
원소를 하나씩 확인하므로, n개의 원소가 있으면 최대 n번 비교
2.
이진 탐색(Binary Search)
•
검색: O(log n)
•
정렬된 배열(또는 리스트)에서만 가능하며, 중간 원소와 비교하면서 반씩 범위를 줄여나감
3.
이진 탐색 트리(BST: Binary Search Tree)
•
검색, 삽입, 삭제: 평균적으로 O(log n)이지만, 트리가 편향되면 최악 O(n)
•
삽입 순서나 데이터 분포에 따라 트리가 한쪽으로 치우칠 수 있음
4.
균형 트리(2-3-4 트리, 레드블랙 트리 등)
•
검색, 삽입, 삭제: O(log n)
•
편향되지 않도록 스스로 균형을 맞추는 기법을 사용하기 때문에 항상 O(log n)을 보장
5.
B-트리(B-Tree)
•
검색, 삽입, 삭제: O(log n)
•
디스크 접근을 최소화하도록 설계된 트리 구조로, 데이터베이스나 파일시스템에서 많이 사용
6.
해시 테이블(Hash Table)
•
검색, 삽입, 삭제: 평균 O(1), 최악 O(n)
•
해시 충돌이 적고(이상적인 해시 함수) 해시 버킷 관리가 잘 되어 있으면 거의 상수 시간에 수행 가능
•
최악의 경우 충돌이 많아지면 한 해시 버킷 체인이 길어져 O(n) 이 될 수 있음
정리
•
빠른 탐색이 필요하고 요소가 동적으로 변할 수 있다면 균형 이진 탐색 트리(예: 레드블랙 트리)나 해시 테이블을 많이 사용
•
순차 탐색과 이진 탐색은 별도의 자료구조가 아닌, 리스트에서의 탐색 알고리즘이므로 상황에 맞게 사용
◦
이진 탐색은 정렬된 리스트가 필요
•
B-트리는 주로 디스크 접근 비용을 고려해야 하는 대용량 데이터베이스나 파일시스템에서 활용