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

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