오뚝이개발자

[Python] 파이썬 in 연산 시간복잡도 본문

Language/파이썬

[Python] 파이썬 in 연산 시간복잡도

땅어 2020. 12. 2. 15:06
728x90
300x250

 

파이썬에는 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


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)

 

시간복잡도


핵심은 각 자료구조마다 in을 사용할 때 시간복잡도가 다르다는 것이다.

list, tuple

  • Average : O(n)
  • 하나하나 순회하기 때문에 O(n)만큼의 시간복잡도를 갖는다

set, dictionary

  • Average : O(1), Worst : O(n)
  • 내부적으로 hash를 통해 저장하므로 접근하는 시간은 O(1)이다. 하지만 해쉬의 충돌이 많아 성능이 떨어지는 경우 O(n)이 걸릴 수도 있다.

 

 

참고자료

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

 

728x90
300x250
Comments