[PYTHON] 교차로 복잡성

교차로 복잡성

파이썬에서는 두 세트의 교집합을 얻을 수 있습니다.

>>> s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> s2 = {0, 3, 5, 6, 10}
>>> s1 & s2
set([3, 5, 6])
>>> s1.intersection(s2)
set([3, 5, 6])

누구나이 교차 (&) 알고리즘의 복잡성을 알고 있습니까?

편집 : 또한, 파이썬 세트 뒤에있는 데이터 구조를 아는 사람 있습니까?

해결법

1. ==============================

   1.그 답은 검색 엔진 쿼리 인 것처럼 보입니다. python.org의 Time Complexity 페이지에 직접 링크를 사용할 수도 있습니다. 간략한 요약 :

   그 답은 검색 엔진 쿼리 인 것처럼 보입니다. python.org의 Time Complexity 페이지에 직접 링크를 사용할 수도 있습니다. 간략한 요약 :

   Average:     O(min(len(s), len(t))
   Worst case:  O(len(s) * len(t))
   

   편집 : 레이몬드는 아래 지적, "최악의 시나리오"가 발생할 가능성이 없습니다. 원래 철저히 조사 했었습니다. 아래 토론에 대한 컨텍스트를 제공하기 위해 남겨 두었습니다.하지만 저는 레이몬드가 옳다고 생각합니다.

2. ==============================

   2.교차 알고리즘은 항상 O (min (len (s1), len (s2)))에서 실행됩니다.

   교차 알고리즘은 항상 O (min (len (s1), len (s2)))에서 실행됩니다.

   순수한 파이썬에서는 다음과 같이 보입니다.

       def intersection(self, other):
           if len(self) <= len(other):
               little, big = self, other
           else:
               little, big = other, self
           result = set()
           for elem in little:
               if elem in big:
                   result.add(elem)
           return result
   

   [추가 편집에서의 질문에 대한 답변] 집합 뒤에있는 데이터 구조는 해시 테이블입니다.

3. ==============================

   3.다음 두 가지 크기 집합 m, n의 교집합은 다음과 같은 방법으로 O (max {m, n} * log (min {m, n})) m << n이라고 가정합니다.

   다음 두 가지 크기 집합 m, n의 교집합은 다음과 같은 방법으로 O (max {m, n} * log (min {m, n})) m << n이라고 가정합니다.

   1. Represent the two sets as list/array(something sortable)
   2. Sort the **smaller** list/array (cost: m*logm)
   3. Do until all elements in the bigger list has been checked:
       3.1 Sort the next **m** items on the bigger list(cost: m*logm)
       3.2 With a single pass compare the smaller list and the m items you just sorted and take the ones that appear in both of them(cost: m)
   4. Return the new set
   

   3 단계의 루프는 n / m 반복에 대해 실행되며 각 반복에는 O (m * logm)이 필요하므로 m << n에 대해 O (nlogm)의 시간 복잡성을 갖습니다.

   나는 그것이 존재하는 최고의 하한이라고 생각한다.

from https://stackoverflow.com/questions/8102478/intersection-complexity by cc-by-sa and MIT license