[python] Operations 별 시간복잡도(TimeComplexity) - list, set, dictionary

가능한 외우자..

 

l : List = []

Operation	Example	Complexity	Notes
Index	l[i]	O(1)	List 인덱스
Store	l[i] = 0	O(1)	인덱스 지정 저장
Length	len(l)	O(1)	List 크기
Append	l.append(j)	O(1)	List 값 추가
Pop - last	l.pop()	O(1)	인덱스 없이 가장 마지막 값 pop하는 경우만
Clear	l.clear()	O(1)	l=[] 랑 똑같음
Slice	l[a:b]	O(b-a)	l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend	l.extend(...)	O(len(...))	extension의 길이에 의존
Construction	list(...)	O(len(...))	(...) iterable의 길이에 의존
check ==, !=	l1 == l2	O(n)	리스트 비교 연산
Insert	l[a:b] = ...	O(n)	특정 범위 or 위치에 Insert
Delete	del l[i]	O(n)  in worst case	인덱스i에 의존
Containment	x in/not in l	O(n)	인덱스 내부 값 검사
Copy	l.copy()	O(n)	l[:]를 할당하는거랑 똑같음
Remove	l.remove(...)	O(n)	리스트
Pop - index	l.pop(i)	O(n)	O(n-i): 임 l.pop(0): O(n)
Extream value	min(l), max(l)	O(n)	검색이나 마찬가지..
Reverse	l.reverse()	O(n)
Iteration	for v in l:	O(n)	Worst: 당연히 무한루프..
Sort	l.sort()	O(n log n )	정렬
Multiply	k * l	O(k n)	5*l 은 O(n): len(l)*l은 O(n**2)

튜플(Tuple)도 List랑 똑같다

 

 

Sets

set은 list 또는 tuple에 비해 O(1) 작업이 더 많다.

set의 특정 순서로 값을 유지할 필요가 없으면(list/tuple은 순서가 필요함..) 일부 set 작업을 더 빠르게 구현할 수 있음

Operation	Example	Complexity	Notes
Length	len(s)	O(1)	set 크기
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)	list, tuple은 O(n)인데..!
Remove	s.remove(...)	O(1)	list, tuple은 O(n)인데..!
Pop	s.pop()	O(1)	set.pop은 랜덤 뽑기
Clear	s.clear()	O(1)	s = set() 이랑 똑같음
Construction	set(...)	O(len(...))	(...) iterable 길이에 의존
Check ==, !=	s != t	O(len(s))	len(t)랑 같은데, 길이가 다르면 O(1)이 아님
<=, <	s <= t	O(len(s))	부분집합
>=, >	s >= t	O(len(t))	s <= t == t >= s
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))
Iteration	for v in s:	O(n)	이거도 무한루프면..
Copy	s.copy()	O(n)

 

Dictionary

dictionary의 대부분 Operation은 시간복잡도가 O(1)이기 때문에 알고리즘 문제를 풀때 활용하기 좋다

Operation	Example	Complexity	Notes
Index	d[k]	O(1)
Store	d[k] = v	O(1)
Length	len(d)	O(1)
Delete	del d[k]	O(1)
get/set default	d.get(k)	O(1)
Pop	d.pop(k)	O(1)
Pop item	d.popitem()	O(1)	랜덤 뽑기
Clear	d.clear()	O(1)	d = {} ot d = dict() 랑 같음
View	d.keys()	O(1)	d.values()도 같은 시간복잡도를 가짐
Construction	dict(...)	O(len(...))	(key, value) 에 의존
Iteration	for k in d:	O(n)	key, value, items 형태. worst는 무한루프

 

---

Reference

https://wiki.python.org/moin/TimeComplexity

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