[python] in 연산자의 실행시간, 시간 복잡도 BigO

---

in 연산자

파이썬에서 자주 사용되는 in 연산자 예제

ls = [1, 2, 3]
if 4 in ls :
	print("exist")
else :
	print("not exist")
    
>>> "not exist"

dc = {
    'a' : 1,
    'b' : 2,
    'c' : 3,
}
if 'c' in dc.keys() :
	print("exist")
else :
	print("not exist")

for k, v in dc.items():
    if k == 'c':
        print(v)
        
>>> "exist"
>>> 3

 

---

in 연산자의 Big-O

 

나는 알고리즘 공부를 하던 중에 in연산자의 bigO가 궁금해졌다.

해시의 문제풀이로 사용되는 dict의 경우 in 연산자가 어떤 속도를 내게 될지 궁금해졌기 때문이다.

그리고 list, tuple / set, dict 객체에서 in연산자의 실행 속도가 서로 다른 것을 확인했다.

 

Big-O

list , tuple

• list나 tuple인 경우엔 시간 복잡도가 O(n)이다.
• 선형 검색의 형태이다.

set , dict

• 평균 실행시간 O(1)
• 최악의 경우 O(n)이 될 수 있다. 이것은 hash충돌이 많아질 경우 성능 저하로 발생한다.

 

---

참고 링크

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

https://twpower.github.io/120-python-in-operator-time-complexity