점프 업 파이썬’ 시리즈

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

  • 0
  • 0
0
0

최근 사고력의 향상을 위해서 꾸준하게 알고리즘 문제를 풀어보고 있다. 당연 필자가 가장 자신있는 언어라고 생각하는 파이썬을 응용하고 있는데 시간초과가 생각보다 많이 발생했다. O(1)로 접근할 수 있는 요소를 O(n)으로 접근하는 등 기본기의 부족으로 인함으로 보였다. 그리하여 파이썬의 각 자료형의 연산에 대한 복잡도를 어지간하면 숙지해 놓으려고 한다.

출처 : https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt


리스트

자료형 리스트의 각 연산별 복잡도

O(1)
연산자예시주석
Indexmy_list[i]연결 리스트라 당연히 O(1)이 아닐거라 생각했다. 그래서 일부러 딕셔너리로 해결한적도 많았는데... 파이썬을 너무 얕본 듯 하다.
Storemy_list[i] = 0이하 동문...
Lengthlen(my_list)아마도 내부적으로 길이 변수를 가지고 있는 듯 하다.
Appendmy_list.append(x)
Popmy_list.pop()스택으로 문제를 해결할 방안을 찾을 수 있다면 좋은 성능으로 해결할 수 있을 듯 보인다.
Clearmy_list.clear()my_list = [] 으로 빈 리스트를 생성하는 것도 동일한 복잡도를 가진다.
O(N)
연산자예시주석
Checkmy_list1 == my_list2이것은 충분히 이정도의 복잡도가 걸릴걸 예상하고 있었다. 😀
Insertmy_list[a:b] = ...-
Deletedel my_list[x]잠깐 del이 O(N) 이었다고? 리스트를 그간 연결 리스트라고 생각했는데 순차 리스트였나? 인덱스 교체를 위한 작업때문인 것으로 생각되는데... 여하지간 문제풀때 del을 남발하는 경우도 많았는데 주의해야 겠다.
Containmentx in my_list-
Copymy_list.copy()-
Removemy_list.remove(x)-
Popmy_list.pop(x)x라는 값을 pop하기 위해서는 정확히 N-x 만큼의 복잡도가 걸린다.
Extream valuemy_list.reverse()-
Iterationfor x in my_listbreakreturn이 없는 경우 최악
O(?)
연산자예시복잡도주석
Slicemy_list[a:b]O(b-a)-
Extendmy_list.extend(...)O(len(...))my_list1 + my_list2도 동일한 복잡도를 가질 것으로 생각된다. 배열의 길이만큼 append가 발생한다고 생각하면 기억하기 쉬울 것 같다.
Constructionlist(...)O(len(...))-
Sortmy_list.sort()O(N Log N)키/역순은 영향을 주지 않는다. 파이썬의 정렬은 각 자료의 상태에 따라서 적절한 정렬 알고리즘을 사용한다고 들었는데 자세한 내용은 모르겠다! (당당)
Multiplyx*my_listO(k N)-


집합

자료형 집합의 각 연산별 복잡도

O(1)
연산자예시주석
Lengthlen(my_set)-
Addmy_set.add(5)-
Containmentx in my_set-
Removemy_set.remove(...)-
Discardmy_set.discard(...)-
Popmy_set.pop()-
Clearmy_set.clear()my_set = set() 로 빈 집합을 생성해도 동일한 복잡도를 가진다.
O(N)
연산자예시주석
Iterationfor x in my_listbreakreturn이 없는 경우 최악의 복잡도를 가진다.
Copymy_list.copy()-
O(?)
연산자예시복잡도주석
Constructionset(...)O(len(...))-
Checks != tO(len(s))-
<= / <s <= tO(len(s))-
>= / >s >= tO(len(t))-
Unions \tO(len(s)+len(t))-
Intersections & tO(len(s)+len(t))-
Differences - tO(len(s)+len(t))-
Symmetric Diffs ^ tO(len(s)+len(t))-


딕셔너리

자료형 딕셔너리의 각 연산별 복잡도

O(1)
연산자예시주석
Indexmy_dict[k]-
Storemy_dict[k] = v-
Lengthlen(my_dict[k])-
Deletedel my_dict[k]-
Get / Setmy_dict.get(k)-
Popmy_dict.pop(k)-
Pop itemmy_dict.popitem()-
Celarmy_dict.clear()my_dict = dict() 로 비어있는 딕셔너리를 생성해도 동일한 복잡도를 가진다.
Viewmy_dict.keys()my_dict.values()도 동일한 복잡도를 가진다.
O(N)
연산자예시주석
Iterationfor key in my_dictall forms: keys, values, items
O(?)
연산자예시복잡도주석
Constructiondict(...)O(len(...))-

앞으로 문제를 풀때는 최대한 이 표를 기억하며 O(1)의 연산자로 풀이할 방안을 찾도록 해야겠다. 😅

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.