파이썬 기본 연산자들의 시간 복잡도(Big-O) 정리

파이썬을 이용해서 알고리즘 문제를 풀다보면 언어 자체에서 지원하는 내장 메소드들을 사용하는 경우가 대부분이다. 이 때, 각 메소드들의 시간 복잡도를 정확하게 알고 사용해야 제대로된 알고리즘을 작성할 수 있다. 따라서 파이썬의 기본 타입들이 제공하는 메소드들과 그것들의 시간 복잡도를 정리하는 시간이 필요하다고 생각했다.

우선 변수 할당(바인딩, Binding)의 시간 복잡도는 O(1)이다. 즉, 'a = 1'이라는 할당문은 O(1)라는 시간복잡도를 갖는다. 여기에 산술연산, 값에 대한 비교 연산들 역시 모두 O(1)의 시간복잡도를 갖는다.

list 타입의 메소드와 Big-O

리스트 타입의 내장 메소드들의 리스트와 그것들의 시간 복잡도에 대해서 알아보겠다. 소문자 L은 리스트 객체를 나타냈고 대문자 N은 리스트의 사이즈를 의미한다.

연산	설명	예제	복잡도	비고
Index	n번째 element 접근	l[i]	O(1)
Store	n번째에 element 할당	l[i] = 10	O(1)
Length	List의 길이 가져옴	len(l)	O(1)
Append	List의 뒤쪽에 element 추가	l.append(1)	O(1)
Pop	List의 뒤쪽 element 제거	l.pop()	O(1)	l.pop(-1)과 동일한 동작
Clear	List를 비움	l.clear()	O(1)	l = list(), l = [] 과 동일
Slice	List의 일부를 취함	l[a:b]	O(b-a)	복사되는 element의 개수에 비례
Extend	리스트뒤에 리스트를 붙임	l.extend(other_list)	O(len(other_list)	추가되는 list의 size에 비례
Construction	list 객체 생성	list()	O(len(...))	초기화 되는 리스트 Element 개수에 비례
Equality Check	두 리스트가 같은지 확인	l1 == l2	O(N)	N : list의 size
Insert	특정 위치에 element를 끼워 넣음	l.insert(2, 10)	O(N)	중간에 끼워 넣어야 해서 한칸씩 뒤로 밀려나서 그러는듯?
Delete	특정 위치의 element를 제거함	del l[10]	O(N)	마찬가지로 중간에 제거되고 그 뒤에 있는 Element를 땡겨줘야해서 그러는듯?
Containment	특정 Element가 list 내에 있는지 확인	x in l, x not in l	O(N)	Searching Overhead
Copy	list를 복사	l.copy()	O(N)	l[:]와 동일한 결과
Remove	list에서 Element를 제거	l.remove(10)	O(N)	10이라는 값을 제거
Pop	List의 i번째 element를 제거	l.pop(1)	O(N)	O(N - i).
Extreme  Value	min/max 값 찾기	min(l), max(l)	O(N)	전체를 한번씩 탐색 필요
Reverse	리스트를 역순으로 변경	l.reverse()	O(N)
Iteration	리스트의 element들을 한번씩 순회	for item in l :	O(N)
Sort	정렬 수행	l.sort()	O(N * log N)
Multiply	리스트의 element들을 k번 반복해서 리스트를 생성	k * l	O(k * l)	3 * [0] -> [0,0,0]

각 연산들이 파이썬 내부에서 어떻게 동작하는지 잘 생각해보면, 각 시간 복잡도를 쉽게 유추할 수 있다.

Set 타입의 메소드와 Big-O

집합(set) 타입의 메소드들과 그들의 시간 복잡도를 정리해보자. 리스트와 비슷하게 소문자 S와 소문자 T는 집합을 나타내고, N은 집합에 있는 엘리먼트의 개수를 의미한다.

연산	설명	예제	복잡도	비고
Length	집합 element들의 개수	len(s)	O(1)
Add	집합에 element 추가	s.add(10)	O(1)
Containment	집합에 특정 Element가 있는지 확인	10 in s, 10 not in s	O(1)	List/Tuple은 O(N)임과 비교
Remove	집합에서 특정 Element를 제거	s.remove(10)	O(1)	List/tuple의 경우 O(N)
Discard	집합에서 특정  Element를 제거	s.discard(10)	O(1)
Pop	집합에서 임의의 element하나를 제거	s.pop()	O(1)
Clear	집합을 공집합(empty)으로 만들어버림	s.clear()	O(1)	s = set() 과 동일
Construction	집합을 생성	set(...)	O(len(...))	새로 생성되는 집합 요소(Element)의 개수에 비례
Equality Check	동일한 집합인지 연산	s == t, s != t	O(len(s))	모든 element가 동일하면 동일한 집합
Subset Check	Subset인지 여부를 확인	s <= t, s >= t	O(len(s)) O(len(t))	Subset 쪽의 모든 element가 superset에 존재하는지 확인
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	집합의 모든 element들을 순회	for v in s:	O(N)
Copy	집합을 복사	s.copy()	O(N)

집합 연산은 리스트에 비해 순서를 보장하지 않아도 되기 때문에 O(1)에 끝나는 연산들이 더 있다. 따라서 순서를 보장하지 않아도 되는 경우 리스트 대신 집합 타입을 사용해서 시간 복잡도를 줄일 수 있다.

dict 타입의 메소드와 Big-O

마지막으로 dict 타입의 메소드들과 그것들의 시간 복잡도를 정리해보겠다. 소문자 D는 dict 타입을 의미하며, 소문자 K는 키 값을 의미한다.

연산	설명	예제	복잡도	비고
Index	특정 Element에 접근	d[k]	O(1)
Store	특정 Element에값을 설정	d[k] = v	O(1)
Length	Dict에 들어있는 Element 개수	len(d)	O(1)
Delete	특정 Element를 지움	del d[k]	O(1)
Pop	특정 Element를 지움	d.pop(k)	O(1)
Pop item	무작위로 Element 하나를 지움	d.popitem()	O(1)
Clear	Dict를 초기화	d.clear()	O(1)	d = {}와 동일함
View	Dict의 Key들을 List형태로 가져옴	d.keys()	O(1)	d.values()도 동일
Construction	Dictionary를 생성	dict(...)	O(len(...))	새로 생성되는 Dict의 element 개수에 비례
Iteration	Dict 내의 element들을 순회	for k in d:	O(N)

각 타입마다 메소드들의 시간 복잡도가 약간씩 다르다. 각 타입별로 메소드들의 시간복잡도를 이해하고 적절한 자료구조를 사용하여 불필요하게 낭비되는 시간 복잡도를 줄여 더 효율적인 알고리즘을 작성할 수 있도록 하자.

Reference

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