Python의 *in* 연산자의 복잡성

Python의 *in* 연산자의 복잡성

복잡성은 무엇입니까?in파이썬의 연산자?세타(n)인가요?

이것은 다음과 같습니까?

def find(L, x):
   for e in L:
       if e == x:
           return True
   return False

L목록입니다.

의 복잡성in전적으로 무엇에 달려 있습니다.L사실은.e in L될 것입니다L.__contains__(e).

여러 기본 제공 유형의 복잡성은 이 시간 복잡성 문서를 참조하십시오.

다음의 요약은 다음과 같습니다.in:

• 리스트 - 평균: O(n)
• set/dict - 평균: O(1), 최악: O(n)

세트와 딕트에 대한 O(n) 최악의 경우는 매우 드물지만 다음과 같은 경우 발생할 수 있습니다.__hash__제대로 구현되지 않았습니다.이 문제는 집합의 모든 항목이 동일한 해시 값을 갖는 경우에만 발생합니다.

그것은 전적으로 용기의 유형에 따라 다릅니다.해싱 용기(dict,set) 해시를 사용하고 기본적으로 O(1)입니다.일반적인 시퀀스(list,tuple)는 사용자가 추측하는 대로 구현되며 O(n)입니다.트리는 평균 O(log n)입니다.등등.이 유형들은 각각 적합합니다.__contains__big-O 특성을 갖는 방법.

테스트하는 컨테이너에 따라 다릅니다.이는 일반적으로 순서가 지정된 데이터 구조의 경우 선형, 순서가 지정되지 않은 데이터 구조의 경우 상수입니다.물론 트리의 일부 변형에 의해 지원될 수 있는 두 가지 유형(순서 또는 순서 없음)이 있습니다.

언급URL : https://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python