🚀 파이썬의 set 함수와 list 함수의 in 함수 사용 시 시간복잡도

⏱️ 파이썬의 set 함수와 list 함수의 in 함수 사용 시 시간복잡도

in 함수 사용 시

set 함수: 평균 O(1)
dict 함수 : 평균 O(1)
list 함수: 평균 O(n)

set 함수는 내부적으로 해시 테이블을 사용하여 데이터를 저장하기 때문에 in 연산을 평균 O(1)의 시간 복잡도로 수행할 수 있습니다.

 

반면에 list 함수는 내부적으로 동적 배열을 사용하여 데이터를 저장합니다.

 

이때, in 연산은 리스트를 처음부터 끝까지 순차적으로 탐색해야 하므로, 평균 O(n)의 시간 복잡도를 가지게 됩니다.

즉, 리스트의 크기가 커질수록 in 연산의 속도는 느려질 수밖에 없습니다.

 

 

 

 

 

 

테스트 결과

test=1000000

set_func=set()
for i in range(test) :
    set_func.add(i)
list_func=[i for i in range(test)]

파이썬 실행결과

 

 

 

 

 

🔍 해시 테이블이란?

해시 테이블(Hash table)은 키(Key)와 값(Value)으로 데이터를 저장하는 자료구조입니다.

배열의 인덱스를 키(Key)로 사용하여 데이터를 저장하고, 이 키(Key)를 해시 함수(Hash function)에 넣어 해시 값(Hash value)을 생성한 후, 이 값을 인덱스로 사용하여 데이터를 검색합니다.

 

해시 테이블은 검색, 삽입, 삭제 등의 연산을 평균 O(1)의 시간 복잡도로 수행할 수 있습니다. 따라서, 많은 양의 데이터를 빠르게 검색해야 하는 경우에 유용하게 사용할 수 있는 자료구조입니다.

 

파이썬에서는 dict 데이터 타입이 해시 테이블을 구현하는데 사용됩니다. dict는 {}를 사용하여 생성할 수 있으며, 각각의 항목은 key: value 형태로 구성됩니다.

dict에서도 in 연산은 해시 테이블을 이용하여 평균 O(1)의 시간 복잡도로 수행됩니다. 따라서, 많은 양의 데이터를 빠르게 검색해야 하는 경우에도 dict를 사용할 수 있습니다.

💡 결론

set 함수와 list 함수 모두 in 연산을 지원합니다. 하지만, set 함수를 사용하면 평균 O(1)의 시간 복잡도로 in 연산을 수행할 수 있고, list 함수를 사용하면 평균 O(n)의 시간 복잡도로 in 연산을 수행할 수 있습니다. 따라서, 많은 양의 데이터를 빠르게 검색해야 하는 경우에는 set 함수를 사용하는 것이 좋습니다.

 

또한, dict를 사용하면 해시 테이블을 이용하여 평균 O(1)의 시간 복잡도로 데이터를 검색할 수 있습니다. 하지만, dict는 순서를 보장하지 않기 때문에, 입력한 순서대로 데이터를 처리해야 하는 경우에는 collections 모듈의 OrderedDict를 사용하는 것이 좋습니다.