코딩테스트 주요 연산자/메소드 시간 복잡도 정리 - 파이썬(Python)

시간 복잡도 in 코딩테스트

	N이 1000일 때의 연산 횟수
O(N)	1000
O(NlogN)	10000
O(N^2)	1000000
O(N^3)	1000000000

 

시간 제한이 1초인 문제일 때

• N의 범위가 500인 경우: 시간복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2000인 경우: 시간복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100000(10만)인 경우: 시간복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10000000(1000만)인 경우: 시간복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

리스트(List)

	Operation	Example	Big-O	Notes
1	Index	l[i]	O(1)	인덱스로 값 찾기
2	Store	l[i] = val	O(1)	인덱스로 데이터 저장
3	Length	len(l)	O(1)	리스트 길이
4	Append	l.append(val)	O(1)	리스트 뒤에 데이터 추가
5	Pop	l.pop()	O(1)	리스트 마지막 데이터 pop
6	Clear	l.clear()	O(1)	빈 리스트로 만듦
7	Slice	l[a:b]	O(b-a)	슬라이싱
8	Extend	l.extend(l2)	O(len(l2))	리스트 확장
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)	x값 포함 여부 확인
14	Copy	l.copy()	O(N)	리스트 복제
15	Remove	l.remove(val)	O(N)	리스트에서 val값 제거
16	Pop 2	l.pop(i)	O(N)	i번째 인덱스 값 pop
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	Big-O	Notes
1	Add	s.add(val)	O(1)	집합 요소 추가
2	Containment	x in/not in s	O(1)	포함 여부 확인
3	Remove	s.remove(val)	O(1)	요소 제거(없으면 에러)
4	Discard	s.discard(val)	O(1)	요소 제거(없어도 에러x)
5	Pop	s.pop()	O(1)	랜덤하게 하나 pop
6	Clear	s.clear()	O(1)	빈 집합으로 만듦
7	Construction	set(…)	O(len(…))	길이만큼
8	check ==, !=	s != t	O(len(s))	전체 요소 동일 여부 확인
9	<= or <	s <= t	O(len(s))	부분집합 여부
10	Union	s, t	O(len(s)+len(t))	합집합
11	Intersection	s & t	O(len(s)+len(t))	교집합
12	Difference	s - t	O(len(s)+len(t))	차집합
13	Symmetric Diff	s ^ t	O(len(s)+len(t))	여집합
14	Iteration	for v in s:	O(N)	전체 요소 순회
15	Copy	s.copy()	O(N)	복제

 

딕셔너리(Dictionary)

	Operation	Example	Big-O	Notes
1	Store	d[k] = v	O(1)	집합 요소 추가
2	Length	len(d)	O(1)	딕셔너리 길이
3	Delete	del d[k]	O(1)	해당 key 제거
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)	랜덤 데이터(key:value) pop
7	Clear	d.clear()	O(1)	빈 딕셔너리로 만듦
8	View	d.keys()	O(1)	key 전체 확인
9	Values	d.values()	O(1)	value 전체 확인
10	Construction	dict(…)	O(len(…))	(key, value) tuple 갯수만큼
11	Iteration	for k in d:	O(N)	딕셔너리 전체 순회

 

덱크(collections.deque)

	Operation	Example	Big-O	Notes
1	Copy	dq.copy()	O(N)	복제
2	Append	dq.append(val)	O(1)	요소 추가 (큐의 오른쪽)
3	Append Left	dq.appendleft(val)	O(1)	요소 추가 (큐의 왼쪽)
4	Pop	dq.pop()	O(1)	마지막 데이터 pop
5	Pop Left	dq.popleft()	O(1)	첫번째 데이터 pop
6	Extend	dq.extend(dq2)	O(k)	dq + dq2 확장
7	Extend Left	dq.extendleft(dq2)	O(len(dq2))	dq2 + dq 확장
8	Rotate	dq.rotate(k)	O(k)	양수k: 오른쪽으로 n만큼 회전, 음수k: 왼쪽으로 n만큼 회전
9	Remove	dq.remove(val)	O(N)	요소 제거

 

우선순위큐(heapq)

	Operation	Example	Big-O	Notes
1	Heappush	heappush(h, 1)	O(logN)	힙에 원소 추가
2	Heappop	heappop(h)	O(logN)	가장 작은 원소 pop
3	Heapify	heapify(h)	O(N)	리스트를 힙으로 변환

 

이진탐색(bisect)

	Operation	Example	Big-O	Notes
1	Bisect Left	bisect_left(data, x)	O(logN)	data에 x가 들어갈 수 있는 가장 작은 인덱스
2	Bisect Right	bisect_right(data, x)	O(logN)	data에 x가 들어갈 수 있는 가장 큰 인덱스