Python 내장 함수의 시간 복잡도

Python 컨테이너 메소드의 시간 복잡도(time complexity)는 어떻게 될까?

 알고리즘을 풀면서 컨테이너를 조작하기 위해 기본 메소드들을 많이 활용하게 되었고, 메소드의 시간 복잡도가 궁금해졌다.

경우에 따라서 어떤 메소드를 사용하느냐가 알고리즘의 시간 복잡도를 크게 좌지우지 할때가 있다. 

물론 문제를 푸느냐 못푸느냐는 대부분 내 알고리즘이 문제이고, 메소드가 문제를 해결하는데 큰 영향을 미치는 경우는 드물다.

그럼에도 궁금한 부분은 바로바로 정리해두는게 좋을 것 같아,

이 포스팅에서는 python의 컨테이너별로 메소드의 시간 복잡도를 정리하려고 한다.

시간 복잡도는 아래의 표와 같이 표기하고 읽는다. 

아래로 내려갈 수록 시간이 오래 걸림을 뜻한다.

시간 복잡도에 관한 자료는 Python 위키 문서에서 가져와 번역하고 정리하였다.

자주 사용하는 시간 복잡도 표기
	상수 시간 (Constant Time)
	로그 시간 (대수 시간, Logarithmic time)
	선형 시간 (Linear time)
	로그 선형 시간 (Log-linear time)
	제곱 시간 (Quadratic time)
	세제곱 시간 (Cubic time)
	지수 시간 (Exponential time)

---

컨테이너 메소드별 시간 복잡도

CPython에서 컨테이너별로 다양한 연산 메소드들이 있으며 메소드 별로 어떤 시간 복잡도를 가지는지 정리해보겠다. 

파이썬의 버전에 따라서 시간 복잡도는 약간 다를 수 있지만 일반적으로  이상으로 느려지지 않는다.

'n'은 컨테이너 안에 들어있는 원소의 수를 의미하며, 'k'는 매개변수 값이거나 매개 변수의 원소 수를 의미한다.

List

리스트는 배열로 표현된다. 그렇기 때문에 배열의 크기가 증가하거나 index 값이 작은 부분에 삽입 또는 삭제가 일어날 경우 비효율적이다.  이럴 경우에는 아래의 collections.deque를 사용하는게 보다 효율적이다.

Operation	Average Case	Amortized Worst Case
Copy
Append[1]
Pop last
Pop intermediate
Insert
Get Item
Set Item
Delete Item
Iteration
Get Slice
Del Slice
Set Slice
Extend[1]
Sort
Multiply
x in s
min(s), max(s)
Get Length

collections.deque

deque(double-ended queue)는 내부적으로 doubly 링크드 리스트로 표현된다. 양 끝단에 모두 접근이 가능하다. 단, deque의 가운데 부분을 찾거나, 중간에 삽입, 제거하는 것은 더 느리다. 

Operation	Average Case	Amortized Worst Case
copy
append
appendleft
pop
popleft
extend
extendLeft
rotate
remove

Set

Set과 dict은 내부적으로 매우 유사하다.

Operation	Average Case	Amortized Worst Case
x in s
Union s|t
Intersection s&t
Multiple intersection s1&s2&...&sn		* where l is max(len(s1),...,len(sn))
Difference s-t
s.difference_update(t)
symmetric Difference s^t
s.symmetric_difference_update(t)

dict

여기서 말하는 평균 시간은 객체에 대한 해시 함수가 충돌을 자주 발생시키지 않을 만큼 견고하다는 가정하에 진행되었다.

평균 사례는 매개 변수에 사용된 키가 모든 키 집합에서 무작위로 균등하게 선택된다고 가정한다.

Operation	Average Case	Amortized Worst Case
copy[2]
Get Item
Set Item[1]
Delete Item
Iteration[2]

#Python 내장 함수 #파이썬 내장 함수 #python 시간 복잡도 #파이썬 시간 복잡도 #내장 메소드 시간 복잡도 #파이썬 내장 메소드 #파이썬 내장 메소드 시간 #시간 복잡도 분석 #python time complexity #time complexity python #time complexity