Python 주요 자료형 시간 복잡도

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

코딩 테스트 효율성 통과하기 너무 어렵다

 

List

Operation	Example	Complexity Class	Notes
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)	same as l.pop(-1)
Clear	l.clear()	O(1)	similar to l = []
Slice	l[a:b]	O(b-a)	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	ㅣ.insert(i, v)	O(N)
Delete	del l[i]	O(N)
Remove	l.remove(…)	O(N)
Containment	x in/not in l	O(N)	searches list
Copy	l.copy()	O(N)	same as l[:], O(N)
Pop	l.pop(i)	O(N)	l.pop(0):O(N)
Extreme value	min(l)/max(l)	O(N)	searches list for value
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)

 

Set

Operation	Example	Complexity Class	Notes
Length	len(s)	O(1)
Add	s.add(n)	O(1)
Containment	x in/not in s	O(1)	compare to list/tuple - O(N)
Remove	s.remove(n)	O(1)	compare to list/tuple - O(N)
Discard	s.discard(n)	O(1)
Pop	s.pop(k)	O(1)
Clear	s.clear()	O(1)	similar to s=set()
Construction	set(A)	O(len(A))	depends on length of A iterable
check ==, !=	s != t	O(len(s))	same as len(t)
<=, <, >=, >	s <= t	O(len(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 i in s:	O(n)
Copy	s.copy()	O(n)

 

Dictionary

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/setdefault	d.method	O(1)
Pop	d.pop(k)	O(1)
Pop item	d.popitem()	O(1)
Clear	d.clear()	O(1)	s = {} or = dict() 유사
View	d.keys()	O(1)	d.values() 동일
Construction	dict(…)	O(len(…))
Iteration	for k in d:	O(N)

 

 

 

 

 

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