[Python] 기본 연산자들의 시간복잡도(Big-O) 정리

알고리즘 문제를 풀다보면 작성한 알고리즘의 시간복잡도(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	리스트의 길이 가져옴	len(l)	O(1)
append	리스트의 뒤쪽에 element 추가	l.append(1)	O(1)
pop	리스트의 뒤쪽 element 제거	l.pop()	O(1)	l.pop(-1)과 동일한 동작
clear	리스트를 비움	l.clear()	O(1)	l = list(), l = [] 과 동일
slice	리스트의 일부를 취함	l[a:b]	O(b-a)	복사되는 element의 개수에 비례
extend	리스트뒤에 리스트를 붙임	l.extend(other_list)	O(len(other_list)	추가되는 list의 size에 비례
construction	리스트 객체 생성	list()	O(len(...))	초기화 되는 리스트 Element 개수에 비례
equals	두 리스트가 같은지 확인	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	리스트를 복사	l.copy()	O(N)	l[:]와 동일한 결과
remove	리스트에서 엘리먼트를 제거	l.remove(10)	O(N)	10이라는 값을 제거
pop	리스트의 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)의 개수에 비례
equals	동일한 집합인지 연산	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 타입의 기본 메소드와 시간 복잡도에 대해서 정리해보겠다. dict 타입은 자바에서의 Map과 비슷하다. 소문자 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

---

파이썬 스크립트 작성에 도움되는 글 모음