파이썬 자료형 연산자 시간복잡도

파이썬 자료형 연산자 시간복잡도

baealex

소비적인 일보단 생산적인 일을 좋아합니다.

Sign in to view email

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

작성된 댓글이 없습니다!
로그인된 사용자만 댓글을 작성할 수 있습니다.