내장 함수 시간 복잡도
추가로 파이썬에서 자주 사용하는 내장 함수인 리스트와 집합, 딕셔너리의 시간 복잡도를 알아보겠습니다. 개발의 편의성과 안전성을 위해 내장 함수와 라이브러리를 자주 사용하곤 하는데, 각각의 시간 복잡도 또한 알아 둘 필요가 있습니다. 코드의 시간 복잡도를 생각하는 것도 중요하지만, 사용하는 함수의 실행 시간이 어느 정도인지 모른다면 예측했던 것과 다른 결과가 나올 것입니다. 책에 실린 내용 외에도 개인적으로 자주 사용하는 코드가 있다면 실행 시간을 직접 찾아볼 것을 권장합니다.
리스트(list; [ ])
▼ 표 2-3 리스트의 시간 복잡도
|
시간 복잡도 |
기능 |
사용 예(변수: data, data2) |
|
O(1) |
조회 |
data[1] |
|
값 할당 |
data[1] = 1 |
|
|
길이 가져오기 |
len(data) |
|
|
리스트 1개 추가 |
data.append(2) |
|
|
마지막 리스트 1개 제거 |
data.pop() |
|
|
리스트 초기화 |
data.clear() |
|
|
O(n) |
리스트 슬라이싱 |
data[a:b]1 |
|
리스트 + 리스트 |
data.extend(data2) |
|
|
리스트 할당 |
list(data) |
|
|
리스트 비교 |
data == data2 / data != data2 |
|
|
값 범위 할당 |
data[a:b] = 3 |
|
|
특정 리스트 항목 제거 |
del data[1] / data.pop(1) |
|
|
리스트에 값이 있는지 확인 |
1 in data |
|
|
리스트 복사 |
data.copy() |
|
|
최솟값/최댓값 탐색 |
min(data), max(data) |
|
|
리스트 역순 |
data.reverse() |
|
|
리스트 전체 연산 |
for v in data: |
|
|
O(nlogn) |
리스트 정렬 |
data.sort() / sorted(data) |
|
O(kn) |
데이터 전체 반복(k번) |
2 * data |