＃컴퓨터 과학 [Computer Science]/알고리즘 [Algorithm]
[알고리즘] ⏰ 주요 자료구조 시간 복잡도 (Time Complexity)
cy_mos
2024. 3. 5. 18:43
반응형
주요 자료구조에 대한 평균 시간 복잡도는 아래의 도표와 같습니다.
| 평균 시간 복잡도 (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
반응형