참고자료: Complexity of Python Operations
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) | |
Pop | l.pop() | O(1) | l.pop(-1) 과 동일 |
Clear | l.clear() | O(1) | l = [] 과 유사 |
Slice | l[a:b] | O(b-a) | l[:] → O(N) |
Extend | l.extend(…) | O(len(…) | 확장 길이에 따라 |
Construction | list(…) | O(len(…) | 요소 길이에 따라 |
check ==, != | l1 == l2 | O(N) | 비교 |
Insert | l.insert(i, v) | O(N) | i 위치에 v를 추가 |
Delete | del l[i] | O(N) | |
Remove | l.remove(…) | O(N) | |
Containment | x in/not in l | O(N) | 검색 |
Copy | l.copy() | O(N) | l[:]과 동일 |
Pop | l.pop(i) | O(N) | l.pop(0) → O(N) |
Extreme value | min(l) / max(l) | O(N) | 검색 |
Reverse | l.reverse() | O(N) | |
Iteration | for v in l: | O(N) | |
Sort | l.sort() | O(NlogN) | |
Multiply | k*l | O(kN) | [1,2,3] * 3 → 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) | list와 tuple에서는 O(N) |
Remove | s.remove(…) | O(1) | list와 tuple에서는 O(N) |
Discard | s.discard(…) | O(1) | |
Pop | s.pop() | O(1) | pop되는 value는 랜덤 |
Clear | s.clear() | O(1) | s = set() 과 유사 |
Construction | set(…) | O(len(…)) | 요소 길이에 따라 |
check ==, != | s != t | O(len(s)) | len(t)와 같음. 두 set의 길이가 다르면 O(1) |
<= / < | s <= t | O(len(s)) | issubset() |
>= / > | s >= t | O(len(t)) | issuperset() s<=t==t>=s |
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) | |
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.method | O(1) | |
Pop | d.pop(k) | O(1) | |
Pop item | d.popitem() | O(1) | pop되는 item은 랜덤 |
Clear | d.clear() | O(1) | s = {} / dict() 와 유사 |
View | d.keys() | O(1) | d.values() 와 동일 |
Construction | dict(…) | O(len(…)) | 요소 길이에 따라 |
Iteration | for k in d: | O(N) | |