시간복잡도 정의
O(1) - 상수
O(logN) - log
O(N) - 선형
O(NlogN) - 선형로그
O(N^c) - 다차
O(c^N) - 지수
O(N!) 팩토리얼
시간복잡도 표
| 시간 / N | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 1000 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| log N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 9.97 |
| N | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 1000 |
| N log N | 0 | 2 | 8 | 24 | 64 | 120 | 384 | 9966 |
| N^2 | 1 | 4 | 16 | 64 | 256 | 1024 | 4096 | 10^6 |
| N^3 | 1 | 8 | 64 | 512 | 4096 | 32768 | 262144 | 10^9 |
| 2^N | 2 | 4 | 16 | 256 | 65536 | 4294967296 | 약 1844 경 | 약 1.07 * 10^301 |
| N! | 1 | 2 | 24 | 40320 | 20922789888000 | 약 2.63 * 10^35 | 약 1.27 * 10^89 | 약 4.02 * 10^2567 |
Python의 built-in type 중 가장 흔히 쓰이는 list, set, dict 의 메소드의 시간복잡도는 아래와 같다.
List
example = list()| Operation | Example | Complexity | Note |
| Index | example[i] | O(1) | |
| Store | example[i] = 0 | O(1) | |
| Length | len(example) | O(1) | |
| Append | example.append(5) | O(1) | |
| Pop | example.pop() | O(1) | example.pop(-1) 와 동일 (끝 요소 pop) |
| Clear | example.clear() | O(1) | example = [] 과 유사 |
| Slice | example[a:b] | O(b-a) | example[1:5]: O(1) example[:]: O(len(example)-0)=O(N) |
| Extend | example.extend(...) | O(len(...)) | 확장할 길이에 따라 다르다 |
| check (==, !=) | example2 == example2 | O(N) | |
| Insert | example[a:b] = ... | O(N) | |
| Delete | del example[i] | O(N) | i 에 따라 다르다. 최악의 경우 O(N) |
| Containment | value in/not in example | O(N) | list 선형 탐색 |
| Copy | example.copy() | O(N) | example[:] 과 동일, O(N) |
| Remove | example.remove(...) | O(N) | |
| Pop | example.pop(i) | O(N) | example.pop(0): O(N) |
| Extreme value | min(example) / max(example) | O(N) | 값에 따라 list 선형 탐색 |
| Reverse | example.reverse() | O(N) | |
| Iteration | for v in example: ... | O(N) | 최악의 경우, loop에서 return/break 없음 |
| Sort | example.sort() | O(NlogN) | key/reverse 는 대부분 바뀌지 않는다 |
| Multiply | example * k | O(k N) | 5*1: O(N) len(example)*1: O(N**2) |
Set
example = set()
| Operation | Example | Complexity | Note |
| Index | example[i] | O(1) | |
| Store | example[i] = 0 | O(1) | |
| Length | len(example) | O(1) | |
| Append | example.append(5) | O(1) | |
| Pop | example.pop() | O(1) | example.pop(-1) 와 동일 (끝 요소 pop) |
| Clear | example.clear() | O(1) | example = [] 과 유사 |
| Slice | example[a:b] | O(b-a) | example[1:5]: O(1) example[:]: O(len(example)-0)=O(N) |
| Extend | example.extend(...) | O(len(...)) | 확장할 길이에 따라 다르다 |
| check (==, !=) | example2 == example2 | O(N) | |
| Insert | example[a:b] = ... | O(N) | |
| Delete | del example[i] | O(N) | i 에 따라 다르다. 최악의 경우 O(N) |
| Containment | value in/not in example | O(N) | list 선형 탐색 |
| Copy | example.copy() | O(N) | example[:] 과 동일, O(N) |
| Remove | example.remove(...) | O(N) | |
| Pop | example.pop(i) | O(N) | example.pop(0): O(N) |
| Extreme value | min(example) / max(example) | O(N) | 값에 따라 list 선형 탐색 |
| Reverse | example.reverse() | O(N) | |
| Iteration | for v in example: ... | O(N) | 최악의 경우, loop에서 return/break 없음 |
| Sort | example.sort() | O(NlogN) | key/reverse 는 대부분 바뀌지 않는다 |
| Multiply | example * k | O(k N) | 5*1: O(N) len(example)*1: O(N**2) |