[Python] 파이썬 'in' 연산자 시간 복잡도(Time Complexity)
Python에서 in 연산자의 시간 복잡도에 대해서 알아보자
환경 및 선수조건
- Python(3.X)
파이썬 in 연산
- 파이썬
in연산자란 멤버십 연산자로 문자열이나 리스트나 튜플과 같이 연속적인 자료구조에 속한 멤버를 확인하기 위한 연산자입니다.
기본 사용법
list
l = [1, 2, 3, 4, 5]
# 멤버 확인
if 1 in l :
print("1 is in l")
# 순회
for i in l :
print(i)
tuple
t = (1, 2, 3, 4, 5)
# 멤버 확인
if 1 in t :
print("1 is in t")
# 순회
for i in t :
print(i)
set
s = {1, 2, 3, 4, 5}
# 멤버 확인
if 1 in s :
print("1 is in s")
# 순회
for i in s :
print(i)
dictionary keys
d = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'}
# 멤버 확인
if 1 in d.keys() :
print("1 is in d keys")
# 순회
for i in d.items() :
print(i)
시간 복잡도
list, tuple
- Average:
O(n) - 하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.
set, dictionary
- Average:
O(1), Worst:O(n) - 내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가
O(1)가 가능하고O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.