[DataStructure] Python 자료구조별 시간 복잡도 정리

Python 자료구조별 시간 복잡도 정리

리스트 자료형과 메서드의 시간 복잡도

	Operation	Example	Class	Notes
1	Index	l[i]	O(1)	인덱스로 값 찾기
2	Store	l[i] = 0	O(1)	인덱스로 데이터 저장
3	Length	len(l)	O(1)	리스트 길이
4	Append	l.append(5)	O(1)	리스드 뒤에 데이터 저장
5	Pop	l.pop()	O(1)	가장 뒤의 데이터 pop
6	Clear	l.clear()	O(1)	l = []
7	Slice	l[a:b]	O(b-a)	슬라이싱되는 요소들 수 만큼 비례
8	Extend	l.extend(...)	O(len(...))	확장되는 길이만큼
9	Construction	list(...)	O(len(...))	리스트 길이만큼
10	check ==, !=	l1 == l2	O(N)	전체 리스트가 동일한지 확인
11	Insert	l[a:b] = ...	O(N)	데이터 삽입
12	Delete	del l[i]	O(N)	데이터 삭제
13	Containment	x in/not in l	O(N)	포함 여부 확인
14	Copy	l.copy()	O(N)	복제
15	Remove	l.remove(...)	O(N)	제거
16	Pop	l.pop(i)	O(N)	제거된 값 이후를 전부 한칸씩 당겨줘야함
17	Extreme value	min(l)/max(l)	O(N)	전체 데이터를 확인해야함
18	Reverse	l.reverse()	O(N)	뒤집기
19	Iteration	for v in l:	O(N)	전체 데이터 확인하므로
20	Sort	l.sort()	O(N Log N)	파이썬 기본 정렬 알고리즘
21	Multiply	k*l	O(k N)	리스트의 곱은 리스트 개수 늘어남

---

집합(set) 자료형과 메소드의 시간 복잡도

	Operation	Example	Class	Notes
1	Add	s.add(5)	O(1)	집합 요소 추가
2	Containment	x in/not in s	O(1)	포함 여부 확인
3	Remove	s.remove(..)	O(1)	요소 제거
4	Discard	s.discard(..)	O(1)	특정 요소 제거
5	Pop	s.pop()	O(1)	랜덤하게 하나 pop
6	Clear	s.clear()	O(1)	similar to s = set()
7	Construction	set(...)	O(len(...))	길이만큼
8	check ==, !=	s != t	O(len(s))	전체 요소 동일 여부 확인
9	<=/<	s <= t	O(len(s))	부분집합 여부
10	>=/>	s >= t	O(len(t))	부분집합 여부
11	Union	s, t	O(len(s)+len(t))	합집합
12	Intersection	s & t	O(len(s)+len(t))	교집합
13	Difference	s - t	O(len(s)+len(t))	차집합
14	Symmetric Diff	s ^ t	O(len(s)+len(t))	여집합
15	Iteration	for v in s:	O(N)	전체 요소 순회
16	Copy	s.copy()	O(N)	복제

---

딕셔너리(Dictionary) 자료형과 메소드의 시간 복잡도

	Operation	Example	Class	Notes
1	Store	d[k] = v	O(1)	데이터 저장
2	Length	len(d)	O(1)	길이 출력
3	Delete	del d[k]	O(1)	요소 제거
4	get/setdefault	d.get(k)	O(1)	key에 따른 value 확인
5	Pop	d.pop(k)	O(1)	pop
6	Pop item	d.popitem()	O(1)	랜덤하게 선택해서 pop
7	Clear	d.clear()	O(1)	similar to s = {} or = dict()
8	View	d.keys()	O(1)	same for d.values() / 키값 전체 확인
9	Construction	dict(...)	O(len(...))	(key, value) 튜플 개수만큼
10	Iteration	for k in d:	O(N)	전체 딕셔너리 순회