algorithm
Notacja Big-O
Szukaj…
Uwagi
Definicja
Notacja Big-O jest w sercu notacją matematyczną, używaną do porównywania szybkości zbieżności funkcji. Niech n -> f(n) i n -> g(n) będą funkcjami zdefiniowanymi na liczbach naturalnych. Mówimy wtedy, że f = O(g) wtedy i tylko wtedy, gdy f(n)/g(n) jest ograniczone, gdy n zbliża się do nieskończoności. Innymi słowy, f = O(g) wtedy i tylko wtedy, gdy istnieje stała A, taka, że dla wszystkich n, f(n)/g(n) <= A
W rzeczywistości zakres notacji Big-O jest nieco szerszy w matematyce, ale dla uproszczenia zawęziłem ją do tego, co jest stosowane w analizie złożoności algorytmu: funkcji zdefiniowanych w naturals, które mają niezerowe wartości, i przypadku n wzrostu do nieskończoności.
Co to znaczy ?
Weźmy przypadek f(n) = 100n^2 + 10n + 1 g(n) = n^2 . Jest całkiem jasne, że obie te funkcje dążą do nieskończoności, podobnie jak n dąży do nieskończoności. Ale czasami znajomość limitu nie wystarcza, a my chcemy również wiedzieć, z jaką prędkością funkcje zbliżają się do granicy. Pojęcia takie jak Big-O pomagają porównywać i klasyfikować funkcje według szybkości konwergencji.
Sprawdźmy, czy f = O(g) , stosując definicję. Mamy f(n)/g(n) = 100 + 10/n + 1/n^2 . Od 10/n to 10, gdy n oznacza 1, a zmniejsza się, a od 1/n^2 oznacza 1 gdy n oznacza 1, a także zmniejszenie mamy f f(n)/g(n) <= 100 + 10 + 1 = 111 . Definicja jest spełniona, ponieważ znaleźliśmy granicę f(n)/g(n) (111), a więc f = O(g) (mówimy, że f jest Big-O z n^2 ).
Oznacza to, że f dąży do nieskończoności z mniej więcej taką samą prędkością jak g. Może to wydawać się dziwną rzeczą do powiedzenia, ponieważ odkryliśmy, że f jest co najwyżej 111 razy większe niż g, lub innymi słowy, gdy g rośnie o 1, f rośnie o maksymalnie 111. Może się wydawać, że rośnie 111 razy szybszy to nie „w przybliżeniu ta sama prędkość”. I rzeczywiście notacja Big-O nie jest bardzo dokładnym sposobem klasyfikowania prędkości zbieżności funkcji, dlatego w matematyce stosujemy relację równoważności, gdy chcemy dokładnego oszacowania prędkości. Ale do celów rozdzielania algorytmów w dużych klasach prędkości wystarczy Big-O. Nie musimy rozdzielać funkcji, które rosną ustaloną liczbę razy szybciej od siebie, ale tylko funkcje, które rosną nieskończenie szybciej od siebie. Na przykład, jeśli weźmiemy h(n) = n^2*log(n) , widzimy, że h(n)/g(n) = log(n) który dąży do nieskończoności za pomocą n, więc h nie jest O (n ^ 2), ponieważ h rośnie nieskończenie szybciej niż n ^ 2.
Teraz muszę zrobić dodatkową notatkę: być może zauważyłeś, że jeśli f = O(g) g = O(h) , to f = O(h) . Na przykład w naszym przypadku mamy f = O(n^3) f = O(n^4) ... W analizie złożoności algorytmu często mówimy f = O(g) co oznacza, że f = O(g) i g = O(f) , co może być rozumiane jako "g jest najmniejsza Big-o i f". W matematyce mówimy, że takie funkcje są dla siebie Big-Thetas.
Jak to jest używane ?
Porównując wydajność algorytmu, interesuje nas liczba operacji, które wykonuje algorytm. Nazywa się to złożonością czasową . W tym modelu uważamy, że każda podstawowa operacja (dodawanie, mnożenie, porównanie, przypisanie itp.) Zajmuje określoną ilość czasu i liczymy liczbę takich operacji. Zwykle możemy wyrazić ten numer jako funkcję wielkości wejścia, które nazywamy n. I niestety liczba ta zwykle rośnie do nieskończoności z n (jeśli nie, mówimy, że algorytmem jest O (1)). Nasze algorytmy dzielimy na duże klasy prędkości zdefiniowane przez Big-O: kiedy mówimy o algorytmie „O (n ^ 2)”, mamy na myśli, że liczba wykonywanych przez niego operacji, wyrażona jako funkcja n, wynosi O ( n ^ 2). Oznacza to, że nasz algorytm jest w przybliżeniu tak szybki jak algorytm, który wykonałby szereg operacji równych kwadratowi wielkości jego danych wejściowych lub szybciej . Część „lub szybsza” istnieje, ponieważ użyłem Big-O zamiast Big-Theta, ale zwykle ludzie mówią, że Big-O oznacza Big-Theta.
Podczas liczenia operacji zwykle bierzemy pod uwagę najgorszy przypadek: na przykład, jeśli mamy pętlę, która może działać najwyżej n razy i zawiera 5 operacji, liczba operacji, które liczymy, wynosi 5n. Można również wziąć pod uwagę średnią złożoność przypadku.
Szybka uwaga: szybki algorytm to taki, który wykonuje kilka operacji, więc jeśli liczba operacji rośnie do nieskończoności szybciej , algorytm jest wolniejszy : O (n) jest lepsze niż O (n ^ 2).
Czasami interesuje nas również złożoność przestrzeni naszego algorytmu. W tym celu bierzemy pod uwagę liczbę bajtów zajętych przez algorytm jako funkcję wielkości danych wejściowych i używamy Big-O w ten sam sposób.
Prosta pętla
Poniższa funkcja znajduje maksymalny element w tablicy:
int find_max(const int *array, size_t len) {
int max = INT_MIN;
for (size_t i = 0; i < len; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
Rozmiar wejściowy to rozmiar tablicy, którą nazwałem len w kodzie.
Policzmy operacje.
int max = INT_MIN;
size_t i = 0;
Te dwa zadania są wykonywane tylko raz, więc są to 2 operacje. Zapętlone operacje to:
if (max < array[i])
i++;
max = array[i]
Ponieważ w pętli są 3 operacje, a pętla jest wykonywana n razy, dodajemy 3n do naszych już istniejących 2 operacji, aby uzyskać 3n + 2 . Nasza funkcja potrzebuje więc operacji 3n + 2 , aby znaleźć maksimum (jej złożoność wynosi 3n + 2 ). Jest to wielomian, w którym najszybciej rosnącym terminem jest współczynnik n, więc jest to O (n).
Prawdopodobnie zauważyłeś, że „operacja” nie jest zbyt dobrze zdefiniowana. Na przykład powiedziałem, że if (max < array[i]) to jedna operacja, ale w zależności od architektury, instrukcja ta może się skompilować na przykład z trzema instrukcjami: jednym odczytem pamięci, jednym porównaniem i jedną gałęzią. Rozważyłem również wszystkie operacje jako takie same, chociaż na przykład operacje pamięci będą wolniejsze niż inne, a ich wydajność będzie się bardzo różnić na przykład z powodu efektów pamięci podręcznej. Całkowicie zignorowałem również instrukcję return, fakt, że dla funkcji zostanie utworzona ramka itp. Ostatecznie nie ma to znaczenia dla analizy złożoności, ponieważ bez względu na sposób liczenia operacji, zmienia ona tylko współczynnik współczynnika n i stałej, więc wynikiem będzie nadal O (n). Złożoność pokazuje, jak algorytm skaluje się z wielkością danych wejściowych, ale nie jest to jedyny aspekt wydajności!
Zagnieżdżona pętla
Poniższa funkcja sprawdza, czy tablica ma duplikaty, biorąc każdy element, a następnie iteruje całą tablicę, aby sprawdzić, czy element tam jest
_Bool contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len; j++) {
if (i != j && array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
Pętla wewnętrzna wykonuje przy każdej iteracji pewną liczbę operacji, które są stałe dla n . Zewnętrzna pętla wykonuje również kilka stałych operacji i uruchamia wewnętrzną pętlę n razy. Sama zewnętrzna pętla jest uruchamiana n razy. Więc operacje w wewnętrznej pętli są uruchamiane n^2 razy, operacje w zewnętrznej pętli są uruchamiane n razy, a przypisanie do i jest wykonywane raz. Tak więc złożoność będzie podobna an^2 + bn + c , a ponieważ najwyższym terminem jest n^2 , notacja O(n^2) to O(n^2) .
Jak zapewne zauważyłeś, możemy ulepszyć algorytm, unikając wielokrotnego wykonywania tych samych porównań. Możemy zacząć od i + 1 w wewnętrznej pętli, ponieważ wszystkie elementy wcześniej będą już sprawdzone pod kątem wszystkich elementów tablicy, w tym tego o indeksie i + 1 . To pozwala nam porzucić czek i == j .
_Bool faster_contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
Oczywiście ta druga wersja wykonuje mniej operacji, a więc jest bardziej wydajna. Jak to się przekłada na notację Big-O? Cóż, teraz ciało wewnętrznej pętli jest uruchamiane 1 + 2 + ... + n - 1 = n(n-1)/2 razy. Jest to nadal wielomian drugiego stopnia, a więc nadal jest tylko O(n^2) . Wyraźnie obniżyliśmy złożoność, ponieważ z grubsza podzieliliśmy przez 2 liczbę operacji, które wykonujemy, ale wciąż jesteśmy w tej samej klasie złożoności, jak zdefiniowana przez Big-O. Aby obniżyć złożoność do niższej klasy, musielibyśmy podzielić liczbę operacji przez coś, co dąży do nieskończoności za pomocą n .
Przykład O (log n)
Wprowadzenie
Rozważ następujący problem:
L jest posortowaną listą zawierającą n liczb całkowitych ze znakiem ( n jest wystarczająco duża), na przykład [-5, -2, -1, 0, 1, 2, 4] (tutaj n ma wartość 7). Jeśli wiadomo, że L zawiera liczbę całkowitą 0, w jaki sposób można znaleźć indeks 0?
Podejście naiwne
Pierwszą rzeczą, która przychodzi na myśl, jest po prostu odczytanie każdego indeksu, aż do znalezienia 0. W najgorszym przypadku liczba operacji wynosi n , więc złożoność wynosi O (n).
Działa to dobrze dla małych wartości n , ale czy istnieje bardziej wydajny sposób?
Dychotomia
Rozważ następujący algorytm (Python3):
a = 0
b = n-1
while True:
h = (a+b)//2 ## // is the integer division, so h is an integer
if L[h] == 0:
return h
elif L[h] > 0:
b = h
elif L[h] < 0:
a = h
a i b są indeksami, między którymi można znaleźć 0. Za każdym razem wchodzimy do pętli, używamy indeks między i a b i użyć go, aby zawęzić obszar do przeszukania.
W najgorszym wypadku, musimy poczekać aż i a b są równe. Ale ile to wymaga operacji? Nie n, ponieważ za każdym razem wprowadzić pętlę podzielić odległość pomiędzy i a b o około dwa. Złożoność to raczej O (log n).
Wyjaśnienie
Uwaga: Kiedy piszemy „log”, mamy na myśli logarytm binarny lub log log base 2 (który napiszemy „log_2”). Ponieważ O (log_2 n) = O (log n) (możesz wykonać matematykę), użyjemy „log” zamiast „log_2”.
Nazwijmy x liczbę operacji: wiemy, że 1 = n / (2 ^ x).
Więc 2 ^ x = n, a następnie x = log n
Wniosek
W obliczu kolejnych podziałów (dwóch lub dowolnej liczby) pamiętaj, że złożoność jest logarytmiczna.
O (log n) typy algorytmów
Powiedzmy, że mamy problem z rozmiarem n. Teraz dla każdego kroku naszego algorytmu (który musimy zapisać) nasz pierwotny problem staje się w połowie jego poprzedniej wielkości (n / 2).
Na każdym kroku nasz problem staje się na pół.
| Krok | Problem |
|---|---|
| 1 | n / 2 |
| 2) | n / 4 |
| 3) | n / 8 |
| 4 | n / 16 |
Kiedy przestrzeń problemowa jest zmniejszona (tzn. Rozwiązana całkowicie), nie można jej już zmniejszyć (n staje się równa 1) po wyjściu z warunku sprawdzania.
Powiedzmy, że przy k-tym kroku lub liczbie operacji:
problem-rozmiar = 1
Ale wiemy, że na k-tym kroku nasz problem powinien wynosić:
problem-rozmiar = n / 2 k
Od 1 i 2:
n / 2 k = 1 lub
n = 2 tys
Weź dziennik po obu stronach
log e n = k log e 2
lub
k = log e n / log e 2
Za pomocą formuły log x m / log x n = log n m
k = log 2 n
lub po prostu k = log n
Teraz wiemy, że nasz algorytm może działać maksymalnie do log n, stąd złożoność czasu jest następująca
O (log n)
Bardzo prosty przykład w kodzie do obsługi powyższego tekstu to:
for(int i=1; i<=n; i=i*2)
{
// perform some operation
}
Więc teraz, jeśli ktoś zapyta cię, czy n wynosi 256, ile kroków, które wykona ta pętla (lub dowolny inny algorytm, który zmniejsza rozmiar problemu na pół), możesz bardzo łatwo obliczyć.
k = log 2 256
k = log 2 2 8 (=> log a a = 1)
k = 8
Innym bardzo dobrym przykładem podobnego przypadku jest algorytm wyszukiwania binarnego .
int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(arr[mid]==item)
return mid;
else if(arr[mid]<item)
low=mid+1;
else high=mid-1;
}
return –1;// Unsuccessful result
}