[Python] List / Set / Dictionary Method 의 시간 복잡도

[Python] List / Set / Dictionary 의 시간 복잡도

[Python] List / Set / Dictionary 의 시간 복잡도

 

Python 의 자료형인 List / Set / Dictionary 에서 제공하는 method 의 시간 복잡도를 정리해 보았다.

 

 

List

Operation	Example	Big-O	Note
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() == l.pop(-1) i.pop(i) l.pop(0)	O(1) O(N) O(N)
Clear	l.clear()	O(1)	l = [] 과 유사
Slice	l[a:b] l[:]	O(b-a) O(N)
Extend	l.extend(…)	O(len(…))
Construction	list(…)	O(len(…))
check ==, !=	l1 == l2	O(N)	비교
Insert	l.insert(i, v)	O(N)
Delete	del l[i]	O(i), worst O(N)
Containment	x in/not in l	O(N)	검색과 유사
Copy	l.copy()	O(N)	l[:] 과 유사 : O(N)
Remove	l.remove()	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)	[1,2,3] * 3 » O(N**2)

 

 

Set

Operation	Example	Big-O	Note
Length	len(s)	O(1)
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)	List 는 O(N)
Remove	s.remove(..)	O(1)	List 는 O(N)
Disard	s.discard(..)	O(1)
Pop	s.pop()	O(1)
Clear	s.clear()	O(1)	s = set() 과 유사
Construction	set(...)	O(len(…))
check ==, !=	s != t	O(len(s))	len(s) != len(t) : O(1), false case
<= / <	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))
Interation	for v in s:	O(N)
Copy	s.copy()	O(N)

 

 

Dictionary

Operation	Example	Big-O	Note
Index	d[k]	O(1)
Store	d[k] = v	O(1)
Length	len(d)	O(1)
Delete	del d[k]	O(1)
get/setdefualt	d.get(k)	O(1)
Pop	d.pop(k)	O(1)
Pop item	d.popitem()	O(1)
Clear	d.clear()	O(1)	d = dict() 와 유사
View	d.keys() d.values()	O(1) O(1)
Construction	dict(...)	O(len(…))
Iteration	for k in d:	O(N)

 

 

 

---

참고 자료

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