딕셔너리(dictionary; { })
▼ 표 2-5 딕셔너리의 시간 복잡도
|
시간 복잡도 |
기능 |
사용 예(변수: data) |
|
O(1) |
조회 |
data[1] / data.get(1, 0) |
|
값 할당 |
data[1] = 1 |
|
|
길이 가져오기 |
len(data) |
|
|
값 제거 |
del data[1] / data.pop(1) / data.popitem() |
|
|
딕셔너리 초기화 |
data.clear() |
|
|
딕셔너리 키 가져오기 |
data.keys() |
|
|
O(n) |
딕셔너리 할당 |
dict(data) |
|
딕셔너리 전체 연산 |
for i in data: |
배운 내용을 한 번 확인해볼까요? 주어진 데이터를 정렬하는 코드로 시간 복잡도를 계산해봅시다.
from random import choices
data = choices(range(1, 10), k=100000)
sorted(data)
임의의 데이터 10만 개를 정렬한다면 리스트 정렬은 O(nlogn)이므로 전체 시간 복잡도는 O(nlogn)이 됩니다.
처음부터 시간 복잡도를 바로 예측하는 것은 어렵습니다. 먼저 가장 오래 걸리는 작업이나 라이브러리 함수의 시간 복잡도를 계산하고, 추가로 연산이 발생하는 곳을 탐색하는 방향으로 잡는 것이 좋습니다. 이렇게 ‘코드를 실행하기 위해 이 정도 시간이 걸리겠구나’라는 감이 왔다면 본격적으로 시간 복잡도를 줄일 수 있는 방법을 알아보겠습니다.