반응형
주요 자료구조에 대한 평균 시간 복잡도는 아래의 도표와 같습니다.
| 평균 시간 복잡도 (Aveage Time Complexity) | 접근 (Access) | 탐색 (Search) | 삽입 (Insert) | 삭제 (Delete) |
| 배열 (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) |
| 이진 탐색 트리 (Binary Search Tree) | 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) |
주요 자료구조에 대한 최악의 시간 복잡도는 아래의 도표와 같습니다.
| 평균 시간 복잡도 (Aveage Time Complexity) | 접근 (Access) | 탐색 (Search) | 삽입 (Insert) | 삭제 (Delete) |
| 배열 (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(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 (Binary Search Tree) | 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) |
🚀 REFERENCE
반응형
'＃컴퓨터 과학 [Computer Science] > 알고리즘 [Algorithm]' 카테고리의 다른 글
| [알고리즘] 허프만 압축 알고리즘 (Huffman Coding Algorithm) (0) | 2024.09.02 |
|---|---|
| [알고리즘] 📚 용어 정리 (0) | 2024.03.05 |
| [Algorithm - Concept] AVL Tree (named after inventors Adelson-Velsky and Landis) (0) | 2019.09.04 |
| [탐색] 깊이 우선 탐색 (DFS, Depth First Search) (0) | 2019.08.29 |
| [Algorithm - Concept] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) (0) | 2019.08.29 |
댓글