[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)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.


참고자료