파이썬 세트 작업의 시간 복잡성?

파이썬 세트 작업의 시간 복잡성?

Big O 표기법에서 파이썬의 각 집합 연산의 시간 복잡도는 얼마입니까?

저는 많은 항목에 대한 작업에 파이썬의 set type을 사용하고 있습니다.세트의 크기에 따라 각 작업의 성능이 어떻게 영향을 받는지 알고 싶습니다.예를 들어, 추가 및 구성원 자격 검정:

myset = set()
myset.add('foo')
'foo' in myset

구글 검색을 통해 리소스를 찾을 수는 없지만 Python의 세트 구현에 대한 시간 복잡성을 신중하게 고려했을 것으로 보입니다.

만약 그것이 존재한다면, 이와 같은 것에 대한 링크가 좋을 것입니다.이런 일이 없다면, 우리가 해결할 수 있을까요?

모든 집합 작업의 시간 복잡도를 찾기 위한 추가 표시입니다.

파이썬 위키에 따르면: 시간 복잡도, 집합은 해시 테이블로 구현됩니다.따라서 O(1) 평균에서 조회/삽입/삭제를 예상할 수 있습니다.해시 테이블의 로드 팩터가 너무 높지 않으면 충돌과 O(n)가 발생합니다.

추신: 어떤 이유로 그들은 잘못된 유형으로 보이는 삭제 작업에 대해 O(n)를 주장합니다.

P.P.S. 이것은 Cython에게 사실입니다, Pypy는 다른 이야기입니다.

다른 답변은 세트에서 두 가지 중요한 작업에 대해 말하지 않습니다.조합과 교차로.최악의 경우, 집합에 동일한 해시를 가진 요소가 많지 않다면 유니언은 O(n+m)를 취하는 반면 교차는 O(min(x,y))를 취합니다.일반적인 작업의 시간 복잡성 목록은 https://wiki.python.org/moin/TimeComplexity 에서 확인할 수 있습니다.

그 작전in컨테이너의 크기, 즉 O(1) -- 최적의 해시 함수가 주어지면 독립적이어야 합니다.이것은 Python 문자열에 대해 거의 사실입니다.해시 문자열은 항상 중요합니다. Python은 그곳에서 영리해야 하므로 거의 최적의 결과를 기대할 수 있습니다.

언급URL : https://stackoverflow.com/questions/7351459/time-complexity-of-python-set-operations