[ 파이썬 ] 파이썬 자료형 별 시간 복잡도 ( BIG - O )

 

---

 

* 알고리즘 풀이에 있어 시간 복잡도를 고려해야하는 부분이 많다 *

 

* 알고리즘 풀이에 도움이 될 만한 파이썬 주요 함수, 자료형 별 시간 복잡도에 대해

간단히 정리해보고자 한다 * 

 

List 

연산	예시	Big - O	기타
Index	list[i]	O(1)	인덱스로 값 찾기
Store	list[i] = 1	O(1)	인덱스로 데이터 저장
Length	len(list)	O(1)	리스트 길이
Append	list.append(3)	O(1)	리스트 뒤에 데이터 저장
Pop	list.pop()	O(1)	list.pop(-1) 과 동일
Slice	list[ a: b ]	O( b-a )	list[:] -> O(N)
Clear	list.clear()	O(1)	list = [ ]
Extend	list.extend(..)	O(len(...))	확장 길이에 따라
Construction	list(...)	O(len(...))	요소 길이에 따라
check ==, !=	list 1 == list 2	O(N)	비교
Insert	list.insert(i, v)	O(N)	i 위치에 v를 추가
Delete	del list[i]	O(N)	데이터 삭제
Remove	list.remove(..)	O(N)	제거
Containment	x in/ not in list	O(N)	검색
Copy	list.copy()	O(N)	복제
Pop	list.pop(i)	O(N)	제거된 값 이후 전부 한칸씩 앞으로 당겨야 함.
Extreme Value	min(list) / max(list)	O(N)	전체 데이터 확인
Reverse	list.reverse()	O(N)	뒤집기
Iteration	for i in list :	O(N)	전체 데이터 확인
Sort	list.sort()	O(NlogN)	파이썬 기본 정렬 알고리즘 ( Tim Sort = 병합 + 삽입)
Multiply	k * list	O(k N)	리스트의 곱은 리스트 개수가 늘어남
Count	list.count(x)	O(N)	x가 몇개 있었는지 count

 

 

딕셔너리 

연산	예시	Big - O	기타
Store	dict[k] = v	O(1)	데이터 저장
Length	len( dict )	O(1)	길이 출력
Delete	del dict[k]	O(1)	요소 제거
get/set default	dict.get(k)	O(1)	key에 따른 value 확인
Pop	dict.pop(k)	O(1)	pop
Pop item	dict.popitem()	O(1)	랜덤하게 선택해서 pop
Clear	dict.clear()	O(1)	s = {} 또는 = dict ()와 비슷
View	dict.keys()	O(1)	dict.values() 도 동일
Construction	dict(...)	O(len(..)	(key,value) 튜플 개수 만큼
Iteration	for k in dict :	O(N)	전체 딕셔너리 순회

 

Set

연산	예시	Big - O	기타
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)	랜덤하게 하나 pop
Clear	s.clear()	O(1)	s=set()과 비슷
Construction	set(...)	O(len(..))	길이만큼
check, == , !=	s!=t	O(len(s))	전체 요소 동일 여부 확인
<=/<	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))	여집합
Iteration	for v in s :	O(N)	전체 요소 순회
Copy	s.copy()	O(N)	복제

 

---

 

* List 자료형은 삽입, 제거, 탐색, 포함 여부 확인에 모두 O(N)의 시간복잡도를 가짐*

 

* Set 과 Dictionary는 삽입, 제거, 탐색, 포함여부 확인 연산에 O(1)의 시간 복잡도를 가짐 *

 

* 탐색과 확인이 주 연산 이라면 Set이나 Dictionary를 사용하는 것이 좋고

 

순서와 Index에 따른 접근이 필요하다면 List 자료형 사용이 유용 *