-> 블로그 이전

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

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

목차

    자료구조 시간복잡도
    평균 최악
    접근 탐색 삽입 삭제 접근 탐색 삽입 삭제
    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)