Big O, jak to obliczyć / przybliżyć?

Większość osób z dyplomem CS z pewnością wie, co stoi na Big O . Pomaga nam zmierzyć, jak dobrze skaluje się algorytm.

Ale jestem ciekaw, w jaki sposób możesz obliczyć lub zbliżenie złożoności algorytmów?

Zrobię co w mojej mocy, aby wyjaśnić to tutaj na prostych zasadach, ale ostrzegam, że ten temat zajmuje moim studentom kilka miesięcy, aby w końcu zrozumieć. Więcej informacji można znaleźć w rozdziale 2 książki Struktury i algorytmy danych w języku Java .

Nie ma mechanicznej procedury, która mogłaby zostać wykorzystana do uzyskania BigOh.

Jako „książka kucharska”, aby uzyskać BigOh z fragmentu kodu, musisz najpierw zdać sobie sprawę, że tworzysz formułę matematyczną, aby policzyć, ile kroków obliczeń zostanie wykonanych przy danych wejściowych o pewnym rozmiarze.

Cel jest prosty: porównać algorytmy z teoretycznego punktu widzenia, bez konieczności wykonywania kodu. Im mniejsza liczba kroków, tym szybszy algorytm.

Załóżmy na przykład, że masz ten fragment kodu:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Ta funkcja zwraca sumę wszystkich elementów tablicy, a my chcemy stworzyć formułę liczącą złożoność obliczeniową tej funkcji:

Number_Of_Steps = f(N)

Mamy więc f(N)funkcję zliczającą liczbę kroków obliczeniowych. Dane wejściowe funkcji to rozmiar struktury do przetworzenia. Oznacza to, że ta funkcja jest wywoływana, na przykład:

Number_Of_Steps = f(data.length)

Parametr Nprzyjmuje data.lengthwartość. Teraz potrzebujemy faktycznej definicji funkcji f(). Odbywa się to z kodu źródłowego, w którym każdy interesujący wiersz jest ponumerowany od 1 do 4.

Istnieje wiele sposobów obliczania BigOh. Od tego momentu zakładamy, że każde zdanie, które nie zależy od wielkości danych wejściowych, wymaga Cobliczeń o stałej liczbie.

Dodamy indywidualną liczbę kroków funkcji i ani deklaracja zmiennej lokalnej, ani instrukcja return nie zależy od wielkości datatablicy.

Oznacza to, że każdy wiersz 1 i 4 zajmuje C liczby kroków, a funkcja wygląda mniej więcej tak:

f(N) = C + ??? + C

Następną częścią jest zdefiniowanie wartości forinstrukcji. Pamiętaj, że liczymy liczbę kroków obliczeniowych, co oznacza, że ​​treść forinstrukcji jest wykonywana Nrazy. To tak samo jak dodawanie C, Nczasy:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Nie ma mechanicznej reguły liczącej, ile razy forwykonywana jest treść operacji , musisz ją policzyć, sprawdzając, co robi kod. Aby uprościć obliczenia, ignorujemy części inicjalizacji zmiennej, warunek i części przyrostowe forinstrukcji.

Aby uzyskać rzeczywistą wartość BigOh, potrzebujemy analizy asymptotycznej funkcji. Robi się to mniej więcej tak:

1. Zabierz wszystkie stałe C.
2. Od f()uzyskać polynomium w swojej standard form.
3. Podziel warunki wielomianu i posortuj je według tempa wzrostu.
4. Zachowaj ten, który rośnie, gdy się Nzbliża infinity.

Nasz f()ma dwa terminy:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Usuwanie wszystkich Cstałych i zbędnych części:

f(N) = 1 + N ^ 1

Ponieważ ostatni termin jest tym, który rośnie, gdy f()zbliża się do nieskończoności (pomyśl o limitach ), jest to argument BigOh, a sum()funkcja ma BigOh o wartości:

O(N)

Istnieje kilka sztuczek, aby rozwiązać niektóre trudne: użyj podsumowań, kiedy tylko możesz.

Na przykład ten kod można łatwo rozwiązać za pomocą podsumowań:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

Pierwszą rzeczą, o którą musisz zapytać, jest kolejność wykonania foo(). Choć zwykle tak jest O(1), musisz zapytać o to swoich profesorów. O(1)oznacza (prawie głównie) stałą C, niezależną od wielkości N.

forOświadczenie o jeden numer zdanie jest trudne. Podczas gdy indeks kończy się na 2 * N, przyrost jest wykonywany przez dwa. Oznacza to, że pierwszy forwykonywany jest tylko Nkrok i musimy podzielić liczbę przez dwa.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

Zdanie numer dwa jest jeszcze trudniejsze, ponieważ zależy od wartości i. Spójrz: indeks i przyjmuje wartości: 0, 2, 4, 6, 8, ..., 2 * N, a drugi forwykonuje się: N razy pierwszy, N - 2 drugi, N - 4 trzeci ... aż do etapu N / 2, na którym drugi fornigdy nie zostanie wykonany.

W formule oznacza to:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Ponownie liczymy liczbę kroków . I z definicji każde sumowanie powinno zawsze zaczynać się od jednego i kończyć liczbą większą lub równą niż jeden.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Zakładamy, że tak foo()jest O(1)i podejmuje Ckroki.)

Mamy tutaj problem: kiedy iwznosi się wartość w N / 2 + 1górę, wewnętrzne Podsumowanie kończy się liczbą ujemną! To niemożliwe i złe. Musimy podzielić podsumowanie na dwie części, ponieważ jest to najważniejszy moment, jaki izajmuje ta chwila N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Od momentu kluczowego momentu i > N / 2wnętrze fornie zostanie wykonane, a my zakładamy stałą złożoność wykonania C na jego ciele.

Teraz podsumowania można uprościć, stosując pewne reguły tożsamości:

1. Sumowanie (w od 1 do N) (C) = N * C
2. Sumowanie (w od 1 do N) (A (+/-) B) = Sumowanie (w od 1 do N) (A) (+/-) Sumowanie (w od 1 do N) (B)
3. Sumowanie (w od 1 do N) (w * C) = C * Sumowanie (w od 1 do N) (w) (C jest stałą, niezależnie od w)
4. Sumowanie (w od 1 do N) (w) = (N * (N + 1)) / 2

Stosowanie algebry:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

A BigOh to:

O(N²)

Duże O określa górną granicę złożoności algorytmu w czasie. Jest zwykle używany w połączeniu z przetwarzaniem zestawów danych (list), ale może być używany w innym miejscu.

Kilka przykładów użycia w kodzie C.

Powiedzmy, że mamy tablicę n elementów

int array[n];

Gdybyśmy chcieli uzyskać dostęp do pierwszego elementu tablicy, byłby to O (1), ponieważ nie ma znaczenia, jak duża jest tablica, zawsze uzyskanie tego samego czasu zajmuje tyle samo czasu.

x = array[0];

Jeśli chcielibyśmy znaleźć numer na liście:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

To byłoby O (n), ponieważ co najwyżej musielibyśmy przejrzeć całą listę, aby znaleźć nasz numer. Big-O to wciąż O (n), chociaż możemy znaleźć nasz numer przy pierwszej próbie przejścia przez pętlę raz, ponieważ Big-O opisuje górną granicę algorytmu (omega jest dla dolnej granicy, a theta jest dla ścisłej granicy) .

Kiedy dojdziemy do zagnieżdżonych pętli:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Jest to O (n ^ 2), ponieważ dla każdego przejścia zewnętrznej pętli (O (n)) musimy ponownie przejść przez całą listę, aby liczba mnożała się n, pozostawiając nam kwadrat n.

To ledwo zarysowanie powierzchni, ale kiedy dochodzi do analizy bardziej złożonych algorytmów, w grę wchodzi złożona matematyka obejmująca dowody. Mam nadzieję, że przynajmniej zapozna się z podstawami.

Chociaż wiedza, jak obliczyć czas Wielkiego O dla konkretnego problemu, jest przydatna, znajomość niektórych ogólnych przypadków może znacznie pomóc w podejmowaniu decyzji dotyczących algorytmu.

Oto niektóre z najczęstszych przypadków, które można znaleźć w http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) - Ustalanie, czy liczba jest parzysta czy nieparzysta; przy użyciu tabeli przeglądowej lub tabeli mieszającej o stałym rozmiarze

O (logn) - Wyszukiwanie elementu w posortowanej tablicy za pomocą wyszukiwania binarnego

O (n) - Znalezienie elementu na nieposortowanej liście; dodając dwie liczby n-cyfrowe

O (n ² ) - Mnożenie dwóch liczb n-cyfrowych przez prosty algorytm; dodanie dwóch macierzy n × n; sortowanie bąbelkowe lub wstawianie

O (n ³ ) - Mnożenie dwóch macierzy n × n przez prosty algorytm

O (c ⁿ ) - Znalezienie (dokładnego) rozwiązania problemu podróżnego sprzedawcy za pomocą programowania dynamicznego; ustalenie, czy dwa zdania logiczne są równoważne przy użyciu brutalnej siły

O (n!) - Rozwiązanie problemu podróżującego sprzedawcy za pomocą wyszukiwania z użyciem siły

O (n ⁿ ) - Często używane zamiast O (n!) W celu uzyskania prostszych wzorów dla asymptotycznej złożoności

Małe przypomnienie: big Onotacja służy do oznaczenia asymptotycznej złożoności (to znaczy, gdy rozmiar problemu rośnie do nieskończoności) i ukrywa stałą.

Oznacza to, że między algorytmem w O (n) a jednym w O (n ² ) najszybszym nie zawsze jest pierwszy (choć zawsze istnieje wartość n taka, że ​​dla problemów z rozmiarem> n pierwszy algorytm jest najszybszy).

Zauważ, że ukryta stała bardzo zależy od implementacji!

Ponadto w niektórych przypadkach środowisko wykonawcze nie jest funkcją deterministyczną wielkości n danych wejściowych. Weźmy na przykład sortowanie za pomocą szybkiego sortowania: czas potrzebny na posortowanie tablicy n elementów nie jest stały, ale zależy od początkowej konfiguracji tablicy.

Istnieją różne zawiłości czasowe:

• Najgorszy przypadek (zwykle najłatwiejszy do wykrycia, choć nie zawsze bardzo znaczący)

• Przeciętny przypadek (zwykle znacznie trudniejszy do zrozumienia ...)

• ...

Dobrym wprowadzeniem jest Wprowadzenie do analizy algorytmów autorstwa R. Sedgewicka i P. Flajoleta.

Jak mówisz, premature optimisation is the root of all evili (jeśli to możliwe) profilowanie naprawdę powinno zawsze być używane podczas optymalizacji kodu. Może nawet pomóc w określeniu złożoności algorytmów.

Widząc odpowiedzi tutaj, myślę, że możemy dojść do wniosku, że większość z nas rzeczywiście przybliża porządek algorytmu, patrząc na niego i kierując się zdrowym rozsądkiem zamiast obliczać go na przykład za pomocą metody mistrzowskiej, jak myśleliśmy na uniwersytecie. Powiedziawszy to, muszę dodać, że nawet profesor zachęcił nas (później), abyśmy się nad tym zastanowili , a nie tylko obliczali.

Chciałbym również dodać, jak to się robi dla funkcji rekurencyjnych :

załóżmy, że mamy funkcję typu ( kod schematu ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

która rekurencyjnie oblicza silnię podanej liczby.

Pierwszym krokiem jest próba określenia charakterystyki wydajności dla ciała funkcji tylko w tym przypadku, nic specjalnego nie jest robione w ciele, tylko pomnożenie (lub zwrócenie wartości 1).

Zatem wydajność dla ciała wynosi: O (1) (stała).

Następnie spróbuj ustalić to dla liczby połączeń rekurencyjnych . W tym przypadku mamy n-1 połączeń rekurencyjnych.

Zatem wydajność dla wywołań rekurencyjnych jest następująca: O (n-1) (kolejność wynosi n, gdy wyrzucamy nieistotne części).

Następnie połącz te dwa elementy i uzyskasz wydajność dla całej funkcji rekurencyjnej:

1 * (n-1) = O (n)

Piotr , aby odpowiedzieć na twoje poruszone problemy; metoda, którą tu opisuję, radzi sobie całkiem dobrze. Pamiętaj jednak, że wciąż jest to przybliżenie, a nie pełna matematycznie poprawna odpowiedź. Opisana tutaj metoda jest również jedną z metod, których nauczono nas na uniwersytecie, i jeśli dobrze pamiętam, została użyta w znacznie bardziej zaawansowanych algorytmach niż silnia, którą zastosowałem w tym przykładzie.
Oczywiście wszystko zależy od tego, jak dobrze możesz oszacować czas działania treści funkcji i liczbę wywołań rekurencyjnych, ale tak samo jest w przypadku innych metod.

Jeśli twój koszt jest wielomianem, po prostu zachowaj termin najwyższego rzędu, bez jego mnożnika. Na przykład:

O ((n / 2 + 1) * (N / 2)) = O (n = ² /4 + N / 2) = O (n = ² /4) = O (n = ² )

Pamiętaj, że to nie działa w przypadku nieskończonej serii. Nie ma jednego przepisu na ogólny przypadek, chociaż w niektórych powszechnych przypadkach obowiązują następujące nierówności:

O (log N ) <O ( N ) <O ( N log N ) <O ( N ² ) <O ( N ^k ) <O (e ⁿ ) <O ( n !)

Myślę o tym w kategoriach informacji. Każdy problem polega na nauce określonej liczby bitów.

Twoim podstawowym narzędziem jest koncepcja punktów decyzyjnych i ich entropia. Entropia punktu decyzyjnego jest średnią informacją, którą ci da. Na przykład, jeśli program zawiera punkt decyzyjny z dwiema gałęziami, jego entropia jest sumą prawdopodobieństwa każdej gałęzi razy log ₂ odwrotnego prawdopodobieństwa tej gałęzi. Tak dużo się uczysz, wykonując tę ​​decyzję.

Na przykład ifinstrukcja posiadająca dwie gałęzie, obie jednakowo prawdopodobne, ma entropię 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Więc jego entropia wynosi 1 bit.

Załóżmy, że przeszukujesz tabelę N elementów, na przykład N = 1024. To jest problem 10-bitowy, ponieważ log (1024) = 10 bitów. Jeśli więc możesz przeszukać go za pomocą instrukcji IF, które mają równie prawdopodobne wyniki, powinien podjąć 10 decyzji.

To właśnie zyskujesz dzięki wyszukiwaniu binarnemu.

Załóżmy, że przeprowadzasz wyszukiwanie liniowe. Patrzysz na pierwszy element i pytasz, czy to ten, którego chcesz. Prawdopodobieństwa to 1/1024, a 1023/1024, że tak nie jest. Entropia tej decyzji to 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * około 0 = około 0,01 bitu. Nauczyłeś się bardzo mało! Druga decyzja nie jest dużo lepsza. Właśnie dlatego wyszukiwanie liniowe jest tak wolne. W rzeczywistości jest to wykładnicza liczba bitów, której musisz się nauczyć.

Załóżmy, że indeksujesz. Załóżmy, że tabela jest wstępnie posortowana na wiele koszy i że używasz niektórych wszystkich bitów w kluczu, aby indeksować bezpośrednio do pozycji tabeli. Jeśli istnieje 1024 pojemników, entropia wynosi 1/1024 * log (1024) + 1/1024 * log (1024) + ... dla wszystkich 1024 możliwych wyników. Jest to 1/1024 * 10 razy 1024 wyników lub 10 bitów entropii dla tej jednej operacji indeksowania. Dlatego wyszukiwanie indeksowania jest szybkie.

Pomyśl teraz o sortowaniu. Masz N przedmiotów i masz listę. Dla każdego elementu należy wyszukać miejsce, w którym element znajduje się na liście, a następnie dodać go do listy. Sortowanie zajmuje więc około N-krotność liczby kroków podstawowego wyszukiwania.

Tak więc sortowanie oparte na decyzjach binarnych, które mają z grubsza jednakowo prawdopodobne wyniki, wymaga wykonania kroków O (N log N). Algorytm sortowania O (N) jest możliwy, jeśli jest oparty na wyszukiwaniu indeksowym.

Przekonałem się, że prawie wszystkie problemy z wydajnością algorytmu można rozpatrywać w ten sposób.

Zacznijmy od początku.

Przede wszystkim zaakceptuj zasadę, że pewne proste operacje na danych można wykonać w O(1)czasie, to znaczy w czasie niezależnym od wielkości danych wejściowych. Te prymitywne operacje w C składają się z

1. Operacje arytmetyczne (np. + Lub%).
2. Operacje logiczne (np. &&).
3. Operacje porównania (np. <=).
4. Operacje na strukturze dostępu (np. Indeksowanie tablic, takie jak A [i], lub wskaźnik po operatorze ->).
5. Proste przypisanie, takie jak kopiowanie wartości do zmiennej.
6. Wywołania funkcji bibliotecznych (np. Scanf, printf).

Uzasadnienie tej zasady wymaga szczegółowego przestudiowania instrukcji maszyny (prymitywnych kroków) typowego komputera. Każdą z opisanych operacji można wykonać za pomocą niewielkiej liczby instrukcji maszyny; często potrzebna jest tylko jedna lub dwie instrukcje. W konsekwencji kilka rodzajów instrukcji w C może być wykonywanych w O(1)czasie, to znaczy w pewnym stałym czasie niezależnym od danych wejściowych. Te proste obejmują

1. Instrukcje przypisania, które nie zawierają wywołań funkcji w ich wyrażeniach.
2. Przeczytaj oświadczenia.
3. Napisz instrukcje, które nie wymagają wywołań funkcji do oceny argumentów.
4. Instrukcje skoku przerywają, kontynuują, przechodzą i zwracają wyrażenie, w którym wyrażenie nie zawiera wywołania funkcji.

W C powstaje wiele pętli for, inicjując zmienną indeksu do pewnej wartości i zwiększając tę ​​zmienną o 1 za każdym razem wokół pętli. Pętla for kończy się, gdy indeks osiągnie pewien limit. Na przykład pętla for

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

używa zmiennej indeksu i. Inkrementuje i o 1 za każdym razem wokół pętli, a iteracje zatrzymują się, gdy osiągnę n - 1.

Jednak na razie skupmy się na prostej formie pętli for, w której różnica między wartościami końcowymi i początkowymi podzielona przez kwotę, o którą zmienna indeksowa jest zwiększana, mówi nam, ile razy ominęliśmy pętlę . Ta liczba jest dokładna, chyba że istnieją sposoby na wyjście z pętli za pomocą instrukcji skoku; w każdym razie jest to górna granica liczby iteracji.

Na przykład iteracja pętli for ((n − 1) − 0)/1 = n − 1 times, ponieważ 0 jest wartością początkową i, n - 1 jest najwyższą wartością osiągniętą przez i (tj. Gdy i osiągnie n-1, pętla zatrzymuje się i nie występuje iteracja z i = n− 1) i 1 dodaje się do i przy każdej iteracji pętli.

W najprostszym przypadku, gdy czas spędzony w ciele pętli jest taki sam dla każdej iteracji, możemy pomnożyć górną granicę dużego oh ciała dla liczby razy wokół pętli . Ściśle mówiąc, musimy dodać czas O (1) do zainicjowania indeksu pętli i czas O (1) do pierwszego porównania indeksu pętli z limitem , ponieważ testujemy jeszcze raz, niż obejdziemy pętlę. Jednakże, chyba że nie można wykonać pętli zero razy, czas zainicjowania pętli i jednorazowego przetestowania limitu jest terminem niskiego rzędu, który można usunąć za pomocą reguły sumowania.

Rozważmy teraz ten przykład:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Wiemy, że linia (1) wymaga O(1)czasu. Oczywiście, omijamy pętlę n razy, co możemy ustalić, odejmując dolną granicę od górnej granicy znalezionej na linii (1), a następnie dodając 1. Ponieważ ciało, linia (2) zajmuje czas O (1), możemy pominąć czas do przyrostu j oraz czas do porównania jz, z których oba są również O (1). Zatem czas przebiegu linii (1) i (2) jest iloczynem n i O (1) , co oznacza O(n).

Podobnie możemy ograniczyć czas działania zewnętrznej pętli składającej się z linii (2) do (4), czyli

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Ustaliliśmy już, że pętla linii (3) i (4) zajmuje czas O (n). Możemy zatem zaniedbać czas O (1), aby zwiększyć i i sprawdzić, czy i <n w każdej iteracji, stwierdzając, że każda iteracja zewnętrznej pętli zajmuje czas O (n).

Inicjalizacja i = 0 zewnętrznej pętli i (n + 1) test warunku i <n podobnie zajmują czas O (1) i można je pominąć. Na koniec obserwujemy, że n razy omijamy zewnętrzną pętlę, zajmując czas O (n) dla każdej iteracji, dając całkowity O(n^2)czas działania.

Bardziej praktyczny przykład.

Jeśli chcesz empirycznie oszacować kolejność kodu, nie analizując go, możesz zastosować szereg rosnących wartości n i czasu kodu. Wykreśl swoje czasy na skali dziennika. Jeśli kod to O (x ^ n), wartości powinny spaść na linii nachylenia n.

Ma to kilka zalet w porównaniu z samym studiowaniem kodu. Po pierwsze, możesz sprawdzić, czy jesteś w zakresie, w którym czas działania zbliża się do swojej asymptotycznej kolejności. Może się również okazać, że jakiś kod, który według ciebie był porządkiem O (x), jest tak naprawdę porządkiem O (x ^ 2), na przykład z powodu czasu spędzonego na wywołaniach biblioteki.

Zasadniczo rzeczą, która pojawia się w 90% przypadków, jest po prostu analiza pętli. Czy masz pojedyncze, podwójne, potrójne zagnieżdżone pętle? Masz czas pracy O (n), O (n ^ 2), O (n ^ 3).

Bardzo rzadko (chyba że piszesz platformę z rozbudowaną biblioteką podstawową (np. .NET BCL lub STL C ++) napotkasz wszystko, co jest trudniejsze niż tylko patrzenie na twoje pętle (dla instrukcji, podczas gdy goto, itp...)

Notacja Big O jest przydatna, ponieważ jest łatwa w obsłudze i ukrywa niepotrzebne komplikacje i szczegóły (w przypadku niektórych definicji niepotrzebnych). Jednym z fajnych sposobów obliczania złożoności algorytmów dzielenia i zdobywania jest metoda drzewa. Załóżmy, że masz wersję Quicksort z procedurą mediany, więc za każdym razem dzielisz tablicę na idealnie zrównoważone pod-tablice.

Teraz zbuduj drzewo odpowiadające wszystkim tablicom, z którymi pracujesz. W katalogu głównym masz oryginalną tablicę, katalog główny ma dwoje potomków, które są podobrazami. Powtarzaj tę czynność, dopóki na dole nie będzie tablic jednoelementowych.

Ponieważ możemy znaleźć medianę w czasie O (n) i podzielić tablicę na dwie części w czasie O (n), praca wykonana w każdym węźle to O (k), gdzie k jest rozmiarem tablicy. Każdy poziom drzewa zawiera (co najwyżej) całą tablicę, więc praca na poziomie wynosi O (n) (rozmiary podcieni sumują się do n, a ponieważ mamy O (k) na poziom, możemy to dodać) . W drzewie są tylko poziomy log (n), ponieważ za każdym razem zmniejszamy o połowę dane wejściowe.

Dlatego możemy górną granicę ilości pracy o O (n * log (n)).

Jednak Big O ukrywa pewne szczegóły, których czasami nie możemy zignorować. Rozważ obliczenie sekwencji Fibonacciego za pomocą

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

i załóżmy, że a i b to BigIntegers w Javie lub coś, co może obsłużyć dowolnie duże liczby. Większość ludzi powiedziałaby, że jest to algorytm O (n) bez wzdrygnięcia. Powodem jest to, że masz iteracje w pętli for, a O (1) działa po stronie pętli.

Ale liczby Fibonacciego są duże, n-ta liczba Fibonacciego jest wykładnicza in, więc po prostu przechowywanie przyjmie kolejność n bajtów. Wykonanie dodawania z dużymi liczbami całkowitymi zajmie O (n) ilość pracy. Tak więc łączna ilość pracy wykonanej w tej procedurze wynosi

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

Tak więc ten algorytm działa w czasie kwadratowym!

Myślę, że ogólnie mniej przydatny, ale ze względu na kompletność istnieje również Big Omega Ω , która określa dolną granicę złożoności algorytmu, i Big Theta Θ , która określa zarówno górną, jak i dolną granicę.

Podziel algorytm na części, dla których znasz dużą notację O, i połącz za pomocą dużych operatorów O. To jedyny znany mi sposób.

Aby uzyskać więcej informacji, sprawdź stronę Wikipedii na ten temat.

Znajomość używanych algorytmów / struktur danych i / lub szybka analiza zagnieżdżania iteracji. Trudność polega na tym, że wywołujesz funkcję biblioteki, być może wiele razy - często nie masz pewności, czy czasami wywołujesz funkcję niepotrzebnie, czy też jakiej implementacji używają. Być może funkcje biblioteczne powinny mieć miarę złożoności / wydajności, niezależnie od tego, czy jest to Big O, czy inna metryka, która jest dostępna w dokumentacji, a nawet IntelliSense .

Jeśli chodzi o „jak obliczyć” Big O, jest to część teorii złożoności obliczeniowej . W niektórych (wielu) szczególnych przypadkach możesz uzyskać prostą heurystykę (np. Mnożenie liczby pętli dla zagnieżdżonych pętli), szczególnie. kiedy wszystko, czego chcesz, to jakiekolwiek oszacowanie górnej granicy i nie masz nic przeciwko, jeśli jest to zbyt pesymistyczne - co, jak sądzę, prawdopodobnie jest tym, o co ci chodzi.

Jeśli naprawdę chcesz odpowiedzieć na pytanie dotyczące dowolnego algorytmu, najlepiej możesz zastosować teorię. Oprócz uproszczonej analizy „najgorszego przypadku” analiza amortyzowana jest bardzo przydatna w praktyce.

W pierwszym przypadku wewnętrzna pętla jest wykonywana n-irazy, więc całkowita liczba wykonań jest sumą iprzejścia od 0do n-1(ponieważ niższa, nie mniejsza niż lub równa) z n-i. Dostajesz w końcu n*(n + 1) / 2, więc O(n²/2) = O(n²).

Dla drugiej pętli iznajduje się pomiędzy 0i jest nuwzględniony dla zewnętrznej pętli; wtedy pętla wewnętrzna jest wykonywana, gdy jjest ściśle większa niż n, co jest wówczas niemożliwe.

Oprócz korzystania z metody master (lub jednej z jej specjalizacji) testuję algorytmy eksperymentalnie. Nie może to udowodnić, że osiągnięto określoną klasę złożoności, ale może zapewnić pewność, że analiza matematyczna jest odpowiednia. Aby pomóc w tym zapewnieniu, używam narzędzi pokrycia kodu w połączeniu z moimi eksperymentami, aby upewnić się, że wykonuję wszystkie przypadki.

Jako bardzo prosty przykład powiedz, że chciałeś przeprowadzić kontrolę poczytalności dotyczącą szybkości sortowania listy .NET Framework. Możesz napisać coś takiego, a następnie przeanalizować wyniki w programie Excel, aby upewnić się, że nie przekraczają krzywej n * log (n).

W tym przykładzie mierzę liczbę porównań, ale rozsądnie jest też zbadać rzeczywisty czas wymagany dla każdej wielkości próbki. Jednak musisz być jeszcze bardziej ostrożny, gdy tylko mierzysz algorytm, nie uwzględniając artefaktów z infrastruktury testowej.

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

Nie zapomnij również uwzględnić złożoności przestrzeni, która może być również powodem do niepokoju, jeśli ktoś ma ograniczone zasoby pamięci. Na przykład możesz usłyszeć, że ktoś chce stałego algorytmu przestrzeni, co w zasadzie mówi, że ilość miejsca zajmowanego przez algorytm nie zależy od żadnych czynników wewnątrz kodu.

Czasami złożoność może wynikać z tego, ile razy coś się nazywa, jak często wykonywana jest pętla, jak często przydzielana jest pamięć, i tak dalej jest inna część odpowiedzi na to pytanie.

Wreszcie, duże O może być użyte w najgorszym przypadku, najlepszym przypadku i przypadkach amortyzacji, gdzie ogólnie jest to najgorszy przypadek używany do opisania, jak zły może być algorytm.

Często pomijane jest oczekiwane zachowanie algorytmów. Nie zmienia Big-O twojego algorytmu , ale odnosi się do stwierdzenia „przedwczesna optymalizacja ...”

Oczekiwane zachowanie twojego algorytmu jest - bardzo głupie - jak szybko możesz oczekiwać, że Twój algorytm będzie działał na danych, które najprawdopodobniej zobaczysz.

Na przykład, jeśli szukasz wartości na liście, jest to O (n), ale jeśli wiesz, że większość list, które widzisz, ma swoją wartość z góry, typowe zachowanie algorytmu jest szybsze.

Aby naprawdę to ustalić, musisz być w stanie opisać rozkład prawdopodobieństwa „przestrzeni wejściowej” (jeśli musisz posortować listę, jak często ta lista będzie już posortowana? Jak często jest całkowicie odwracana? W jaki sposób często jest to najczęściej posortowane?) Nie zawsze jest to możliwe, że o tym wiesz, ale czasami tak jest.

świetne pytanie!

Zastrzeżenie: ta odpowiedź zawiera fałszywe stwierdzenia, patrz komentarze poniżej.

Jeśli używasz Big O, mówisz o najgorszym przypadku (więcej o tym, co to znaczy później). Dodatkowo istnieje kapitał theta dla przeciętnego przypadku i duża omega dla najlepszego przypadku.

Sprawdź tę stronę, aby uzyskać piękną formalną definicję Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) oznacza, że ​​istnieją stałe dodatnie c i k, takie że 0 ≤ f (n) ≤ cg (n) dla wszystkich n ≥ k. Wartości c i k muszą być ustalone dla funkcji f i nie mogą zależeć od n.

Ok, więc co teraz rozumiemy przez złożoność „najlepszego przypadku” i „najgorszego przypadku”?

Prawdopodobnie najlepiej to ilustrują przykłady. Na przykład, jeśli używamy wyszukiwania liniowego do znalezienia liczby w posortowanej tablicy, najgorszym przypadkiem jest decyzja o poszukiwaniu ostatniego elementu tablicy, ponieważ zajęłoby to tyle kroków, ile jest elementów w tablicy. Najlepszym wypadku będzie, gdy szukamy w pierwszym elemencie , ponieważ chcemy być wykonane po pierwszym czeku.

Istotą wszystkich tych przymiotników -złożoności jest to, że szukamy sposobu na wykres czasu, przez jaki hipotetyczny program biegnie do końca, pod względem wielkości poszczególnych zmiennych. Jednak w przypadku wielu algorytmów można argumentować, że nie ma czasu dla określonego rozmiaru danych wejściowych. Zauważ, że jest to sprzeczne z podstawowym wymogiem funkcji, każde wejście powinno mieć nie więcej niż jedno wyjście. Dlatego opracowaliśmy wiele funkcji opisujących złożoność algorytmu. Teraz, nawet jeśli wyszukiwanie tablicy o rozmiarze n może zająć różny czas w zależności od tego, czego szukasz w tablicy i proporcjonalnie do n, możemy stworzyć pouczający opis algorytmu przy użyciu najlepszego przypadku, średniej wielkości i najgorsze klasy.

Niestety jest to tak źle napisane i brakuje w nim wielu informacji technicznych. Ale miejmy nadzieję, że ułatwi to zastanowienie się nad klasami złożoności czasu. Kiedy już poczujesz się z nimi komfortowo, staje się prostą kwestią analizowania programu i szukania takich rzeczy, jak pętle for, które zależą od rozmiarów tablic i wnioskowania na podstawie struktur danych, jaki rodzaj danych wejściowych spowodowałby trywialne przypadki i jakie dane wejściowe spowodowałyby w najgorszych przypadkach.

Nie wiem, jak programowo rozwiązać ten problem, ale pierwszą rzeczą, którą ludzie robią, jest to, że próbkujemy algorytm dla pewnych wzorców w liczbie wykonanych operacji, powiedzmy 4n ^ 2 + 2n + 1 mamy 2 reguły:

1. Jeśli mamy sumę terminów, zostaje zachowany termin o największej stopie wzrostu, z pominięciem innych terminów.
   
2. Jeśli mamy iloczyn kilku czynników, stałe czynniki są pomijane.

Jeśli uprościć f (x), gdzie f (x) jest wzorem na liczbę wykonanych operacji ((4n ^ 2 + 2n + 1 wyjaśnione powyżej), otrzymujemy w tym przypadku dużą wartość O [O (n ^ 2) walizka]. Musiałoby to jednak uwzględniać interpolację Lagrange'a w programie, co może być trudne do wdrożenia. A jeśli prawdziwą dużą wartością O byłoby O (2 ^ n), a moglibyśmy mieć coś takiego jak O (x ^ n), więc ten algorytm prawdopodobnie nie byłby programowalny. Ale jeśli ktoś udowodni, że się mylę, daj mi kod. . . .

W przypadku kodu A zewnętrzna pętla będzie wykonywana n+1razy, czas „1” oznacza proces, który sprawdza, czy nadal spełniam wymaganie. A wewnętrzna pętla działa nrazy, n-2razy ... Tak więc 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

W przypadku kodu B, chociaż pętla wewnętrzna nie wkroczyłaby i nie wykona foo (), pętla wewnętrzna zostanie wykonana, ponieważ n razy zależy od czasu wykonania pętli zewnętrznej, czyli O (n)

Chciałbym wyjaśnić Big-O w nieco innym aspekcie.

Big-O ma po prostu porównać złożoność programów, co oznacza, jak szybko rosną one, gdy rosną nakłady, a nie dokładny czas, jaki poświęca się na działanie.

IMHO we wzorach big-O lepiej nie używać bardziej złożonych równań (możesz po prostu trzymać się tych na poniższym wykresie). Jednak nadal możesz użyć innej, bardziej precyzyjnej formuły (np. 3 ^ n, n ^ 3, .. .), ale więcej niż to może czasem wprowadzać w błąd! Więc lepiej, aby było to tak proste, jak to możliwe.

Chciałbym jeszcze raz podkreślić, że tutaj nie chcemy uzyskać dokładnej formuły dla naszego algorytmu. Chcemy tylko pokazać, jak rośnie, gdy rosną nakłady, i porównać z innymi algorytmami w tym sensie. W przeciwnym razie lepiej skorzystaj z różnych metod, takich jak benchmarking.