기본 연산자의 시간복잡도 (Big-O)

Lists

연산	예시	복잡도	비고
Index	l[i]	$O(1)$
Store	l[i]=0	$O(1)$
Length	len(l)	$O(1)$
Append	l.append(5)	$O(1)$
Pop	l.pop()	$O(1)$	l.pop(-1)과 동일
Clear	l.clear()	$O(1)$	l = []와 유사
Slice	l[a:b]	$O(b-a)$	슬라이싱하는 요소의 개수에 비례
Extend	l.extend(...)	$O(len(...))$	추가할 리스트의 크기에 비례
Construction	list(...)	$O(len(...))$	변환할 Iteratble의 길이에 비례
check ==, !=	l1 == l2	$O(N)$
Insert	l[a:b] = ...	$O(N)$
Delete	del l[i]	$O(N)$	지우려는 요소의 위치에 따름 최악의 경우 $O(N)$
Containment	x in/not in l	$O(N)$	리스트 탐색
Copy	l.copy()	$O(N)$	l[:]과 동일
Remove	l.remove(...)	$O(N)$
Pop	l.pop(i)	$O(N)$	l.pop(0) 복잡도: $O(N)$
Extreme value	min(l) / max(l)	$O(N)$	리스트 탐색
Reverse	l.reverse()	$O(N)$
Iteration	for v in l:	$O(N)$
Sort	l.sort()	$O(N \log N)$
Multiply	k*l	$O(k N)$	len(l) * l 복잡도: $O(N^2)$

Sets

연산	예시	복잡	비고
Length	len(s)	$O(1)$
Add	s.add(5)	$O(1)$
Containment	x in/not in s	$O(1)$	리스트/튜플은 $O(N)$
Remove	s.remove(..)	$O(1)$	리스트/튜플은 $O(N)$
Discard	s.discard(..)	$O(1)$
Pop	s.pop()	$O(1)$
Clear	s.clear()	$O(1)$	s = set()과 동일
Construction	set(...)	$O(len(...))$	변환할 Iteratble의 길이에 비례
check ==, !=	s != t	$O(len(s))$	모든 요소가 동일해야 함 길이가 다른 경우 $O(1)$
<=, <	s <= t	$O(len(s))$	s가 t의 부분집합인지 체크
>=, >	s >= t	$O(len(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)$

Dictionaries

연	예	복잡	비고
Index	d[k]	$O(1)$
Store	d[k] = v	$O(1)$
Length	len(d)	$O(1)$
Delete	del d[k]	$O(1)$
get/setdefault	d.get(k)	$O(1)$
Pop	d.pop(k)	$O(1)$
Pop Item	d.popitem()	$O(1)$	무작위로 요소를 pop
Clear	d.clear()	$O(1)$	s = {} 또는 s = dict()와 유사
View	d.keys()	$O(1)$	d.values()와 동일
Construction	dict(...)	$O(len(...))$
Interation	for k in d:	$O(N)$

References

• Complexity of Python Operations - ICS-33: Intermediate Programming