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

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

baealex

  • 95%
  • 2

소비적인 일보단 생산적인 일을 추구하며, 좋아하는 일을 잘하고 싶어합니다 😀

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)의 연산자로 풀이할 방안을 찾도록 해야겠다. 😅

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