Python - List, Set, Dict 자료형에 따른 시간 복잡도
작성일
백준 1920번 수 찾기 문제를 풀면서 list 안에서 특정 값을 찾을 땐 시간 초과….
set 안에서 특정 값을 찾을 땐 통과!!
이런 상황을 겪고 나니 시간복잡도에 대한 생각이 더 필요하다고 느껴졌음
Complexity of Python Operations 를 보면 삽입(insert, pop), 제거(delete, remove), 탐색(check==, $\ne$), 포함 여부 확인(containment) 의 경우 List 자료형의 경우 모두 시간 복잡도 $O(N)$ 이고 Set, Dict 는 $O(1)$ 임을 확인할 수 있음
따라서 삽입, 제거, 탐색, 포함 여부 확인과 같은 연산이 필요한 알고리즘 문제에서 시간초과가 나는 경우 List 보다는 Set 이나 Dict 자료형을 사용해야 함을 기억하자!
List
| Operation | Example | Big-O | Notes |
|---|---|---|---|
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | mostly: ICS-46 covers details |
| Pop | l.pop() | O(1) | same as l.pop(-1), popping at end |
| Clear | l.clear() | O(1) | similar to l = [] |
| Slice | l[a:b] | O(b-a) | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N) |
| Extend | l.extend(…) | O(len(…)) | depends only on len of extension |
| Construction | list(…) | O(len(…)) | depends on length of … iterable |
| check | ==, != l1 == l2 | O(N) | |
| Insert | l[a:b] = … | O(N) | |
| Delete | del l[i] | O(N) | depends on i; O(N) in worst case |
| Containment | x in/not in l | O(N) | linearly searches list |
| Copy | l.copy() | O(N) | Same as l[:] which is O(N) |
| Remove | l.remove(…) | O(N) | |
| Pop | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) (see above) |
| Extreme | value min(l)/max(l) | O(N) | linearly searches list for value |
| Reverse | l.reverse() | O(N) | |
| Iteration | for v in l: | O(N) | Worst: no return/break in loop |
| Sort | l.sort() | O(N Log N) | key/reverse mostly doesn’t change |
| Multiply | k*l | O(k N) | 5l is O(N): len(l)l is O(N**2) |
Set
| Operation | Example | Big-O | Notes |
|---|---|---|---|
| Length | len(s) | O(1) | |
| Add | s.add(5) | O(1) | |
| Containment | x in/not in s | O(1) | compare to list/tuple - O(N) |
| Remove | s.remove(..) | O(1) | compare to list/tuple - O(N) |
| Discard | s.discard(..) | O(1) | |
| Pop | s.pop() | O(1) | popped value “randomly” selected |
| Clear | s.clear() | O(1) | similar to s = set() |
| Construction | set(…) | O(len(…)) | depends on length of … iterable |
| check | ==, != s != t | O(len(s)) | same as len(t); False in O(1) if the lengths are different |
| <=/< | s <= t | O(len(s)) | issubset |
| />=/> | s >= t | O(len(t)) | issuperset s <= t == t >= s |
| Union | s $\mid$ 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) | Worst: no return/break in loop |
| Copy | s.copy() | O(N) |
Dict
| Operation | Example | Big-O | 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) | similar to s = {} or = dict() |
| View | d.keys() | O(1) | same for d.values() |
| Construction | dict(…) | O(len(…)) | depends # (key,value) 2-tuples |
| Iteration | for k in d: | O(N) | all forms: keys, values, items |
댓글남기기