파이썬 기본 연산 시간 복잡도 (Big O)
작성 완료
- 알고리즘의 시간 복잡도를 나타내는 척도
- 두 함수 $f$와 $g\,(g>0)$에 대해 상수 $k<\infty$가 존재해서 $x\in A \subset \mathbb{R}$인 $x$에 대하여 $\left|\frac{f(x)}{g(x)}\right|<K$이면 $f(x)=O(g(x))$임
- 쉽게 말하면 $f$는 $g$로부터 일정수준 이상 벗어날 수 없다는 뜻($f$나 $g$나 비슷비슷하다)
- $f(x) = 2x, \,g(x) = x$이면 $\left|\frac{f(x)}{g(x)}\right| = 2<\infty$이므로 $f(x) = O(g(x))$임 ---> $f$나 $g$나 비슷함
- 만약 $h(x) = x^2$이면 $\left|\frac{h(x)}{g(x)}\right| = |x|$이고 $x\to \infty$이면 $\left|\frac{h(x)}{g(x)}\right| \to \infty$이므로 $h(x) \neq O(g(x))$임 ---> $h$와 $g$는 급이 다름
| Operation | Example | Complexity Class | Notes |
|---|---|---|---|
| index | l[n] | $O(1)$ | |
| store | l[n] = 0 | $O(1)$ | store는 변수 저장 |
| length | len(l) | $O(1)$ | |
| append | l.append(5) | $O(1)$ | |
| pop | l.pop() | $O(1)$ | same as l.pop(-1) |
| clear | l.clear() | $O(1)$ | similar to l = [] |
| slice | l[a:b] | $O(b-a)$ | $l[1:5]\to O(l)$, $l[\;\; :\;\; ]\to O(len(l)-0)=O(N)$ |
| extend | l.extend(...) | $O(len(\dots))$ | depends only on len of extension |
| construction | list(...) | $O(len(\dots))$ | depends on length of ... iterable |
| check ==, != | l1 == l2 | $O(N)$ | |
| insert | l[a:b] = ... | $O(N)$ | |
| delete | del l[n] | $O(N)$ | depends on $n$; $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(n) | $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 does not change |
| multiply | $k \times l$ | $O(kN)$ | $5\times l$ is $O(N)$: $len(l)\times l$ is $O(N^2)$ |
| Operation | Example | Complexity Class | 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 | 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)$ |
| 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)$ | 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, Worst: no return/break in loop |