(Python) 파이썬 - list, Dict의 메소드 시간복잡도

알고리즘 문제들을 풀다보면 로직과 도출되는 결과값은 같지만, 시간복잡도 때문에 애먹는 경우가 많았다.

확실히 입력값들이 많으면 많을수록 시간복잡도를 고려해야할것같다.

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

 

 

이곳에 가면 온갖 연산들에 대한 시간복잡도가 있다. 자주 쓰는것들만 정리해보면

 

Python의 List 연산에 대한 시간복잡도

Operation	ex	BigO	Notes
Index	arr[i]	O(1)	그냥 값에 접근
Length	len(arr)	O(1)
Append	arr.append(4)	O(1)
Pop	arr.pop()	O(1)
Slice	arr[a:b]	O(b-a)	자를 길이에 따라 달라진다
Extend	arr.extend(...)	O(len(...))	확장할 길이에 따라 달라진다.
Insert	arr.insert(i, v)	O(N)
Delete	del arr[i]	O(N)
Pop	arr.pop(i)	O(N)
Reverse	Arr.reverse()	O(N)
Sort	arr.sort()	O(N LogN)
Iteration	for i in arr:	O(N)
Store	arr[i] = v	O(1)	그냥 저장, 수정하는것을 말함

인덱스를 지정하는 연산의 경우에 무조건 O(N)의 시간복잡도가 들어간다. (굵은 글씨) 이 자료들을 보니 왜 리스트보다 Stack이나, Queue등이 연산이 빠른지 알것같다.

Python Dictionary 연산의 시간복잡도

Operation	ex	BigO	Notes
Index	d[k]	O(1)	그냥 값에 접근
Store	d[k] = v	O(1)	그냥 저장
Length	len(d)	O(1)
Delete	del d[k]	O(1)
Get	d.get	O(1)
Pop	d.pop(k)	O(1)
Pop item	d.popitem()	O(1)
Veiw	d.keys() / d.values()	O(1)

확실히 Key와 Value값으로 접근하기 때문에 거의 O(1)이다.

set은 사용할일이 잘 없어서 생략..