O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^n) < O(n!)
O(1)
- append()
- deque.popleft()
O(logN)
- 이진 트리 탐색, 우선순위큐PriorityQueue()힙정렬
O(N)
- 투포인터(부분합)
- 변수명.count(특정값)
- max(), min()
O(NlogN)
- 퀵정렬, 머지정렬 등 ,heappush랑 heappop은 O(nlogn) 우선순위큐의 put,get도
- 변수명.sort()
O(N^2)
- 버블 정렬, 삽입정렬 등
O(N^3)
- 편상관관계 계산 등
O(2^n)
- 피보나치, Brutal Force 등
O(n!)
- 완전탐색(Brutal Force)무작위 대입
- 순열, 조합, 백트래킹
list
| Operation | Average Case | Amortized Worst Case |
| Copy | O(n) | O(n) |
| Append[1] | O(1) | O(1) |
| Pop last | O(1) | O(1) |
| Pop intermediate[2] | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Set Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(k+n) |
| Extend[1] | O(k) | O(k) |
| Sort | O(n log n) | O(n log n) |
| Multiply | O(nk) | O(nk) |
| x in s | O(n) | |
| min(s), max(s) | O(n) | |
| Get Length | O(1) | O(1) |
collections.deque
| Operation | Average Case | Amortized Worst Case |
| Copy | O(n) | O(n) |
| append | O(1) | O(1) |
| appendleft | O(1) | O(1) |
| pop | O(1) | O(1) |
| popleft | O(1) | O(1) |
| extend | O(k) | O(k) |
| extendleft | O(k) | O(k) |
| rotate | O(k) | O(k) |
| remove | O(n) | O(n) |
| Get Length | O(1) | O(1) |
set
| Operation | Average case | Worst Case | notes |
| x in s | O(1) | O(n) | |
| Union s|t | O(len(s)+len(t)) | ||
| Intersection s&t | O(min(len(s), len(t))) | O(len(s) * len(t)) | replace "min" with "max" if t is not a set |
| Multiple intersection s1&s2&..&sn | (n-1)*O(l) where l is max(len(s1),..,len(sn)) | ||
| Difference s-t | O(len(s)) | ||
| s.difference_update(t) | O(len(t)) | ||
| Symmetric Difference s^t | O(len(s)) | O(len(s) * len(t)) | |
| s.symmetric_difference_update(t) | O(len(t)) | O(len(t) * len(s)) |
dict
| Operation | Average Case | Amortized Worst Case |
| k in d | O(1) | O(n) |
| Copy[3] | O(n) | O(n) |
| Get Item | O(1) | O(n) |
| Set Item[1] | O(1) | O(n) |
| Delete Item | O(1) | O(n) |
| Iteration[3] | O(n) | O(n) |