반응형
파이썬의 시간 복잡도
I. 시간 복잡도
알고리즘이 문제 해결을 위해 사용한 시간(연산)의 경과시간(횟수)를 의미하며 보통 점근표기법(Big-O)으로 표현하는 경우가 많음
1. 알고리즘에서의 Big - O
Big-O의 정의는 어떤 함수 f(x), g(x) 가 존재할 때, x > k 인 경우 |f(x)| <= C * |g(x)| 를 만족한다면 f(x) is O(g(x)) 이다.(= 이 아닌 is 임을 유의)
따라서 만약 우리의 알고리즘이 n개의 수행에 대해 n^2+100 번 수행된다면 그냥 O(n^2) 의 복잡도를 갖는다고 표현하는 것이다.
II. 데이터 유형별 시간복잡도
1. List/tuple
| Operation | Example | Complexity Class | Notes |
|---|---|---|---|
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | |
| Pop | l.pop() | O(1) | |
| Pop | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) |
| Clear | l.clear() | O(1) | l = [] 와 동일 |
| Slice | l[a:b] | O(b-a) | |
| Extend | l.extend(...) | O(len(...)) | extension 길이에 따라 유동적 |
| Construction | list(...) | O(len(...)) | ...에 포함되는 자료의 길이에 연관 |
| check ==, != | l1 == l2 | O(N) | |
| Insert | l[a:b] = ... | O(N) | |
| Delete | del l[i] | O(N) | 지정한 index 길이에 영향 |
| Copy | l.copy() | O(N) | l2 = l[:] 과 동일 |
| Remove | l.remove(...) | O(N) | |
| min/max | min(l)/max(l) | O(N) | 리스트 전체를 모두 조회하기 때문 |
| Reverse | l.reverse() | O(N) | |
| Iteration | for v in l: | O(N) | loop에서 종료되거나 return되는게 없는 경우 가장 큰 복잡도를 갖음 |
| Sort | l.sort() | O(N Log N) | key/reverse mostly doesn't change |
| Multiply | k * l | O(k N) | 5 * l ==> O(N): len(l)l == O(N*2) |
- 튜플은 데이터 구조가 변경되지 않는 연산에서 list와 동일한 시간 복잡성을 갖음
2. Dict
| Operation | Example | Complexity Class | Notes |
|---|---|---|---|
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| get/setdefault | d.get(k) | O(1) | |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | popped item "randomly" selected |
| Clear | d.clear() | O(1) | d = {} or = dict() 와 동일 |
| View | d.keys(), d.values() | O(1) | |
| Construction | dict(...) | O(len(...)) | (key,value) 갯수로 결정 |
| Iteration | for k in d: | O(N) | keys, values, items 모두 동일하며 return/break 이 없는 경우 가장 복잡 |
- collections.defaultdict 도 동일한 시간 복잡성을 갖음
3. (Frozen)set
| Operation | Example | Complexity Class | Notes |
|---|---|---|---|
| Length | len(s) | O(1) | |
| Add | s.add(5) | O(1) | |
| Containment | x in/not in s | O(1) | list/tuple은 O(N) |
| Remove | s.remove(..) | O(1) | list/tuple은 O(N) |
| Discard | s.discard(..) | O(1) | |
| Pop | s.pop() | O(1) | popped value "randomly" selected |
| Clear | s.clear() | O(1) | s = set() 과 동일 |
| Construction | set(...) | O(len(...)) | ... 에 포함되는 자료 길이에 영향 |
| check ==, != | s != t | O(len(s)) | same as len(t) 길이가 다른 경우 O(1) |
| <=/< | s <= t | O(len(s)) | |
| >=/> | s >= t | O(len(t)) | |
| Union | s | t | O(len(s)+len(t)) |
| Intersection | s & t | O(len(s)+len(t)) | |
| Difference | s - t | O(len(s)+len(t)) | |
| Symmetric Diff | s ^ t | O(len(s)+len(t)) | |
| Iteration | for v in s: | O(N) | |
| Copy | s.copy() | O(N) |
참고문헌
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
반응형