☰ Menu Python

☰ Menu

내장형 타입의 연산 시간 복잡도

이 페이지는 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 를 사용하는 것을 고려하십시오.

연산	복잡도
복사 (l.copy())	O(n)
Append (l.append(x)) [1]	O(1)
Pop (l.pop(k)) [1] [2]	O(n - k)
Insert (l.insert(k, x)) [1] [2]	O(n - k)
항목 가져오기 (l[k])	O(1)
항목 설정 (l[k] = x)	O(1)
항목 삭제 (del l[k]) [2]	O(n - k)
이터레이션	O(n)
슬라이스 가져오기 (l[i:j])	O(j - i)
슬라이스 설정 (l[i:j] = t) [1]	O(j - i) if len(t) == j - i, otherwise O(n - i + len(t))
슬라이스 삭제 (del l[i:j])	O(n - i)
Extend (l.extend(t)) [1] [3]	O(len(t))
Sort (l.sort()) [4]	O(n log n)
Concatenate (l1 + l2)	O(len(l1) + len(l2))
Multiply (l * k)	O(nk)
x in l	O(n)
min(l), max(l)	O(n)
길이 가져오기 (len(l)) [5]	O(1)

tuple

tuple 은 불변 시퀀스입니다. 튜플은 변경될 수 없으므로 삽입이나 삭제에 드는 비용이 없으며, 복사본을 만드는 것은 단순히 동일한 객체를 반환하므로 상수 시간(O (1))이 소요됩니다.

연산	복잡도
복사 (tuple(t))	O(1)
항목 가져오기 (t[k])	O(1)
슬라이스 가져오기 (t[i:j])	O(j - i)
Concatenate (t1 + t2)	O(len(t1) + len(t2))
곱하기 (t * k)	O(nk)
이터레이션	O(n)
x in t	O(n)
min(t), max(t)	O(n)
길이 구하기 (len(t)) [5]	O(1)

dict, frozendict

dict 객체에 대해 나열된 시간은 평균적인 경우의 시간입니다. 이는 객체에 대한 해시 함수가 충돌을 발생시키지 않을 만큼 충분히 견고하다고 가정하기 때문입니다. 또한 키가 가능한 키 세트 내에 고르게 분포되어 있다고 가정합니다. 최악의 경우, 모든 키가 동일한 값으로 해싱되면 아래의 O (1) 연산들은 각각 O (n) 시간이 소요됩니다. 또한 키를 해싱하고 비교하는 것이 O (1)이라고 가정합니다. 구현에 대한 자세한 내용은 CPython에서 딕셔너리는 어떻게 구현됩니까? 를 참조하십시오.

frozendict 는 불변이므로 항목을 설정, 삭제 또는 업데이트하는 기능을 지원하지 않습니다. 아래의 다른 연산들은 동일한 비용으로 적용됩니다.

연산	복잡도
key in d	O(1)
복사 (d.copy()) [6] [7]	O(n)
항목 가져오기 (d[key], d.get(key))	O(1)
항목 설정 (d[key] = value) [1]	O(1)
항목 삭제 (del d[key], d.pop(key))	O(1)
업데이트 (d.update(t), d |= t) [1] [3] [7]	O(len(t))
이터레이션 [7]	O(n)
길이 구하기 (len(d)) [5]	O(1)

set, frozenset

dict 가 set 및 frozenset 구현과 유사하므로 동일한 주의 사항이 적용됩니다. 최악의 경우, O (1) 연산이 대신 O (n) 시간이 소요되며, 모든 요소를 조회하는 연산의 성능이 그에 따라 저하됩니다.

frozenset 은 immutable 이므로 추가, 제거 또는 인플레이스 업데이트 연산을 지원하지 않습니다. 아래의 다른 연산들은 동일한 비용으로 적용됩니다.

연산	복잡도
x in s	O(1)
복사 (s.copy()) [6] [7]	O(n)
추가 (s.add(x)) [1]	O(1)
제거 (s.discard(x), s.remove(x))	O(1)
합집합 (s1 | s2, s1.union(s2)) [7]	O(len(s1) + len(s2))
Update (s1 |= s2, s1.update(s2)) [1] [7]	O(len(s2))
Intersection (s1 & s2, s1.intersection(s2)) [7] [8]	O(min(len(s1), len(s2)))
Intersection update (s1 &= s2, s1.intersection_update(s2)) [1] [7] [8]	O(min(len(s1), len(s2)))
차이 (s1 - s2, s1.difference(s2)) [7] [9]	O(len(s1))
차집합 업데이트 (s1 -= s2, s1.difference_update(s2)) [1] [7] [8]	O(min(len(s1), len(s2)))
대칭 차집합 (s1 ^ s2, s1.symmetric_difference(s2)) [7]	O(len(s1) + len(s2))
대칭 차이 업데이트 (s1 ^= s2, s1.symmetric_difference_update(s2)) [1] [7]	O(len(s2))
길이 구하기 (len(s)) [5]	O(1)

str, bytes, bytearray

str 와 bytes 객체는 각각 문자와 바이트의 불변 시퀀스입니다. 튜플과 마찬가지로, 하나를 복사하면 원본 객체를 반환합니다. bytearray 는 가변이며, 추가로 list 의 변형 연산(단, sort() 제외)을 동일한 비용으로 지원합니다. 그러나 del 을 사용하여 앞부분을 삭제하는 경우(del b[0], del b[:k]) 남은 바이트를 이동시키는 대신 버퍼의 시작 부분만 전진시키므로, 평균적으로 O (1)입니다.

연산	복잡도
항목 가져오기 (s[k])	O(1)
슬라이스 가져오기 (s[i:j])	O(j - i)
연결 (s + t) [10]	O(len(s) + len(t))
곱하기 (s * k)	O(nk)
부분 문자열 검색 (x in s, s.find(x), s.index(x)) [11]	O(n)
역방향 부분 문자열 검색 (s.rfind(x), s.rindex(x)) [11] [12]	O(n × len(x))
인코딩 또는 디코딩 [13]	O(n)
이터레이션	O(n)
길이 구하기 (len(s)) [5]	O(1)

memoryview

memoryview 객체는 파이썬 코드가 복사 없이 buffer protocol 를 지원하는 객체의 내부 데이터에 접근할 수 있게 합니다. 특히, 메모리 뷰를 슬라이싱하면 동일한 버퍼에 대한 새로운 뷰를 반환합니다.

연산	복잡도
생성 (memoryview(obj))	O(1)
항목 가져오기 (v[k])	O(1)
슬라이스 가져오기 (v[i:j])	O(1)
인덱스 (v.index(x)) [11] [14]	O(n)
Count (v.count(x)) [14]	O(n)
바이트로 변환 (v.tobytes(), bytes(v))	O(n)
길이 구하기 (len(v)) [5]	O(1)

range

range 객체는 start, stop, step 값을 기반으로 요청 시에 항목을 계산하므로, 대부분의 연산은 범위의 길이에 의존하지 않습니다.

연산	복잡도
항목 가져오기 (r[k])	O(1)
슬라이스 가져오기 (r[i:j])	O(1)
x in r [15]	O(1)
인덱스 및 개수 (r.index(x), r.count(x)) [15]	O(1)
이터레이션	O(n)
min(r), max(r)	O(n)
길이 가져오기 (len(r)) [5]	O(1)

참고

[1] (1,2,3,4,5,6,7,8,9,10,11,12)

분할 상환(Amortized). 기반 저장소가 리사이즈될 때 개별 연산이 가끔 O(n)이 될 수 있지만, 이 비용은 컨테이너의 이력에 따라 많은 연산에 걸쳐 분산됩니다.

[2] (1,2,3)

크기가 n*인 리스트에서 인덱스 *k*에 있는 요소를 제거하거나 삭제하면 *k 이후의 모든 요소가 왼쪽으로 한 칸씩 이동하며, n - k - 1개의 요소가 이동합니다. 인덱스 k*에 요소를 삽입하면 *k*부터 시작하는 요소들이 오른쪽으로 한 칸씩 이동하며, *n - k*개의 요소가 이동합니다. 최악의 경우는 모든 나머지 리스트를 이동시켜야 하는 인덱스 0이며, 평균적인 경우(리스트 중간의 인덱스)는 *O(n/2) = O(n)의 연산이 소요됩니다. 리스트 끝에서 수행하는 연산은 아무것도 이동시키지 않으며 O(1)입니다.

[3] (1,2)

t 을 순회하는 비용이 추가되며, 이는 임의의 이터러블(iterable)에 대해 비용이 많이 들 수 있습니다.

[4]

이것은 최악의 경우 시나리오입니다. 정렬은 적응형이며 이미 정렬되었거나 역순으로 정렬된 입력은 단지 O (n) 비교만 수행합니다. 자세한 내용은 Objects/listsort.txt 를 참조하십시오.

[5] (1,2,3,4,5,6,7)

요소의 수가 객체에 저장되어 있으므로, len() 은 이를 세지 않아도 됩니다.

[6] (1,2)

frozendict 또는 frozenset 을 복사하는 것은 원래 객체를 반환하므로 O (1)입니다.

[7] (1,2,3,4,5,6,7,8,9,10,11,12)

이 연산들은 컨테이너의 내부 해시 테이블을 스캔하며, 요소가 제거되어도 이 테이블은 줄어들지 않습니다. 대부분의 요소를 제거한 후에도, 나중에 삽입할 때 리사이즈가 발생하기 전까지는 컨테이너의 이전 크기에 비례하는 시간이 소요됩니다.

[8] (1,2,3)

t*이 집합(set)이 아닌 경우 *O(len(t)).

[9]

t*이 세트가 아닌 경우 *O(len(s) + len(t))

[10]

각 이어붙이기는 새로운 객체를 생성하므로, 루프에서 여러 조각을 이어 붙여 문자열을 만드는 것은 전체 길이에 대해 이차의 비용이 발생합니다. 대안을 확인하려면 note on concatenating immutable sequences 을 참조하십시오.

[11] (1,2,3)

start 와 end 인자가 있는 경우, n 은 s 의 길이가 아니라 검색된 영역의 길이이며, 슬라이싱과 달리 아무것도 복사되지 않습니다.

[12]

이것은 최악의 경우입니다. 일반적인 입력에 대한 역방향 검색은 O (n)입니다. 정방향 검색은 대신 Objects/stringlib/stringlib_find_two_way_notes.txt 에 설명된 선형 최악의 경우를 가진 더 복잡한 알고리즘을 사용합니다.

[13]

이것은 문자당 일정한 양의 작업을 수행하는 코덱을 가정합니다.

[14] (1,2)

이 기능들은 각 요소를 개별적으로 풀어서 비교하므로, 동일한 기능을 수행하는 bytes 메서드보다 훨씬 느립니다.

[15] (1,2)

int 또는 bool 인자를 가정합니다. 다른 유형의 경우, 범위는 다른 모든 시퀀스와 마찬가지로 O(n) 시간에 검색됩니다.