자료 구조(data structure)
효율적으로 데이터를 관리하고, 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
자료구조 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열 (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) |
| 이중 연결 리스트 (doublylinked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 (hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 (BST) | 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) |
자료구조 최악 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열 (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) |
| 이중 연결 리스트 (doublylinked list) | O(n) | O(n) | O(n) | O(n) |
| 해시 테이블 (hash table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 (BST) | O(n) | O(n) | O(n) | O(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) |
'Computer Science > 자료구조' 카테고리의 다른 글
| Array(배열)과 List(리스트) 차이 (0) | 2023.05.13 |
|---|---|
| [자료구조] 우선순위 큐(Priority Queue) (0) | 2023.05.10 |