[Algorithm] - Dict 주요 연산 시간복잡도
Python에서 딕셔너리(Dictionary)는 키(key)와 값(value)로 이뤄진 자료형이다. 내부적으로는 해시 테이블(Hash Table)로 구현되어 있다.
Dict의 주요 특징
- 인덕세를 숫자로만 지정할 수 있는 리스트와 달리 문자를 포함하여 다양한 타입을 키로 사용 가능
- 해시 테이블을 이용해 자료를 저장한다.
- 입력과 조회 모두 O(1)의 시간 복잡도를 가진다.
Dict의 주요 연산 시간복잡도 아래와 같다.
주요 연산 시간복잡도
| 순서 | 연산 | 예시 | 시간 복잡도 | 설명 |
|---|---|---|---|---|
| 1 | Store | a[k] = v | O(1) | 데이터 저장 |
| 2 | Length | len(a) | O(1) | 길이 출력 |
| 3 | Delete | del a[k] | O(1) | 요소 제거 |
| 4 | get/setdefault | a.get(k) | O(1) | key에 따른 value 확인 |
| 5 | Pop a.pop(k) | O(1) | pop | |
| 6 | Pop item | a.popitem() | O(1) | 랜덤하게 선택해서 pop |
| 7 | Clear | a.clear() | O(1) | similar to s = {} or = dict() |
| 8 | View | a.keys() | O(1) | same for a.values() / 키값 전체 확인 |
| 9 | Construction | dict(…) | O(len(…)) | (key, value) 튜플 개수만큼 |
| 10 | Iteration | for k in a: | O(N) | 전체 딕셔너리 순회 |