자료구조 인터뷰 준비용

자료구조 인터뷰 준비용

Common Data Structure Operations

Data Structure Time Complexity Space Complexity

Average Worst Worst

Access Search Insertion Deletion Access Search Insertion Deletion

Array `Θ(1)` `Θ(n)` `Θ(n)` `Θ(n)` `O(1)` `O(n)` `O(n)` `O(n)` `O(n)`

Stack `Θ(n)` `Θ(n)` `Θ(1)` `Θ(1)` `O(n)` `O(n)` `O(1)` `O(1)` `O(n)`

Queue `Θ(n)` `Θ(n)` `Θ(1)` `Θ(1)` `O(n)` `O(n)` `O(1)` `O(1)` `O(n)`

Singly-Linked List `Θ(n)` `Θ(n)` `Θ(1)` `Θ(1)` `O(n)` `O(n)` `O(1)` `O(1)` `O(n)`

Hash Table `N/A` `Θ(1)` `Θ(1)` `Θ(1)` `N/A` `O(n)` `O(n)` `O(n)` `O(n)`

Binary Search Tree `Θ(log(n))` `Θ(log(n))` `Θ(log(n))` `Θ(log(n))` `O(n)` `O(n)` `O(n)` `O(n)` `O(n)`

B-Tree `Θ(log(n))` `Θ(log(n))` `Θ(log(n))` `Θ(log(n))` `O(log(n))` `O(log(n))` `O(log(n))` `O(log(n))` `O(n)`

Array Sorting Algorithms

Algorithm Time Complexity Space Complexity

Best Average Worst Worst

Quicksort `Ω(n log(n))` `Θ(n log(n))` `O(n^2)` `O(log(n))`

Mergesort `Ω(n log(n))` `Θ(n log(n))` `O(n log(n))` `O(n)`

Heapsort `Ω(n log(n))` `Θ(n log(n))` `O(n log(n))` `O(1)`

Bubble Sort `Ω(n)` `Θ(n^2)` `O(n^2)` `O(1)`

Insertion Sort `Ω(n)` `Θ(n^2)` `O(n^2)` `O(1)`

Selection Sort `Ω(n^2)` `Θ(n^2)` `O(n^2)` `O(1)`

Radix Sort `Ω(nk)` `Θ(nk)` `O(nk)` `O(n+k)`

Quicksort의 Space Complexity가 O(logn)인 이유: recursion이므로 log(n)만큼 반복되는데, 매 recursion마다 constant 사이즈의 stack frame이 할당되므로 O(logn)이다.

Mergesort의 Space Compelxity가 O(n)인 이유: Quicksort와 같은 recursion형태이므로 log(n)같지만 merge를 하는 과정에서 auxiliary array를 사용하기 때문에 O(n)이다.

Merge Sort: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

댓글