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:
[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.
Odpowiedzi:
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 == b
gałąź 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:Ten wariant wykorzystuje generatory do przedstawienia wyników pośrednich.
AB
bę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²).ABC
obejmuje pętlę nad generatoremAB
o długości n i większejC
o długości n , tak że jego złożoność algorytmiczna wynosi również 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
AB
ma co najwyżej długość min (| A |, | B |), a wytwarzanie go ma złożoność O (| A | • | B |). ProdukcjaABC
ma 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:
lub w wersji opartej na generatorze:
źródło
n
zmienną i rozmawialiśmy o rzeczywistych zmiennych w grze.len(a) == len(b) == len(c)
choć jest to prawda w kontekście analizy złożoności czasu, ma tendencję do mylenia rozmowy.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)
źródło
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:
które wyjścia:
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
disjoint
byłoby O (n) dla każdego wejścia.źródło
key in dict
, tak jak zrobili to autorzy. : - / W mojej obronie myślę, że o wiele trudniej jest znaleźć dyktand z kolizjamin
kluczy in
skrótów niż po prostu stworzyć listę zen
zduplikowanymi 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ź.Aby umieścić rzeczy w terminach używanych w książce:
Myślę, że nie masz problemu ze zrozumieniem, że sprawdzenie na
a == b
najgorszy przypadek O (n 2 ).Teraz w najgorszym przypadku do trzeciej pętli, każda
a
wA
ma odpowiednika wB
, więc trzecia pętla będzie wywoływana za każdym razem. W przypadku,a
gdy nie istniejeC
, przejdzie przez całyC
zestaw.Innymi słowy, jest to 1 raz za każdym razem
a
i 1 raz za każdym razemc
, lub n * n. O (n 2 )Jest więc O (n 2 ) + O (n 2 ), na które wskazuje twoja książka.
źródło
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.
Odbyłoby się to natychmiast, ponieważ pasujące 1 są pierwszym elementem w obu seriach. Co powiesz na
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.
źródło
O(n^2)
pętle; co daje wynik ogólnyO(n^2)
(stałe są ignorowane).Na początku był zaskoczony, ale odpowiedź Amona jest naprawdę pomocna. Chcę zobaczyć, czy mogę zrobić naprawdę zwięzłą wersję:
Dla danej wartości
a
inA
funkcja porównuje sięa
z każdą możliwą wartościąb
inB
i robi to tylko raz. Dla danegoa
działaa == b
dokładnie tak samon
.B
nie zawiera żadnych duplikatów (żadna z list nie zawiera), więc dla danegoa
będzie maksymalnie jedno dopasowanie. (To jest klucz). Tam, gdzie jest dopasowanie,a
zostanie porównany z każdym możliwymc
, co oznacza, żea == c
jest przeprowadzany dokładnie n razy. Gdzie nie ma dopasowania,a == c
wcale się nie zdarza.Tak więc dla danego
a
istnieją albon
porównania, albo2n
porównania. Dzieje się tak dla każdegoa
, więc najlepszym możliwym przypadkiem jest (n²), a najgorszym jest (2n²).TLDR: każda wartość
a
jest porównywana z każdej wartościb
i wobec każdej wartościc
, ale nie przed każdym połączeniu zb
ac
. Oba problemy sumują się, ale się nie mnożą.źródło
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ź.
źródło