[CS기초] Set은 왜 이진 탐색보다 빠르게 데이터 유무를 알 수 있을까?

집합(Set)은 중복된 값을 허용하지 않는 자료구조입니다. 파이썬의 Set 자료형은 내부적으로 해싱(Hashing)을 사용하여 값을 저장하기 때문에, 평균적으로 O(1)의 시간 복잡도로 빠르게 요소의 존재 여부를 확인할 수 있습니다. 이진 탐색이 O(logN)의 시간 복잡도인 것을 생각하면 굉장히 빠르다고 할 수 있지요.

 

해시 테이블(Hash Table)이 키(Key)와 값(Value)의 쌍을 저장하는 것과 달리, 집합은 키만을 저장하기 때문에 메모리 사용 측면에서도 더 효율적입니다. 따라서 집합은 중복된 데이터를 제거하거나 특정 요소의 존재 여부를 빠르게 확인하는 용도로 자주 활용됩니다.