Counter, hash table, 그리고 python에서는 조금 다른 시간 복잡도

1. Counter

오늘은 Python의 collections 모듈에 포함된 Counter 클래스에 대해서 알아볼 것이다. -> hash table의 일종

Counter 클래스: 

          키 -> 요소

          값 -> 요소의 개수

 

데이터의 빈도수를 쉽게 계산할 수 있다.

from collections import Counter

# 문자열에서 문자의 빈도수 계산
char_count = Counter('banana')
print(char_count)  # 출력: Counter({'a': 3, 'b': 1, 'n': 2})

# 리스트에서 요소의 빈도수 계산
word_count = Counter(['apple', 'banana', 'apple', 'orange', 'banana', 'apple'])
print(word_count)  # 출력: Counter({'apple': 3, 'banana': 2, 'orange': 1})

# 빈도수가 가장 높은 요소 찾기
most_common = word_count.most_common(1)
print(most_common)  # 출력: [('apple', 3)]

이런식으로 사용할 수 있다. .most_common(1) 을 통해서 빈도수가 가장 높은 요소를 찾을 수 있다.  -> 상위 1개의 요소 반환

 

most_common([n]) 가장 흔한 n개의 요소 + 요소의 개수를 내림차순으로 반환한다.

만약, .most_common(2) 라면 -> 빈도수가 가장 높은 상위 2개의 요소 + 개수 를 tuple로 묶어 리스트 형태로 반환.

 

2. Hash Table

정의: 키를 값에 매핑하는 데이터 구조 -> 효율적인 검색, 삽입, 삭제 작업을 지원함.

 

키 => 해시 함수 => 해시 코드

 

충돌이 일어날 경우: 1) 체이닝 2) 오픈 어드레싱 

 

1) 체이닝: 이미 해당 hash table이 차 있을 경우, 연결 리스트를 이용

2) 오픈 어드레싱: 충돌이 일어난다면 해당 인덱스에 저장하는 것이 아니라, 빈 인덱스를 찾아서 저장한다.

 

시간 복잡도 : O(1) 이지만, 모든 키가 동일한 인덱스로 해싱되는 경우 -> O(n) 의 시간 복잡도를 가진다.

 

3. python에서는 조금 다른 시간 복잡도

if s in dictionary

이 부분은 다른 언어에서 O(n)의 복잡도를 지니는 것으로 알고 있다. 

하지만 python의 경우 dictionary가 hash 로 구성되어 있기 때문에 O(1)의 복잡도를 가진다. 

python의 dictionary를 애용할 이유가 생겼다.