Dlaczego najgorszy przypadek dla tej funkcji O (n ^ 2)?

Próbuję nauczyć się, jak obliczyć notację BigO dla dowolnej funkcji. Znalazłem tę funkcję w podręczniku. Książka potwierdza, że ​​funkcją jest O (n ² ). To wyjaśnia, dlaczego tak jest, ale staram się podążać. Zastanawiam się, czy ktoś mógłby mi pokazać matematykę, dlaczego tak jest. Zasadniczo rozumiem, że jest to coś mniejszego niż O (n ³ ), ale nie mogłem samodzielnie wylądować na O (n ² )

Załóżmy, że podano nam trzy sekwencje liczb: A, B i C. Zakładamy, że żadna pojedyncza sekwencja nie zawiera zduplikowanych wartości, ale mogą istnieć pewne liczby, które występują w dwóch lub trzech sekwencjach. Problem rozłączności zestawu trójdrożnego polega na określeniu, czy przecięcie trzech sekwencji jest puste, a mianowicie, czy nie ma takiego elementu x, że x ∈ A, x ∈ B i x ∈ C.

Nawiasem mówiąc, nie jest to dla mnie problem w odrabianiu prac domowych - ten statek wypłynął lata temu:), tylko ja próbuję stać się mądrzejszy.

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

[Edytuj] Zgodnie z podręcznikiem:

W ulepszonej wersji nie tylko oszczędzamy czas, jeśli mamy szczęście. Twierdzimy, że najgorszym przypadkiem dla rozłączności jest O (n ² ).

Wyjaśnienie książki, do którego staram się podążać, jest następujące:

Aby uwzględnić całkowity czas działania, sprawdzamy czas poświęcony na wykonanie każdego wiersza kodu. Zarządzanie pętlą for przez A wymaga czasu O (n). Zarządzanie pętlą for przez B stanowi łącznie O (n ² ), ponieważ ta pętla jest wykonywana n razy. Test a == b jest oceniany O (n ² ) razy. Reszta czasu zależy od liczby pasujących par (a, b). Jak zauważyliśmy, istnieje co najwyżej n takich par, a zatem zarządzanie pętlą nad C i polecenia w ciele tej pętli używają maksymalnie O (n ² ) czasu. Całkowity czas spędzony to O (n ² ).

(I przyznać należny kredyt ...) Książka jest: Struktury danych i algorytmy w Pythonie autorstwa Michaela T. Goodricha i in. wszystkie, Wiley Publishing, str. 135

[Edytuj] Uzasadnienie; Poniżej znajduje się kod przed optymalizacją:

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

Na powyższym widać wyraźnie, że jest to O (n ³ ), ponieważ każda pętla musi przebiegać w pełni. Książka twierdzi, że w uproszczonym przykładzie (podanym jako pierwszy) trzecia pętla jest tylko złożonością O (n ² ), więc równanie złożoności przyjmuje postać k + O (n ² ) + O (n ² ), co ostatecznie daje O (n ² ).

Chociaż nie mogę udowodnić, że tak jest (stąd pytanie), czytelnik może zgodzić się, że złożoność uproszczonego algorytmu jest co najmniej mniejsza niż w oryginale.

[Edytuj] Aby udowodnić, że uproszczona wersja jest kwadratowa:

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)

Wydajność:

0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766

Ponieważ druga różnica jest równa, funkcja uproszczona jest rzeczywiście kwadratowa:

[Edytuj] A jeszcze więcej dowodów:

Jeśli założę najgorszy przypadek (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)

daje:

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

W drugim teście różnic najgorszy wynik jest dokładnie kwadratowy.

Książka jest rzeczywiście poprawna i stanowi dobry argument. Należy pamiętać, że czasy nie są wiarygodnym wskaźnikiem złożoności algorytmicznej. Czasy mogą uwzględniać tylko specjalny rozkład danych lub przypadki testowe mogą być zbyt małe: złożoność algorytmu opisuje tylko, jak zużycie zasobów lub środowisko wykonawcze skaluje się powyżej pewnego odpowiednio dużego rozmiaru wejściowego.

Książka argumentuje, że złożoność wynosi O (n²), ponieważ if a == bgałąź jest wprowadzana co najwyżej n razy. Nie jest to oczywiste, ponieważ pętle są nadal zapisywane jako zagnieżdżone. Bardziej oczywiste jest, jeśli go wyodrębnimy:

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

Ten wariant wykorzystuje generatory do przedstawienia wyników pośrednich.

• W generatorze ABbędziemy mieć co najwyżej n elementów (ze względu na gwarancję, że listy wejściowe nie będą zawierać duplikatów), a wytwarzanie generatora wymaga złożoności O (n²).
• Wytworzenie generatora ABCobejmuje pętlę nad generatorem ABo długości n i większej Co długości n , tak że jego złożoność algorytmiczna wynosi również O (n²).
• Operacje te nie są zagnieżdżone, ale zachodzą niezależnie, więc całkowita złożoność wynosi O (n² + n²) = O (n²).

Ponieważ pary list wejściowych można sprawdzać sekwencyjnie, z tego wynika, że ​​określenie, czy dowolna liczba list jest rozłączna, może być wykonane w czasie O (n²).

Ta analiza jest nieprecyzyjna, ponieważ zakłada, że ​​wszystkie listy mają tę samą długość. Możemy powiedzieć bardziej precyzyjnie, że ABma co najwyżej długość min (| A |, | B |), a wytwarzanie go ma złożoność O (| A | • | B |). Produkcja ABCma złożoność O (min (| A |, | B |) • | C |). Całkowita złożoność zależy wówczas od sposobu uporządkowania list wejściowych. Z | A | ≤ | B | ≤ | C | otrzymujemy całkowitą najgorszą złożoność O (| A | • | C |).

Zauważ, że wygrane wydajnościowe są możliwe, jeśli kontenery wejściowe pozwalają na szybkie testy członkostwa zamiast konieczności iteracji wszystkich elementów. Może tak być w przypadku ich sortowania, aby można było przeprowadzić wyszukiwanie binarne, lub gdy są zestawami skrótów. Bez wyraźnych zagnieżdżonych pętli wyglądałoby to następująco:

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

lub w wersji opartej na generatorze:

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

Zauważ, że jeśli wszystkie elementy są różne na każdej założonej liście, możesz iterować C tylko raz dla każdego elementu w A (jeśli element w B jest równy). Zatem wewnętrzna pętla jest sumą O (n ^ 2)

Zakładamy, że żadna pojedyncza sekwencja nie zawiera duplikatu.

jest bardzo ważną informacją.

W przeciwnym razie najgorszym przypadkiem zoptymalizowanej wersji nadal będzie O (n³), gdy A i B są równe i zawierają jeden element powielony n razy:

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))

które wyjścia:

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

Zasadniczo autorzy zakładają, że najgorszy przypadek O (n³) nie powinien się zdarzyć (dlaczego?) I „udowadniają”, że najgorszym przypadkiem jest teraz O (n²).

Rzeczywistą optymalizacją byłoby użycie zbiorów lub dykt w celu przetestowania włączenia w O (1). W takim przypadku disjointbyłoby O (n) dla każdego wejścia.

Aby umieścić rzeczy w terminach używanych w książce:

Myślę, że nie masz problemu ze zrozumieniem, że sprawdzenie na a == bnajgorszy przypadek O (n ² ).

Teraz w najgorszym przypadku do trzeciej pętli, każda aw Ama odpowiednika w B, więc trzecia pętla będzie wywoływana za każdym razem. W przypadku, agdy nie istnieje C, przejdzie przez cały Czestaw.

Innymi słowy, jest to 1 raz za każdym razem ai 1 raz za każdym razem c, lub n * n. O (n ² )

Jest więc O (n ² ) + O (n ² ), na które wskazuje twoja książka.

Sztuczka zoptymalizowanej metody polega na skracaniu zakrętów. Tylko jeśli a i b pasują, c będzie warte zobaczenia. Teraz możesz pomyśleć, że w najgorszym przypadku nadal będziesz musiał ocenić każde c. To nie jest prawda.

Prawdopodobnie najgorszym przypadkiem jest to, że każde sprawdzenie a == b powoduje przejechanie C, ponieważ każde sprawdzenie a == b zwraca dopasowanie. Nie jest to jednak możliwe, ponieważ warunki tego są sprzeczne. Aby to zadziałało, potrzebujesz A i B, które zawierają te same wartości. Można je uporządkować inaczej, ale każda wartość w A musiałaby mieć pasującą wartość w B.

Teraz jest kicker. Nie ma sposobu na uporządkowanie tych wartości, aby dla każdego a musiałbyś ocenić wszystkie b, zanim znajdziesz swoje dopasowanie.

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

Odbyłoby się to natychmiast, ponieważ pasujące 1 są pierwszym elementem w obu seriach. Co powiesz na

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

To działałoby przy pierwszym przejechaniu przez A: tylko ostatni element w B dałby trafienie. Ale następna iteracja nad A musiałaby już być szybsza, ponieważ ostatnie miejsce w B jest już zajęte przez 1. I tym razem zajęłoby to tylko cztery iteracje. Z każdą kolejną iteracją staje się to trochę lepsze.

Teraz nie jestem matematykiem, więc nie mogę udowodnić, że skończy się na O (n2), ale czuję to na moich chodakach.

Na początku był zaskoczony, ale odpowiedź Amona jest naprawdę pomocna. Chcę zobaczyć, czy mogę zrobić naprawdę zwięzłą wersję:

Dla danej wartości ain Afunkcja porównuje się az każdą możliwą wartością bin Bi robi to tylko raz. Dla danego adziała a == bdokładnie tak samo n.

Bnie zawiera żadnych duplikatów (żadna z list nie zawiera), więc dla danego abędzie maksymalnie jedno dopasowanie. (To jest klucz). Tam, gdzie jest dopasowanie, azostanie porównany z każdym możliwym c, co oznacza, że a == cjest przeprowadzany dokładnie n razy. Gdzie nie ma dopasowania, a == cwcale się nie zdarza.

Tak więc dla danego aistnieją albo nporównania, albo 2nporównania. Dzieje się tak dla każdego a, więc najlepszym możliwym przypadkiem jest (n²), a najgorszym jest (2n²).

TLDR: każda wartość ajest porównywana z każdej wartości bi wobec każdej wartości c, ale nie przed każdym połączeniu z ba c. Oba problemy sumują się, ale się nie mnożą.

Pomyśl o tym w ten sposób, niektóre liczby mogą występować w dwóch lub trzech sekwencjach, ale przeciętny przypadek tego jest taki, że dla każdego elementu w zestawie A wyczerpujące wyszukiwanie jest wykonywane wb. Gwarantuje się, że każdy element w zestawie A będzie iterowany, ale oznacza to, że mniej niż połowa elementów w zestawie b zostanie iterowana.

Gdy elementy zestawu b są iterowane, iteracja ma miejsce, jeśli występuje dopasowanie. oznacza to, że średni przypadek dla tej funkcji rozłącznej wynosi O (n2), ale absolutnie najgorszym przypadkiem może być O (n3). Jeśli książka nie zagłębiłaby się w szczegóły, prawdopodobnie podałaby średnią odpowiedź jako odpowiedź.