내장형 타입 연산의 시간 복잡도¶
이 페이지는 CPython에서 내장형 타입의 다양한 연산에 대한 시간 복잡도를 설명합니다. 다른 파이썬 구현은 다른 성능 특성을 가질 수 있습니다. 또한, 나열된 비용은 정확한 내장 타입을 가정하며, 하위 클래스의 인스턴스는 다른 비용이 발생할 수 있습니다.
We use Big O notation to describe how the running time of an operation grows with the size of its inputs. Unless stated otherwise, n denotes the number of elements currently in the container, and k is the value of a numeric parameter, such as an index or a repeat count.
list¶
리스트는 가변 시퀀스입니다. 구현에 대한 자세한 내용은 CPython에서 리스트는 어떻게 구현됩니까? 를 참조하십시오. 가장 큰 비용은 현재 할당 크기를 초과하여 확장할 때(모든 데이터가 이동해야 하므로) 또는 시작 부분 근처에 삽입하거나 삭제할 때(그 이후의 모든 데이터가 이동해야 하므로) 발생합니다. 양쪽 끝에서 항목을 추가하거나 제거해야 하는 경우 collections.deque 사용을 고려하십시오.
연산 |
복잡도 |
|---|---|
복사 ( |
O(n) |
추가(Append) ( |
O(1) |
O(n - k) |
|
O(n - k) |
|
항목 가져오기 ( |
O(1) |
항목 설정 ( |
O(1) |
항목 삭제 ( |
O(n - k) |
이터레이션 |
O(n) |
슬라이스 가져오기 ( |
O(j - i) |
슬라이스 설정 ( |
O(j - i) if len(t) == j - i, otherwise O(n - i + len(t)) |
슬라이스 삭제 ( |
O(n - i) |
O(len(t)) |
|
정렬(Sort) ( |
O(n log n) |
연결(Concatenate) ( |
O(len(l1) + len(l2)) |
곱하기(Multiply) ( |
O(nk) |
|
O(n) |
|
O(n) |
길이 가져오기 ( |
O(1) |
tuple¶
A tuple is an immutable sequence. Because a tuple can never
change, there are no insertion or deletion costs, and making a copy simply
returns the same object, so is constant time (O(1)).
연산 |
복잡도 |
|---|---|
복사 ( |
O(1) |
항목 가져오기 ( |
O(1) |
슬라이스 가져오기 ( |
O(j - i) |
연결(Concatenate) ( |
O(len(t1) + len(t2)) |
곱셈 ( |
O(nk) |
이터레이션 |
O(n) |
|
O(n) |
|
O(n) |
길이 가져오기 ( |
O(1) |
dict, frozendict¶
딕셔너리 객체에 대해 나열된 시간은 해시 함수가 충분히 견고하여 충돌이 드문 경우를 가정한 평균적인 경우의 시간입니다. 또한 키가 가능한 키들의 집합에 잘 분산되어 있다고 가정합니다. 최악의 경우, 모든 키가 동일한 값으로 해싱되는 경우 아래의 각 O (1) 연산은 대신 O (n)의 시간이 소요됩니다. 또한 키의 해싱 및 비교는 O (1)이라고 가정합니다. 구현에 대한 자세한 내용은 CPython에서 딕셔너리는 어떻게 구현됩니까? 를 참조하십시오.
frozendict 은 불변(immutable)이므로 항목 설정, 삭제 또는 업데이트를 지원하지 않습니다. 그 아래의 다른 작업들은 동일한 비용으로 적용됩니다.
연산 |
복잡도 |
|---|---|
|
O(1) |
O(n) |
|
항목 가져오기 ( |
O(1) |
항목 설정 ( |
O(1) |
항목 삭제 ( |
O(1) |
O(len(t)) |
|
이터레이션 [7] |
O(n) |
길이 구하기 ( |
O(1) |
set, frozenset¶
set 및 frozenset 구현이 dict 와 유사하므로 동일한 주의 사항이 적용됩니다. 최악의 경우, O (1) 연산이 O (n)의 시간이 소요되며, 모든 요소를 조회하는 연산도 그에 따라 성능이 저하됩니다.
frozenset 은 immutable 이므로, 추가, 제거 또는 인플레이스 업데이트 연산을 지원하지 않습니다. 그 외의 항목들은 동일한 비용으로 적용됩니다.
연산 |
복잡도 |
|---|---|
|
O(1) |
O(n) |
|
추가(Add) ( |
O(1) |
제거(Discard) ( |
O(1) |
합집합(Union) ( |
O(len(s1) + len(s2)) |
O(len(s2)) |
|
O(min(len(s1), len(s2))) |
|
교집합 업데이트(Intersection update) ( |
O(min(len(s1), len(s2))) |
O(len(s1)) |
|
차집합 업데이트(Difference update) ( |
O(min(len(s1), len(s2))) |
대칭 차집합(Symmetric difference) ( |
O(len(s1) + len(s2)) |
대칭 차이 업데이트 ( |
O(len(s2)) |
길이 구하기 ( |
O(1) |
str, bytes, bytearray¶
str and bytes objects are immutable sequences of characters and
bytes, respectively. As with tuples, copying one returns the original object.
A bytearray is mutable, and additionally supports the mutating operations
of list (except sort()), at the same costs. However, deleting at
the front with del (del b[0], del b[:k]) only advances the start of
the buffer instead of moving the remaining bytes, and is amortized O(1).
연산 |
복잡도 |
|---|---|
항목 가져오기 ( |
O(1) |
슬라이스 가져오기 ( |
O(j - i) |
연결(Concatenate) ( |
O(len(s) + len(t)) |
곱셈 ( |
O(nk) |
부분 문자열 검색 ( |
O(n) |
O(n × len(x)) |
|
인코딩 또는 디코딩 [13] |
O(n) |
이터레이션 |
O(n) |
길이 구하기 ( |
O(1) |
memoryview¶
memoryview 객체는 파이썬 코드가 buffer protocol 를 지원하는 객체의 내부 데이터에 복사 없이 접근할 수 있게 합니다. 특히, memory view를 슬라이싱하면 동일한 버퍼에 대한 새로운 뷰를 반환합니다.
연산 |
복잡도 |
|---|---|
생성(Create) ( |
O(1) |
항목 가져오기 ( |
O(1) |
슬라이스 가져오기 ( |
O(1) |
O(n) |
|
개수 세기(Count) ( |
O(n) |
바이트로 변환 ( |
O(n) |
길이 구하기 ( |
O(1) |
range¶
range 객체는 start, stop 및 step 값을 바탕으로 요청 시에 항목을 계산하므로, 대부분의 연산이 범위의 길이에 의존하지 않습니다.
연산 |
복잡도 |
|---|---|
항목 가져오기 ( |
O(1) |
슬라이스 가져오기 ( |
O(1) |
|
O(1) |
인덱스 및 개수 ( |
O(1) |
이터레이션 |
O(n) |
|
O(n) |
길이 가져오기 ( |
O(1) |