[python] in 시간복잡도

참고: python wiki
https://wiki.python.org/moin/TimeComplexity

in 연산의 시간복잡도가 궁금해서 찾아보게 되었다.

---

in 연산의 시간복잡도

자료형에 따른 시간복잡도의 차이가 있다.

자료형	average	worse case
list	O(n)	O(n)
tuple	O(n)	O(n)
set	O(1)	O(n)
dict	O(1)	O(n)

• list와 tuple은 하나하나 순회하기 때문에 O(n)
• set과 dictionary는 내부적으로 hash를 이용해 저장하기에 O(n), 해시의 충돌이 많은 경우 O(1)이 된다.