[Python]파이썬 자료형별 시간복잡도 정리

Lists/Tuples(데이터가 수정되지 않는 동작 한정)

 

리스트는 메모리 주소값을 이용해 임의접근(random access)이 가능하므로  탐색의 시간복잡도가 매우 낮다.

반면 삽입/삭제는 그 인덱스 뒷 요소는 모두 한칸씩 밀려나거나 당겨지기 때문에 뒷 요소만큼 연산이 필요하다.

 

탐색: O(1)

삽입/삭제: O(N)

Operation	Example	Big-O
Index	l[i]	O(1)
Store	l[i]=0	O(1)
Length	len(l)	O(1)
Append	l.append(5)	O(1)
Delete	l.pop()	O(1)
Clear	l.clear()	O(1)
Slice	l[a:b]	O(b-a)
Extend	l.extend(...)	O(len(...))
Construction	list(...)	O(len(...))
Check	==, !==	O(N)
Insert	l[a:b] = ...	O(N)
Delete	del l[i]	O(N)
Containment	x in/not in l	O(N)
Copy	l.copy()	O(N)
Remove	l.remove(...)	O(N)
Pop	l.pop(i)	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)

 

Dicts

파이썬의 Dictionary구조는 hash함수를 활용하기 때문에 삽입/삭제가 매우 빠르다.

 

탐색/삽입/삭제: O(1)

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)
Clear	d.clear()	O(1)
View	d.kets()	O(1)
Construction	dict(...)	O(len(...))
Iteration	for k in d:	O(N)

 

 

Sets

삽입/삭제: O(1)

Length	len(s)	O(1)
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)
Remove	s.remove(...)	O(1)
Discard	s.discard(...)	O(1)
Pop	s.pop()	O(1)
Clear	s.clear()	O(1)
Construction	set(...)	O(len(...))
check	==, !==	O(len(s))
<=/<	s <= t	O(len(s))
>=/>	s >= t	O(len(t))
Union	s | t	O(len(s))+O(len(t))
intersection	s & t	O(len(s))+O(len(t))
Difference	s - t	O(len(s))+O(len(t))
Symmetric Diff	s ^ t	O(len(s))+O(len(t))
Iteration	f v in s:	O(N)
Copy	s.copy()	O(N)

 

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