Big O notation
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리듬의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.
대표적으로 다음의 다섯 가지 표기법이 있다.
- 대문자 O 표기법
- 소문자 o 표기법
- 대문자 오메가(Ω) 표기법
- 소문자 오메가(ω) 표기법
- 대문자 세타(Θ) 표기법
이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, 란다우 표기법('빅-오 표기법' 아닌가?)이라고도 한다.
표기법
알고리즘 수행시간에 따른 분석으로 주로, 빅O 표기법(Big-O Notation)을 사용한다.
- O(1): 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘.
- O(log N): 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
- O(N): 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
- O(N log N): 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.
- O(N2): 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.
- O(N3): 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.
- O(2n): 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.
- O(n!): 입력 자료의 크기가 N일경우 n(n-1)(n-2)... * 1(n!) 번만큼의 수행시간을 가진다.
ex) 외판원 문제(TSP)의 기본적인 해법.
실행시간 순서로 정렬하면 아래와 같다. (오른쪽으로 갈 수록 느리다)
BigO-graph.png
Big-O Cheat Sheet
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) |
| Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
| Θ(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) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(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) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | 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) |
| Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Array Sorting Algorithms
| Algorithm | Time Complexity | Space Complexity | ||
| Best | Average | Worst | Worst | |
| Ω(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) |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Ω(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) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) |
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(n) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
Big-O Cheat Sheet Poster
Big-o-cheat-sheet-poster.png
Time complexity
(Time complexity로 들어올 수 있다)
시간 복잡도(Time complexity)는 알고리즘의 수행시간 분석결과.
Space complexity
(Space complexity로 들어올 수 있다)
공간 복잡도(Space complexity)는 알고리즘의 메모리 사용량에 대한 분석결과.