컬렉션 객체의 내장 함수 시간 복잡도 모음

요즘 Python이 배우기도 쉽고, 알고리즘 코드를 작성할 때 짧고 생각한 그대로 표현하기에 좋은 언어이기 때문에 코딩테스트에서의 선호도가 점차 증가하고 있는 추세이다. 하지만 코드를 작성할 때, 파이썬 객체의 내장 함수를 사용하면서 해당 함수의 시간 복잡도가 얼마나 걸리는지에 대해서는 잘 알지 못하고 사용하고 있는 부분이 있어 해당 내용을 정리하고자 한다.  

 

아래에 나오는 표는 각 객체에 대하여 내장 함수의 시간 복잡도를 정리한 표이다.

해당 표는 (목적 / 예제 / 시간복잡도 / 기타 사항) 순으로 정리하였다.

 

 

 

 

파이썬 자료형의 내장 함수 시간 복잡도 정리

 

List

l = list() 로 고려한 다음의 Example이다.

Operation	Example	Big-O	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)	l.pop(-1) 과 동일
Clear	l.clear()	O(1)	l = [] 과 유사
Slice	l[a:b]	O(b-a)	l[:] : O(len(l)-0) = O(N)
Extend	l.extend(…)	O(len(…))	확장 길이에 따라
Construction	list(…)	O(len(…))	요소 길이에 따라
check ==, !=	l1 == l2	O(N)	비교
Insert	l.insert(i, v)	O(N)	i 위치에 v를 추가
Delete	del l[i]	O(N)
Remove	l.remove(…)	O(N)
Containment	x in/not in l	O(N)	검색
Copy	l.copy()	O(N)	l[:] 과 동일 - 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)	[1,2,3] * 3 » O(N**2)

 

 

 

Dict

d = dict() 로 고려한 다음의 Example이다.

Operation	Example	Big-O	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)

 

 

 

 

Set

s = set()로 고려한 다음의 Example이다.

Operation	Example	Notes	Big-O
Length	len(s)	O(1)	집합 element들의 개수
Add	s.add(10)	O(1)	집합에 element 추가
Containment	10 in s, 10 not in s	O(1)	집합에 특정 Element가 있는지 확인
Remove	s.remove(10)	O(1)	집합에서 특정 Element를 제거
Discard	s.discard(10)	O(1)	집합에서 특정 Element를 제거
Pop	s.pop()	O(1)	집합에서 임의의 element하나를 제거
Clear	s.clear()	O(1)	집합을 공집합(empty)으로 만들어버림
Construction	set(...)	O(len(...))	집합을 생성
Equality Check	s == t, s != t	O(len(s))	동일한 집합인지 연산
Subset Check	s <= t, s >= t	O(len(s)) O(len(t))	Subset인지 여부를 확인
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)	집합의 모든 element들을 순회
Copy	s.copy()	O(N)	집합을 복사