최근 사고력의 향상을 위해서 꾸준하게 알고리즘 문제를 풀어보고 있다. 당연 필자가 가장 자신있는 언어라고 생각하는 파이썬을 응용하고 있는데 시간초과가 생각보다 많이 발생했다. O(1)로 접근할 수 있는 요소를 O(n)으로 접근하는 등 기본기의 부족으로 인함으로 보였다. 그리하여 파이썬의 각 자료형의 연산에 대한 복잡도를 어지간하면 숙지해 놓으려고 한다.
출처 : https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
리스트
자료형 리스트의 각 연산별 복잡도
O(1)
| 연산자 |
예시 |
주석 |
| Index |
my_list[i] |
연결 리스트라 당연히 O(1)이 아닐거라 생각했다. 그래서 일부러 딕셔너리로 해결한적도 많았는데... 파이썬을 너무 얕본 듯 하다. |
| Store |
my_list[i] = 0 |
이하 동문... |
| Length |
len(my_list) |
아마도 내부적으로 길이 변수를 가지고 있는 듯 하다. |
| Append |
my_list.append(x) |
|
| Pop |
my_list.pop() |
스택으로 문제를 해결할 방안을 찾을 수 있다면 좋은 성능으로 해결할 수 있을 듯 보인다. |
| Clear |
my_list.clear() |
my_list = [] 으로 빈 리스트를 생성하는 것도 동일한 복잡도를 가진다. |
O(N)
| 연산자 |
예시 |
주석 |
| Check |
my_list1 == my_list2 |
이것은 충분히 이정도의 복잡도가 걸릴걸 예상하고 있었다. 😀 |
| Insert |
my_list[a:b] = ... |
- |
| Delete |
del my_list[x] |
잠깐 del이 O(N) 이었다고? 리스트를 그간 연결 리스트라고 생각했는데 순차 리스트였나? 인덱스 교체를 위한 작업때문인 것으로 생각되는데... 여하지간 문제풀때 del을 남발하는 경우도 많았는데 주의해야 겠다. |
| Containment |
x in my_list |
- |
| Copy |
my_list.copy() |
- |
| Remove |
my_list.remove(x) |
- |
| Pop |
my_list.pop(x) |
x라는 값을 pop하기 위해서는 정확히 N-x 만큼의 복잡도가 걸린다. |
| Extream value |
my_list.reverse() |
- |
| Iteration |
for x in my_list |
break나 return이 없는 경우 최악 |
O(?)
| 연산자 |
예시 |
복잡도 |
주석 |
| Slice |
my_list[a:b] |
O(b-a) |
- |
| Extend |
my_list.extend(...) |
O(len(...)) |
my_list1 + my_list2도 동일한 복잡도를 가질 것으로 생각된다. 배열의 길이만큼 append가 발생한다고 생각하면 기억하기 쉬울 것 같다. |
| Construction |
list(...) |
O(len(...)) |
- |
| Sort |
my_list.sort() |
O(N Log N) |
키/역순은 영향을 주지 않는다. 파이썬의 정렬은 각 자료의 상태에 따라서 적절한 정렬 알고리즘을 사용한다고 들었는데 자세한 내용은 모르겠다! (당당) |
| Multiply |
x*my_list |
O(k N) |
- |
집합
자료형 집합의 각 연산별 복잡도
O(1)
| 연산자 |
예시 |
주석 |
| Length |
len(my_set) |
- |
| Add |
my_set.add(5) |
- |
| Containment |
x in my_set |
- |
| Remove |
my_set.remove(...) |
- |
| Discard |
my_set.discard(...) |
- |
| Pop |
my_set.pop() |
- |
| Clear |
my_set.clear() |
my_set = set() 로 빈 집합을 생성해도 동일한 복잡도를 가진다. |
O(N)
| 연산자 |
예시 |
주석 |
| Iteration |
for x in my_list |
break나 return이 없는 경우 최악의 복잡도를 가진다. |
| Copy |
my_list.copy() |
- |
O(?)
| 연산자 |
예시 |
복잡도 |
주석 |
| Construction |
set(...) |
O(len(...)) |
- |
| Check |
s != t |
O(len(s)) |
- |
| <= / < |
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)) |
- |
딕셔너리
자료형 딕셔너리의 각 연산별 복잡도
O(1)
| 연산자 |
예시 |
주석 |
| Index |
my_dict[k] |
- |
| Store |
my_dict[k] = v |
- |
| Length |
len(my_dict[k]) |
- |
| Delete |
del my_dict[k] |
- |
| Get / Set |
my_dict.get(k) |
- |
| Pop |
my_dict.pop(k) |
- |
| Pop item |
my_dict.popitem() |
- |
| Celar |
my_dict.clear() |
my_dict = dict() 로 비어있는 딕셔너리를 생성해도 동일한 복잡도를 가진다. |
| View |
my_dict.keys() |
my_dict.values()도 동일한 복잡도를 가진다. |
O(N)
| 연산자 |
예시 |
주석 |
| Iteration |
for key in my_dict |
all forms: keys, values, items |
O(?)
| 연산자 |
예시 |
복잡도 |
주석 |
| Construction |
dict(...) |
O(len(...)) |
- |
앞으로 문제를 풀때는 최대한 이 표를 기억하며 O(1)의 연산자로 풀이할 방안을 찾도록 해야겠다. 😅