728x90
반응형
자료구조의 평균 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
자료구조 최악의 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 | O(n) | O(n) | O(n) | O(n) |
해시 테이블과 이진 탐색 트리만 상이하다.
728x90
반응형
'알고리즘 > 자료구조' 카테고리의 다른 글
| 그리디 알고리즘 (0) | 2023.08.28 |
|---|---|
| 자료구조 - 연결 리스트 (2) | 2023.07.07 |
| 자료구조 - 배열 (0) | 2023.07.05 |
댓글