파이썬(Python) 자료형(List, Set, Dictionary) 연산자 시간복잡도 (Big-O) 정리

 

저는 최근 코딩테스트를 준비하면서 자료구조 및 알고리즘을 다시 공부하고 있습니다.

문제를 풀다보면 종종 시간복잡도를 고려하지 않으면 오답처리 되는 경우가 있습니다.

 

저는 주로 파이썬(Python) 혹은 C++을 이용하는데, 오늘은 파이썬 주요 연산자의 시간 복잡도를 알아보겠습니다.

 

Lists

Operation	Example	Big-O	Notes
Index	l[i]	O(1)
Store	I[i] = 0	O(1)
Length	len(l)	O(1)
Append	l.append(2)	O(1)
Pop	l.pop()	O(1)	same as l.pop(-1)
Clear	l.clear()	O(1)	similar to l = []
Slice	l[a:b]	O(b-a)	l[1:5] : O(1) l[:] : O(len(l)-0)=O(N)
Extend	l.extend(...)	O(len(...))	depends only on len of extension
Construction	list(...)	O(len(...))	depends on length of ... iterable
check ==, !=	l1 == l2	O(N)
Insert	l.insert(i, v)	O(N)
Delete	del l[i]	O(N)	depends on i O(N) in worst case
Containment	x in/not in l	O(N)	linearly searches list
Copy	l.copy()	O(N)	Same as l[:] which is O(N)
Remove	l.remove(...)	O(N)
Pop	l.pop(i)	O(N)	O(N-i)
Extreme value	min(l)/max(l)	O(N)	linearly searches list for value
Reverse	l.reverse()	O(N)
Iteration	for v in l	O(N)	Worst : no return/break in loop
Sort	l.sort()	O(NlogN)	key/reverse mostly doesn't change
Multiply	k*l	O(kN)	5*l is O(N): len(l)*l is O(N**2)

 

Sets

Operation	Example	Big-O	Notes
Length	len(s)	O(1)
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)	compare to list/tuple - O(N)
Remove	s.remove(..)	O(1)	compare to list/tuple - O(N)
Discard	s.discard(..)	O(1)
Pop	s.pop()	O(1)	popped value "randomly" selected
Clear	s.clear()	O(1)	similar to s = set()
Construction	set(...)	O(len(...))	depends on length of ... iterable
check ==, !=	s != t	O(len(s))	same as len(t); False in O(1) if the lengths are different
<= / <	s <= t	O(len(s))	issubset
>= / >	s >= t	O(len(t))	issuperset 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)	Worst: no return/break in loop
Copy	s.copy()	O(N)

 

Dictionaries: dict and defaultdict

Operation	Example	Complexity Class	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)	popped item "randomly" selected
Clear	d.clear()	O(1)	similar to s = {} or = dict()
View	d.keys()	O(1)	same for d.values()
Construction	dict(...)	O(len(...))	depends # (key, value) 2-tuples
Iteration	for k in d:	O(N)	all forms: keys, values, items Worst: no return/break in loop