최근 사고력의 향상을 위해서 꾸준하게 알고리즘 문제를 풀어보고 있다. 당연 필자가 가장 자신있는 언어라고 생각하는 파이썬을 응용하고 있는데 시간초과가 생각보다 많이 발생했다. 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)의 연산자로 풀이할 방안을 찾도록 해야겠다. 😅
Ghost