- List functions time complexity
| Operation | Example | Big-O | Notes |
|---|
Index | I[i] | O(1) | |
len | len(I) | O(1) | |
append | I.append(5) | O(1) | |
pop | I.pop() | O(1) | I.pop(-1)과 동일함 |
clear | I.clear() | O(1) | I = []과 유사 |
[:](Slice) | I[a:b] | O(b-a) | I[:] = O(N) |
extend | I.extend(...) | O(len(...)) | 확장 길이에 따라 |
insert | I.insert(i, v) | O(N) | i위치까지 이동한 후 v를 삽입 |
delete | del I[i] | O(N) | |
remove | I.remove(...) | O(N) | |
containment | in or not in | O(N) | |
min or max | min(I), max(I) | O(N) | |
reverse | I.reverse() | O(N) | |
iteration | for v in I: | O(N) | |
sort | I.sort() | O(N log N) | |
- Dict functions time complexity
| Operation | Example | Big-O | Notes |
|---|
index | d[k] | O(1) | |
len | len(d) | O(1) | |
del | del d[k] | O(1) | |
pop | d.pop() | O(1) | |
popitem | d.popitem() | O(1) | |
clear | d.clear() | O(1) | |
containment | x in d | O(1) | |
iteration | for k in d: | O(N) | |
- set functions time complexity
| Operation | Example | Big-O | Notes |
|---|
x in s | | O(1) | |
union | | O(len(s)+len(t)) | |
intersection | | O(len(s)+len(t)) | |
difference | | O(len(s)+len(t)) | |
iteration | | O(N) | |
containment | | O(1) | |
주의사항 : List에서는 in 연산의 시간복잡도는 O(N)이지만 Set이나 Dict에서 in 연산의 시간복잡도는 O(1)이다.
https://wiki.python.org/moin/TimeComplexity
