Jakie są funkcje asymptotyczne? Czym w ogóle jest asymptota?
Biorąc pod uwagę funkcję f (n), która opisuje ilość zasobów (czas procesora, pamięci RAM, miejsca na dysku itp.) Zużywanych przez algorytm po zastosowaniu do danych wejściowych o rozmiarze n , definiujemy do trzech asymptotycznych notacji opisujących jego wydajność dla duży n .
Asymptota (lub funkcja asymptotyczna) to po prostu jakaś inna funkcja (lub relacja) g (n), do której f (n) zbliża się coraz bardziej, gdy n rośnie i rośnie, ale nigdy się nie osiąga. Zaletą mówienia o funkcjach asymptotycznych jest to, że ogólnie są one o wiele prostsze w mówieniu, nawet jeśli wyrażenie dla f (n) jest wyjątkowo skomplikowane. Funkcje asymptotyczne są używane jako część notacji granicznych, które ograniczają f (n) powyżej lub poniżej.
(Uwaga: w zastosowanym tutaj znaczeniu funkcje asymptotyczne są zbliżone do pierwotnej funkcji po skorygowaniu o pewien stały niezerowy współczynnik, ponieważ wszystkie trzy notacje duże-O / Θ / Ω nie uwzględniają tych stałych czynników przy ich rozważaniu.)
Jakie są trzy asymptotyczne notacje graniczne i czym się różnią?
Wszystkie trzy notacje są używane w następujący sposób:
f (n) = O (g (n))
gdzie f (n) jest funkcją będącą przedmiotem zainteresowania, a g (n) jest jakąś inną funkcją asymptotyczną , którą próbujesz aproksymować f (n) . Nie należy tego traktować jako równości w ścisłym znaczeniu, ale formalne stwierdzenie, jak szybko rośnie f (n) w stosunku do n w porównaniu do g (n) , gdy n staje się duże. Puryści często używają alternatywnej notacji f (n) ∈ O (g (n)), aby podkreślić, że symbol O (g (n)) jest naprawdę całą rodziną funkcji, które mają wspólną stopę wzrostu.
Notacja Big-ϴ (Theta) stwierdza równość wzrostu f (n) do stałego współczynnika (więcej na ten temat później). Zachowuje się podobnie jak =operator w przypadku wskaźników wzrostu.
Notacja Big-O opisuje górną granicę wzrostu f (n) . Zachowuje się podobnie jak ≤operator w przypadku wskaźników wzrostu.
Notacja Big-Ω (Omega) opisuje niższe ograniczenie wzrostu f (n) . Zachowuje się podobnie jak ≥operator w przypadku wskaźników wzrostu.
Istnieje wiele innych asymptotycznych notacji , ale nie występują one tak często w literaturze informatycznej.
Notacje Big-O i ich podobne są często sposobem na porównanie złożoności czasowej .
Czym jest złożoność czasu?
Złożoność czasu to fantazyjny termin określający czas T (n) potrzebny do wykonania algorytmu w zależności od jego wielkości wejściowej n . Można to zmierzyć ilością czasu rzeczywistego (np. Sekund), liczbą instrukcji procesora itp. Zazwyczaj zakłada się, że algorytm będzie działał na twoim codziennym komputerze z architekturą von Neumanna . Ale oczywiście możesz wykorzystać złożoność czasu, aby porozmawiać o bardziej egzotycznych systemach komputerowych, w których może być inaczej!
Często mówi się o złożoności przestrzeni za pomocą notacji Big-O. Złożoność przestrzeni to ilość pamięci (pamięci) wymagana do ukończenia algorytmu, którą może być pamięć RAM, dysk itp.
Może się zdarzyć, że jeden algorytm jest wolniejszy, ale zużywa mniej pamięci, podczas gdy inny jest szybszy, ale zużywa więcej pamięci. Każdy może być bardziej odpowiedni w różnych okolicznościach, jeśli zasoby są ograniczone w inny sposób. Na przykład wbudowany procesor może mieć ograniczoną pamięć i faworyzować wolniejszy algorytm, podczas gdy serwer w centrum danych może mieć dużą ilość pamięci i faworyzować szybszy algorytm.
Obliczanie Big-ϴ
Obliczanie Big ϴ algorytmu jest tematem, który może wypełnić mały podręcznik lub około pół semestru zajęć licencjackich: ta sekcja obejmie podstawy.
Biorąc pod uwagę funkcję f (n) w pseudokodzie:
int f(n) {
int x = 0;
for (int i = 1 to n) {
for (int j = 1 to n) {
++x;
}
}
return x;
}
Jaka jest złożoność czasu?
Zewnętrzna pętla działa n razy. Za każdym razem, gdy działa zewnętrzna pętla, wewnętrzna pętla działa n razy. To stawia czas działania na T (n) = n 2 .
Rozważ drugą funkcję:
int g(n) {
int x = 0;
for (int k = 1 to 2) {
for (int i = 1 to n) {
for (int j = 1 to n) {
++x;
}
}
}
return x;
}
Zewnętrzna pętla działa dwa razy. Pętla środkowa działa n razy. Za każdym razem, gdy działa środkowa pętla, wewnętrzna pętla działa n razy. To stawia czas działania na T (n) = 2n 2 .
Teraz pytanie brzmi: jaki jest asymptotyczny czas działania obu funkcji?
Aby to obliczyć, wykonujemy dwa kroki:
- Usuń stałe. Ponieważ algorytmy rosną w czasie z powodu danych wejściowych, inne terminy dominują w czasie wykonywania, przez co stają się nieważne.
- Usuń wszystkie oprócz największego terminu. Gdy n idzie w nieskończoność, n 2 szybko wyprzedza n .
Kluczem tutaj jest skupienie się na dominujących warunkach i uproszczenie tych warunków .
T (n) = n 2 ∈ ϴ (n 2 )
T (n) = 2n 2 ∈ ϴ (n 2 )
Jeśli mamy inny algorytm z wieloma terminami, uprościlibyśmy go, stosując te same reguły:
T (n) = 2n 2 + 4n + 7 ∈ ϴ (n 2 )
Kluczem do wszystkich tych algorytmów jest to, że skupiamy się na największych terminach i usuwamy stałe . Nie patrzymy na rzeczywisty czas działania, ale na względną złożoność .
Obliczanie Big-Ω i Big-O
Po pierwsze, należy pamiętać, że w literaturze nieformalnej „Big-O” jest często traktowany jako synonim Big-Θ, być może dlatego, że greckie litery są trudne do pisania. Więc jeśli ktoś nieoczekiwanie poprosi cię o Big-O algorytmu, prawdopodobnie chce jego Big-Θ.
Teraz, jeśli naprawdę chcesz obliczyć Big-Ω i Big-O w zdefiniowanych wcześniej formalnych zmysłach, masz poważny problem: istnieje nieskończenie wiele opisów Big-Ω i Big-O dla dowolnej funkcji! To tak, jakby zapytać, jakie są liczby mniejsze lub równe 42. Istnieje wiele możliwości.
W przypadku algorytmu z T (n) ∈ ϴ (n 2 ) dowolne z poniższych są formalnie poprawnymi instrukcjami do złożenia:
- T (n) ∈ O (n 2 )
- T (n) ∈ O (n 3 )
- T (n) ∈ O (n 5 )
- T (n) ∈ O (n 12345 × e n )
- T (n) ∈ Ω (n 2 )
- T (n) ∈ Ω (n)
- T (n) ∈ Ω (log (n))
- T (n) ∈ Ω (log (log (n)))
- T (n) ∈ Ω (1)
Ale błędne jest podanie T (n) ∈ O (n) lub T (n) ∈ Ω (n 3 ) .
Co to jest względna złożoność? Jakie są klasy algorytmów?
Jeśli porównamy dwa różne algorytmy, ich złożoność w miarę wprowadzania danych do nieskończoności zwykle wzrośnie. Jeśli spojrzymy na różne typy algorytmów, mogą one pozostać względnie takie same (na przykład, różnią się stałym współczynnikiem) lub mogą się znacznie różnić. Jest to powód przeprowadzenia analizy Big-O: w celu ustalenia, czy algorytm będzie działał rozsądnie przy dużych danych wejściowych.
Klasy algorytmów dzielą się następująco:
Θ (1) - stała. Na przykład wybranie pierwszego numeru z listy zawsze zajmuje tyle samo czasu.
Θ (n) - liniowy. Na przykład iteracja listy zawsze zajmuje czas proporcjonalny do wielkości listy, n .
Θ (log (n)) - logarytmiczny (podstawa zwykle nie ma znaczenia). Przykładami są algorytmy dzielące przestrzeń wejściową na każdym kroku, takie jak wyszukiwanie binarne.
Θ (n × log (n)) - logarytmiczny razy liniowy („linearithmic”). Algorytmy te zwykle dzielą i zdobywają ( log (n) ), a jednocześnie iterują ( n ) wszystkie dane wejściowe. Wiele popularnych algorytmów sortowania (sortowanie scalone, Timsort) należy do tej kategorii.
Θ (n m ) - wielomian ( n podniesiony do dowolnej stałej m ). Jest to bardzo powszechna klasa złożoności, często spotykana w zagnieżdżonych pętlach.
Θ (m n ) - wykładniczy (dowolna stała m podniesiona do n ). Wiele algorytmów rekurencyjnych i graficznych należy do tej kategorii.
Θ (n!) - silnia. Niektóre algorytmy grafowe i kombinatoryczne są złożonością czynnikową.
Czy to ma coś wspólnego z najlepszym / przeciętnym / najgorszym przypadkiem?
Nie. Big-O i jego rodzina zapisów mówią o określonej funkcji matematycznej . Są to narzędzia matematyczne stosowane w celu scharakteryzowania wydajności algorytmów, ale pojęcie najlepszego / przeciętnego / najgorszego przypadku nie ma związku z opisaną tutaj teorią tempa wzrostu.
Aby mówić o Big-O algorytmu, należy zobowiązać się do określonego modelu matematycznego algorytmu z dokładnie jednym parametrem n, który ma opisywać „wielkość” danych wejściowych, w jakimkolwiek sensie jest to użyteczne. Ale w prawdziwym świecie nakłady mają znacznie więcej struktury niż tylko ich długości. Jeśli był to algorytm sortowania, mogę karmić w struny "abcdef", "fedcba"albo "dbafce". Wszystkie mają długość 6, ale jeden jest już posortowany, jeden jest odwrócony, a ostatni to tylko losowa zbieranina. Niektóre algorytmy sortowania (np. Timsort) działają lepiej, jeśli dane wejściowe są już posortowane. Ale jak włączyć tę niejednorodność do modelu matematycznego?
Typowym podejściem jest po prostu założenie, że dane wejściowe pochodzą z jakiegoś losowego rozkładu probabilistycznego. Następnie uśredniasz złożoność algorytmu na wszystkich wejściach o długości n. Daje to model algorytmu o średniej złożoności przypadków . Odtąd możesz używać notacji Big-O / Θ / Ω jak zwykle, aby opisać średnie zachowanie przypadku.
Ale jeśli obawiasz się ataków typu „odmowa usługi”, być może będziesz musiał być bardziej pesymistyczny. W takim przypadku bezpieczniej jest założyć, że jedynymi danymi wejściowymi są te, które powodują najwięcej żalu w algorytmie. To daje najgorszy model złożoności algorytmu. Następnie możesz mówić o Big-O / Θ / Ω itp . Modelu najgorszego przypadku .
Podobnie, możesz również skupić swoje zainteresowanie wyłącznie na danych wejściowych, z którymi Twój algorytm ma najmniej kłopotów, aby znaleźć najlepszy model, a następnie spojrzeć na Big-O / Θ / Ω itp.