[순차탐색] in 연산자 시간복잡도 비교

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

 

주제: in 연산자는 어떤 자료형을 탐색하느냐에 따라 시간복잡도의 차이가 발생한다.

 

1) list / tuple / deque

• 구조: 연속 배열(리스트/튜플), 양방향 연결 버퍼(deque)
• 동작: 왼쪽부터 순차 비교(Linear scan) → 값이 같을 때까지 하나씩 == 비교
• 복잡도: 평균/최악 O(N)
• 비고: 정렬된 리스트라면 in 대신 이진탐색(예: bisect)을 쓰면 O(log N) 로 가능.
  단, in 자체는 이진탐색을 쓰지 않습니다.

x in [a, b, c, ...]     # O(N)
x in tuple_of_items     # O(N)
x in deque_of_items     # O(N)

 

2) set / dict

• 구조: 해시 테이블
• 동작: hash(x)로 버킷을 계산해 해당 버킷에서만 비교
• 복잡도: 평균 O(1), 최악(충돌 심함) O(N)
  (파이썬은 리사이즈·로드팩터 관리로 평균 O(1)를 잘 유지)
• 주의: 원소는 해시 가능(불변·hashable) 해야 함. list/dict는 안 되고, tuple(내부도 불변이면)는 가능.
• 딕셔너리의 in: 키에 대한 멤버십 검사입니다.
  x in my_dict → x in my_dict.keys()와 동일(평균 O(1)). 
  • x in my_dict.values() / x in my_dict.items() 는 선형탐색 O(N) 이라 느립니다.

x in {a, b, c}          # 평균 O(1)
key in {"k": 1}         # 평균 O(1)  (키 검사)
val in {"k": 1}.values()# O(N)       (값 검사)

 

(해시 기반이 O(1)인 이유)

• set/dict는 버킷 배열을 두고, hash(x) % capacity 로 위치를 바로 찾아갑니다.
• 동일 해시의 원소가 많아지면 충돌 체인을 따라 비교하므로 느려질 수 있어 로드팩터 임계에서 자동 리사이즈합니다.
• 평균적으로 충돌 길이를 짧게 유지하여 상수 시간에 가깝게 동작합니다.

 

3) str (문자열)

• 단일 문자 검사: ch in text → 선형 탐색, 평균 O(N)
• 부분문자열 검사: pat in text → 전통적으론 O(N·M) 이지만 CPython은 Two-Way 등 최적화로 평균 O(N)에 가깝게 동작.
• 비고: 매우 큰 텍스트에서는 re(정규식), find(), index() 등 전용 알고리즘을 쓰는 게 더 낫습니다.

'a' in 'banana'       # O(N)
'ana' in 'banana'     # ~O(N) (내부 최적화)

 

 

4) 왜 “list→set 변환”이 빠를까?

멤버십 검사를 여러 번 할 때는, 한 번의 변환 비용(O(N))을 내고 평균 O(1) 조회를 반복하는 편이 압도적으로 유리합니다.

• 리스트에서 M번 검사: O(M·N)
• 세트로 변환 후 M번 검사: O(N) + O(M)

의사결정 팁
– 한 번만 검사하면: 그냥 리스트에서도 괜찮음
– 많이 검사하면(M이 크면): set으로 변환이 유리
– 이미 키만 검사하면: dict 키 집합을 그대로 활용

menus = ['ramen', 'sushi', 'pasta', ...]   # N개
queries = ['sushi', 'taco', ...]           # M개

# 느린 버전: O(M·N)
for q in queries:
    if q in menus:
        ...

# 빠른 버전: O(N) + O(M)
menu_set = set(menus)
for q in queries:
    if q in menu_set:   # 평균 O(1)
        ...

 

5) 요약 표

컨테이너 x in container 평균 복잡도 내부 구조 비고

컨테이너	x in container 평균 복잡도	내부 구조	비고
list / tuple / deque	O(N)	배열/연결버퍼	선형 탐색
set	O(1)	해시 테이블	원소는 hashable 필요
dict	O(1) (키)	해시 테이블	x in d는 키 검사
dict.values() / .items()	O(N)	선형 탐색	값/쌍 검사
str (문자/부분문자열)	~O(N)	특화 검색	내부 최적화 있음

 

 

 

참고:

이진탐색시에 문자열 "가나다" 도 크기 비교가 가능하다.

한글을 유니코드값으로 바꿔서 크기를 비교함