임의의 함수에 대해 BigO 표기법을 계산하는 방법을 스스로 가르치려고합니다. 교과서에서이 기능을 찾았습니다. 이 책은 함수가 O (n ² ) 라고 주장합니다 . 이것이 왜 그런지에 대한 설명을 제공하지만, 따르기 위해 고심하고 있습니다. 이것이 왜 그런지에 대한 수학을 보여줄 수 있을지 궁금합니다. 기본적으로, 나는 그것이 O (n ³ ) 보다 작은 것을 이해 하지만, O (n ² ) 에 독립적으로 착륙 할 수 없었습니다

우리가 A, B, C의 3 개의 시퀀스를 가지고 있다고 가정하자. 우리는 개별 시퀀스가 ​​중복 값을 포함하지 않는다고 가정하지만, 시퀀스 중 2 개 또는 3 개의 숫자가있을 수 있다고 가정 할 것이다. 3 방향 집합 분리 문제는 3 개의 시퀀스의 교집합이 비어 있는지, 즉 x x A, x ∈ B 및 x ∈ C와 같은 요소 x가 없는지 확인하는 것입니다.

우연히도 이것은 숙제 문제가 아닙니다. 그 배는 몇 년 전에 항해했습니다.

def disjoint(A, B, C):
        """Return True if there is no element common to all three lists."""
        for a in A:
            for b in B:
                if a == b: # only check C if we found match from A and B
                   for c in C:
                       if a == c # (and thus a == b == c)
                           return False # we found a common value
        return True # if we reach this, sets are disjoint

[편집] 교과서에 따르면 :

개선 된 버전에서 운이 좋으면 시간을 절약 할 수있는 것은 아닙니다. 분리에 대한 최악의 실행 시간은 O (n ² ) 라고 주장합니다 .

내가 따르기 어려운이 책의 설명은 다음과 같습니다.

전체 실행 시간을 설명하기 위해 각 코드 줄을 실행하는 데 소요 된 시간을 검사합니다. A를 통한 for 루프 관리에는 O (n) 시간이 필요합니다. B에 대한 for 루프 관리는 루프가 n 번 실행되므로 총 O (n ² ) 시간을 차지 합니다. 테스트 a == b는 O (n ² ) 번 평가 됩니다. 남은 시간은 일치하는 (a, b) 쌍의 수에 따라 다릅니다. 우리가 언급했듯이, 그러한 쌍은 최대 n 개이므로 C를 통한 루프 관리와 해당 루프의 본문 내 명령은 최대 O (n ² ) 시간을 사용합니다. 소요 된 총 시간은 O (n ² )입니다.

(그리고 적절한 신용을주기 위해 …)이 책은 : Michael T. Goodrich et al. 모두, Wiley Publishing, pg. 135

[편집] 정당화; 아래는 최적화 전의 코드입니다.

def disjoint1(A, B, C):
    """Return True if there is no element common to all three lists."""
       for a in A:
           for b in B:
               for c in C:
                   if a == b == c:
                        return False # we found a common value
return True # if we reach this, sets are disjoint

위에서 각 루프가 최대한 실행되어야하므로 이것이 O (n ³ ) 임을 분명히 알 수 있습니다 . 이 책은 단순화 된 예에서 (첫 번째로 주어진) 세 번째 루프는 O (n ² )의 복잡성이므로 복잡도 방정식은 k + O (n ² ) + O (n ² ) 로 간다. O (n ² ).

이것이 사실임을 증명할 수는 없지만 (문제), 독자는 단순화 된 알고리즘의 복잡성이 최소한 원래의 것보다 작다는 데 동의 할 수 있습니다.

[편집] 그리고 단순화 된 버전이 2 차임을 증명하려면 :

if __name__ == '__main__':
    for c in [100, 200, 300, 400, 500]:
        l1, l2, l3 = get_random(c), get_random(c), get_random(c)
        start = time.time()
        disjoint1(l1, l2, l3)
        print(time.time() - start)
        start = time.time()
        disjoint2(l1, l2, l3)
        print(time.time() - start)

수율 :

0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766

두 번째 차이가 같으므로 단순화 된 함수는 실제로 2 차입니다.

그리고 추가 증거 :

최악의 경우 (A = B! = C)를 가정하면

if __name__ == '__main__':
    for c in [10, 20, 30, 40, 50]:
        l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
        its1 = disjoint1(l1, l2, l3)
        its2 = disjoint2(l1, l2, l3)
        print(f"iterations1 = {its1}")
        print(f"iterations2 = {its2}")
        disjoint2(l1, l2, l3)

수율 :

iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500

두 번째 차이 검정을 사용하면 최악의 결과는 정확히 2 차입니다.

답변

def disjoint(A, B, C):
  AB = (a
        for a in A
        for b in B
        if a == b)
  ABC = (a
         for a in AB
         for c in C
         if a == c)
  for a in ABC:
    return False
  return True

for a in A:
  if a in B:  # might implicitly loop
    if a in C:  # might implicitly loop
      return False
return True

AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
  return False
return True

i = 0
def disjoint(A, B, C):
    global i
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    i+=1
                    print(i)
                    if a == c:
                        return False
    return True

print(disjoint([1] * 10, [1] * 10, [2] * 10))

...
...
...
993
994
995
996
997
998
999
1000
True

A: 1 2 3 4 5
B: 1 2 3 4 5

A: 1 2 3 4 5
B: 5 4 3 2 1