-> 블로그 이전

[Data Structure] 자료구조별 시간복잡도

2021. 12. 31. 14:03Major`/자료구조

728x90
반응형
자료구조 시간복잡도
평균 최악
접근 탐색 삽입 삭제 접근 탐색 삽입 삭제
Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n)
Stack O(n) O(n) O(1) O(1)
- pop
O(n)
- remove
O(n) O(n) O(1) O(1)
- pop
O(n)
- remove
Queue O(n) O(n) O(1) O(1)
- dequeue
O(n)
- remove
O(n) O(n) O(1) O(1)
- dequeue
O(n)
- remove
Deque O(n) O(n) O(1) O(1)
- pop
O(n)
- remove
O(n) O(n) O(1) O(1)
- pop
O(n)
- remove
Singly
Linked
List
O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1)
Doubly
Linked
List
O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1)
Circular
Linked
List
O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1)
Heap O(1)
- max/min
O(1)
- max/min
O(log n) O(log n) O(1)
- max/min
O(1)
- max/min
O(log n) O(log n)
Binary
Search
Tree
O(log n) O(log n) O(log n) O(log n) O(n) O(n) O(n) O(n)
Red
Black
Tree
O(log n) O(log n) O(log n) O(log n) O(log n) O(log n) O(log n) O(log n)

 

728x90
반응형