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

44

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 2 ). 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 3 ), ale nie mogłem samodzielnie wylądować na O (n 2 )

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

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 2 ), ponieważ ta pętla jest wykonywana n razy. Test a == b jest oceniany O (n 2 ) 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 2 ) czasu. Całkowity czas spędzony to O (n 2 ).

(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 3 ), 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 2 ), więc równanie złożoności przyjmuje postać k + O (n 2 ) + O (n 2 ), co ostatecznie daje O (n 2 ).

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:

wprowadź opis zdjęcia tutaj

[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.

wprowadź opis zdjęcia tutaj

SteveJ
źródło
6
Albo książka jest zła, albo twoja transkrypcja jest.
candied_orange
6
Nie. Źle jest źle, niezależnie od tego, jak dobrze cytowany. Albo wyjaśnij, dlaczego nie możemy tak po prostu założyć, jeśli pójdzie to w najgorszy możliwy sposób, kiedy robisz dużą analizę O, lub zaakceptuj otrzymane wyniki.
candied_orange
8
@candied_orange; Dodałem dodatkowe uzasadnienie do moich najlepszych możliwości - nie mój mocny kolor. Prosiłbym, abyś ponownie uwzględnił możliwość, że rzeczywiście możesz się mylić. Zrobiłeś słusznie swój punkt widzenia.
SteveJ
8
Liczby losowe nie są twoim najgorszym przypadkiem. To nic nie dowodzi.
Telastyn
7
ach w porządku. „Żadna sekwencja nie ma zduplikowanych wartości” zmienia najgorszy przypadek, ponieważ C może wywołać tylko raz na dowolną A. Przepraszam za frustrację - właśnie to dostaję za to, że jestem na
wymianie stosów

Odpowiedzi:

63

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
amon
źródło
4
Byłoby to o wiele wyraźniejsze, gdybyśmy po prostu zlikwidowali tę magiczną nzmienną i rozmawialiśmy o rzeczywistych zmiennych w grze.
Alexander
15
@code_dredd Nie, nie jest, nie ma bezpośredniego połączenia z kodem. Jest to abstrakcja, która przewiduje, że len(a) == len(b) == len(c)choć jest to prawda w kontekście analizy złożoności czasu, ma tendencję do mylenia rozmowy.
Alexander
10
Być może stwierdzenie, że kod OP ma najgorszą złożoność przypadku O (| A | • | B | + min (| A |, | B |) • | C |) jest wystarczające, aby wywołać zrozumienie?
Pablo H
3
Jeszcze jedna rzecz dotycząca testów czasowych: jak się dowiedziałeś, nie pomogły ci zrozumieć, co się dzieje. Z drugiej strony wydaje się, że dali ci dodatkową pewność w przeciwstawianiu się różnym błędnym, ale zdecydowanie stwierdzonym twierdzeniom, że książka była oczywiście błędna, więc to dobrze, iw tym przypadku twoje testowanie pokonało intuicyjne machanie ręką ... Aby zrozumieć, bardziej skutecznym sposobem testowania byłoby uruchomienie go w debuggerze z punktami przerwania (lub dodaniem wydruków wartości zmiennych) na wejściu każdej pętli.
sdenham
4
„Zauważ, że czasy nie są użytecznym wskaźnikiem złożoności algorytmicznej.” Myślę, że byłoby to bardziej dokładne, gdyby powiedział „rygorystyczny” lub „niezawodny” zamiast „użyteczny”.
Accumumulation
7

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)

RiaD
źródło
3

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.

Eric Duminil
źródło
Twój ostatni komentarz jest dość interesujący, nie pomyślałem o tym. Czy sugerujesz, że wynika to z faktu, że jesteś w stanie wykonać trzy operacje O (n) w szeregu?
SteveJ
2
Jeśli nie otrzymasz idealnego skrótu z co najmniej jednym segmentem na element wejściowy, nie możesz przetestować włączenia w O (1). Posortowany zestaw zwykle ma wyszukiwanie O (log n). Chyba że mówisz o średnim koszcie, ale nie o to chodzi. Jednak posiadanie zbalansowanego zestawu binarnego, który staje się twardy O (n log n), jest banalne.
Jan Dorniak
@JanDorniak: Doskonały komentarz, dzięki. Teraz jest to trochę dziwne: zignorowałem najgorszy przypadek key in dict, tak jak zrobili to autorzy. : - / W mojej obronie myślę, że o wiele trudniej jest znaleźć dyktand z kolizjami nkluczy i nskrótów niż po prostu stworzyć listę ze nzduplikowanymi wartościami. A w zestawie lub dykcie naprawdę nie może być żadnej zduplikowanej wartości. Zatem najgorszym i najgorszym przypadkiem jest rzeczywiście O (n²). Zaktualizuję moją odpowiedź.
Eric Duminil
2
@JanDorniak Myślę, że zbiory i dyktanda to tabele skrótów w pythonie, w przeciwieństwie do czerwono-czarnych drzew w C ++. Zatem absolutnie najgorszy przypadek jest gorszy, do 0 (n) dla wyszukiwania, ale średni przypadek to O (1). W przeciwieństwie do O (log n) dla C ++ wiki.python.org/moin/TimeComplexity . Biorąc pod uwagę, że jest to pytanie python i że dziedzina problemu prowadzi do wysokiego prawdopodobieństwa średniej wydajności sprawy, nie sądzę, aby twierdzenie O (1) było złe.
Baldrickk
3
Myślę, że widzę tu problem: kiedy autorzy mówią „założymy, że żadna pojedyncza sekwencja nie zawiera zduplikowanych wartości”, nie jest to krok w odpowiedzi na pytanie; jest to raczej warunek wstępny, w którym pytanie zostanie rozwiązane. Dla celów pedagogicznych zamienia to nieciekawy problem w taki, który podważa ludzkie intuicje na temat wielkiej-O - i wydaje się, że odniósł sukces, sądząc po liczbie ludzi, którzy zdecydowanie nalegali, że O (n²) musi się mylić. .. Ponadto, chociaż jest tutaj dyskusja, liczenie kroków w jednym przykładzie nie jest wyjaśnieniem.
sdenham
3

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

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

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

Mars
źródło
0

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.

Martin Maat
źródło
1
Kolejność elementów nie odgrywa tutaj roli. Istotnym wymogiem jest brak duplikatów; argumentem jest więc to, że pętle można przekształcić w dwie osobne O(n^2)pętle; co daje wynik ogólny O(n^2)(stałe są ignorowane).
AnoE
@AnoE Rzeczywiście kolejność elementów nie ma znaczenia. Właśnie to pokazuję.
Martin Maat
Widzę, co próbujesz zrobić, a to, co piszesz, nie jest złe, ale z perspektywy PO twoja odpowiedź pokazuje głównie, dlaczego dany ciąg myśli jest nieistotny; nie wyjaśnia, jak dojść do faktycznego rozwiązania. OP nie wydaje się wskazywać, że tak naprawdę uważa, że ​​ma to związek z porządkiem. Nie jest więc dla mnie jasne, w jaki sposób ta odpowiedź mogłaby pomóc OP.
AnoE
-1

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żą.

Douglas Winship
źródło
-3

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ź.

Eddie Ekpo
źródło
4
Książka jest całkiem jasna, że ​​O (n2) to najgorszy przypadek, a nie przeciętny przypadek.
SteveJ
Opis funkcji w postaci dużej notacji O zwykle stanowi jedynie górną granicę szybkości wzrostu funkcji. Z dużą notacją O związane jest kilka powiązanych notacji, wykorzystujących symbole o, Ω, ω i Θ, do opisania innych rodzajów granic asymptotycznych szybkości wzrostu. Wikipedia - Big O
candied_orange
5
„Jeśli książka nie zagłębiłaby się w szczegóły, prawdopodobnie dałaby ci średnią odpowiedź jako odpowiedź”. - Uhm, nie. Bez żadnych wyraźnych kwalifikacji zwykle mówimy o złożoności najgorszego przypadku w modelu pamięci RAM. Mówiąc o operacji na strukturach danych, a to wynika z kontekstu, to może mówić o amortyzacji najgorszy etap złożoność modelu RAM. Bez wyraźnej kwalifikacji na ogół nie będziemy rozmawiać o najlepszym przypadku, średnim przypadku, oczekiwanym przypadku, złożoności czasowej ani żadnym innym modelu oprócz pamięci RAM.
Jörg W Mittag