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

Wielkie O daje górną granicę złożoności czasowej algorytmu. Zwykle jest używany w połączeniu z przetwarzaniem zestawów danych (List), ale może być używany gdzie indziej.

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

Powiedzmy, że mamy tablicę N elementów

int array[n];

Jeśli chcemy uzyskać dostęp do pierwszego elementu tablicy, to będzie to O(1), ponieważ nie ma znaczenia, jak duża jest tablica, uzyskanie pierwszego elementu zawsze zajmuje ten sam stały czas.

x = array[0];

Jeśli chciał znaleźć numer na liście:

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

Byłoby to O (n), ponieważ co najwyżej musielibyśmy przejrzeć całą listę, aby znaleźć nasz numer. Big-O jest nadal O (n), chociaż możemy znaleźć naszą liczbę pierwszą próbą i uruchomić przez pętlę raz, ponieważ Big-O opisuje górną granicę dla algorytmu (omega jest dla dolnej granicy i theta jest dla ciasnej granicy).

Gdy dotrzemy 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 pętli zewnętrznej(O (n) ) mamy musimy jeszcze raz przejrzeć całą listę, żeby mnożyć n, pozostawiając nas z N do kwadratu.

To jest ledwo zarysowania powierzchni, ale kiedy dostać się do analizy bardziej złożonych algorytmów skomplikowana matematyka z udziałem dowodów wchodzi w grę. Mam nadzieję, że przynajmniej zapoznasz się z podstawami.

Chociaż wiedza, jak rozgryźć wielki czas na konkretny problem, jest przydatna, znajomość niektórych ogólnych przypadków może pomóc w podejmowaniu decyzji w algorytmie.

Oto niektóre z najczęstszych przypadków, http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1)-Określenie, czy liczba jest parzysta lub nieparzysta; użycie tabeli Wyszukiwania o stałej wielkości lub tabeli hash

O(logn) - znalezienie elementu w posortowanej tablicy z wyszukiwanie binarne

O (n)-znalezienie pozycji na liście nieposortowanej; dodanie dwóch n-cyfrowych liczb

O (n²) - mnożenie dwóch liczb n-cyfrowych za pomocą prostego algorytmu; dodawanie dwóch macierzy n×n; sortowanie bąbelkowe lub sortowanie wstawiania

O (n³) - mnożenie dwóch macierzy n×n za pomocą algorytmu prostego

O (c ⁿ ) - znalezienie (dokładnego) rozwiązania problemu komiwojażera za pomocą programowania dynamicznego; określenie, czy dwa wyrażenia logiczne są równoważne za pomocą brute force

O(n!)- Rozwiązanie problemu komiwojażera za pomocą wyszukiwania brute-force

O(n ⁿ) - często używane zamiast O(N!) do wyprowadzenia prostszych formuł złożoności asymptotycznej

Małe przypomnienie: notacja big O jest używana do oznaczenia asymptotycznej złożoności (to znaczy, gdy rozmiar problemu rośnie do Nieskończoności), i ukrywa stałą.

Oznacza to, że pomiędzy algorytmem w O(n) i jednym w O (n²), najszybszy nie zawsze jest pierwszy (choć zawsze istnieje wartość n taka, że dla problemów o rozmiarze >n pierwszy algorytm jest najszybszy).

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

Również, w niektórych przypadkach, runtime nie jest deterministyczną funkcją size N wejścia. Weźmy sortowanie za pomocą szybkiego sortowania na przykład: czas potrzebny do sortowania tablicy N elementów nie jest stały, ale zależy od początkowej konfiguracji tablicy.

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

• najgorszy przypadek (zwykle najprostszy do zrozumienia, choć nie zawsze bardzo znaczący)

• Przeciętny przypadek (zwykle znacznie trudniejszy żeby się dowiedzieć...)

• ...

Dobrym wstępem jest Wprowadzenie do analizy algorytmów autorstwa R. Sedgewicka i P. Flajoleta.

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

Widząc tutaj odpowiedzi, myślę, że możemy wywnioskować, że większość z nas rzeczywiście przybliża kolejność algorytmu przez patrząc na niego i używa zdrowego rozsądku zamiast obliczać go, na przykład, metodą master, jak sądzono nam na Uniwersytecie. W tym miejscu muszę dodać, że nawet profesor zachęcał nas (później) do faktycznie myśleć o tym, zamiast tylko kalkulować.

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

Załóżmy, że mamy funkcję podobną do (kod schematu):

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

Który rekurencyjnie oblicza iloczyn danej liczby.

Pierwszym krokiem jest próba określenia charakterystyki działania dla ciała tylko funkcji w tym przypadku w ciele nie robi się nic specjalnego, tylko mnożenie (lub zwracanie wartości 1).

Więc wydajność dla ciała wynosi: O (1) (stała).

Następna próba i określ to dla liczby wywołań rekurencyjnych . W tym przypadku mamy N-1 wywołań rekurencyjnych.

Więc wydajność dla wywołań rekurencyjnych wynosi: O (n-1) (kolejność to n, ponieważ wyrzucamy nieistotne części).

Następnie połącz te dwa Razem i wtedy masz wydajność dla całej funkcji rekurencyjnej:

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

Piotr , aby odpowiedzieć Twoje poruszone kwestie; metoda, którą tutaj opisuję, właściwie radzi sobie z tym całkiem dobrze. Należy jednak pamiętać, że nadal jest to przybliżenie , a nie pełna matematycznie poprawna odpowiedź. Opisywana tutaj metoda jest też jedną z metod, których uczyliśmy się na uniwersytecie i o ile dobrze pamiętam była stosowana dla znacznie bardziej zaawansowanych algorytmów niż ta, którą zastosowałem w tym przykładzie.
Oczywiście wszystko zależy od tego, jak dobrze można oszacować czas działania ciała funkcji i liczbę wywołań rekurencyjnych, ale jest to tak samo prawdziwe dla inne metody.

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

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

To nie działa dla serii nieskończonych, pamiętaj o tym. Nie ma jednego przepisu na przypadek ogólny, choć w niektórych typowych przypadkach stosuje się następujące nierówności:

O (log N) N) N log N ) N²) N^k ) n) n!)

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

Twoim podstawowym narzędziem jest pojęcie punktów decyzyjnych i ich entropii. Entropia punktu decyzyjnego jest średnią informacją, jaką ci da. Na przykład, jeśli program zawiera punkt decyzyjny z dwoma gałęziami, to Entropia jest sumą prawdopodobieństwa każdej gałęzi razy log₂ odwrotnego prawdopodobieństwa tej gałęzi. Tyle można się nauczyć przez wykonanie tej decyzji.

Na przykład twierdzenie if mające 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. Jego Entropia wynosi 1 bit.

Załóżmy, że przeszukujesz tabelę N elementów, np. N = 1024. Jest to problem 10-bitowy, ponieważ log(1024) = 10 bitów. Jeśli więc możesz przeszukać go za pomocą twierdzeń IF, które mają równie prawdopodobne wyniki, powinieneś podjąć 10 decyzji.

To jest to, co dostajesz z binary Szukaj.

Załóżmy, że wykonujesz wyszukiwanie liniowe. Patrzysz na pierwszy element i pytasz, czy to ten, którego chcesz. Prawdopodobieństwo wynosi 1/1024, że jest i 1023/1024, że nie jest. Entropia tej decyzji wynosi 1/1024 * log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * około 0 = około .01 bit. Niewiele się nauczyłeś! Druga decyzja nie jest o wiele lepsza. Dlatego wyszukiwanie liniowe jest tak powolne. W rzeczywistości jest wykładnicza w liczbie bitów, które trzeba ucz się.

Załóżmy, że robisz indeksowanie. Załóżmy, że tabela jest wstępnie posortowana na wiele pojemników i używasz niektórych wszystkich bitów w kluczu do indeksowania bezpośrednio do pozycji tabeli. Jeśli jest 1024 * log(1024) + 1/1024 * log(1024) + ... dla wszystkich 1024 możliwych wyników. Jest to 1/1024 * 10 razy 1024 wyników, czyli 10 bitów entropii dla tej jednej operacji indeksowania. Dlatego wyszukiwanie indeksujące jest szybkie.

Tak więc sortowanie oparte na decyzjach binarnych, które mają mniej więcej równie prawdopodobne wyniki, zajmuje około O(N log N) kroków. Algorytm sortowania O(N) jest możliwy, jeśli opiera się na wyszukiwaniu indeksującym.

Odkryłem, że prawie wszystkie problemy z wydajnością algorytmiczną można rozpatrywać w ten sposób.

Zacznijmy od początku.

Przede wszystkim przyjmij zasadę, że pewne proste operacje na danych mogą być wykonywane w czasie O(1), czyli 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ównawcze (np.
4. operacje dostępu do struktury (np. indeksowanie tablic jak [i] , czy wskaźnik fol- z operatorem ->).
5. proste przypisanie, takie jak skopiowanie wartości do zmiennej.
6. wywołania funkcji bibliotecznych (np. scanf, printf).

Uzasadnienie tej zasady wymaga szczegółowego przestudiowania instrukcji maszynowych (prymitywnych kroków) typowego komputera. Każda z opisanych operacji może być wykonana za pomocą niewielkiej liczby instrukcji maszynowych; często potrzebna jest tylko jedna lub dwie instrukcje. W konsekwencji, kilka rodzajów polecenia w C mogą być wykonywane w O(1) czasie, czyli w pewnej stałej ilości czasu niezależnej od wejścia. Te proste obejmują

1. polecenia przypisania, które nie zawierają wywołań funkcji w wyrażeniach.
2. przeczytaj Oświadczenia.
3. zapisuje polecenia, które nie wymagają wywołań funkcji do oceny argumentów.
4. wyrażenia jump break, continue, goto I return, gdzie wyrażenie nie zawiera wywołania funkcji.

W C, wiele pętli for powstaje przez zainicjalizowanie zmiennej indeksu do pewnej wartości i zwiększenie tej zmiennej o 1 za każdym razem wokół pętli. Pętla for kończy się, gdy indeks osiąga pewien limit. Na przykład, for-loop

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. zwiększa i o 1 za każdym razem wokół pętli, a iteracje zatrzymaj się, gdy dotrę do n-1.

Jednak na razie skup się na prostej postaci for-loop, gdzie różnica między wartościami końcowymi i początkowymi, dzielona przez ilość, o jaką zmienna indeksu jest zwiększana, mówi nam ile razy obejdziemy pętlę . Liczba ta jest dokładna, chyba że istnieją sposoby wyjścia z pętli za pomocą instrukcji jump; Jest to górna granica liczby iteracji w każdym przypadku.

Na przykład iteracje 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. osiąga n-1, pętla zatrzymuje się i nie występuje iteracja z i = N-1), A 1 jest dodawany do i w każda iteracja pętli.

W najprostszym przypadku, gdzie czas spędzony w ciele pętli jest taki sam dla każdego iteracji, możemy pomnożyć wielką-oh górną granicę dla ciała przez liczbę czasy wokół pętli . Ściśle mówiąc, musimy dodać o(1) czas, aby zainicjować indeks pętli i o(1) czas na pierwsze porównanie indeksu pętli z limit , ponieważ testujemy jeszcze raz, niż objeżdżamy pętlę. Jednak, chyba że możliwe jest wykonanie pętli zero razy, Czas inicjalizacji pętli i testowania limit once jest terminem niskiego rzędu, który może zostać upuszczony przez regułę sumowania.

Rozważ teraz ten przykład:

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

Wiemy, że linia (1) zajmuje O(1) czas. Oczywiście objeżdżamy pętlę n razy, jak możemy określić poprzez odjęcie dolnej granicy od górnej granicy znalezionej na linii (1) a następnie dodanie 1. Ponieważ ciało, linia (2), zajmuje O(1) czas, możemy zaniedbać czas na zwiększenie j i czas porównać j Z n, z których oba są również O (1). Tak więc czas działania linii (1) i (2) jest iloczynem N I O(1) , czyli O(n).

Podobnie możemy związać czas działania pętli zewnętrznej 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). W ten sposób możemy zaniedbać czas O(1), Aby zwiększyć i i sprawdzić, czy i

Inicjalizacja i = 0 pętli zewnętrznej i (n + 1)testu St warunku i O(n^2) Czas trwania.

Jeśli chcesz empirycznie oszacować kolejność kodu, zamiast analizować kod, możesz trzymać się szeregu rosnących wartości n i czasu kodu. Wykreśl swój czas na skali dziennika. Jeśli kod jest 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 zobaczyć, czy jesteś w zakresie, w którym czas realizacji zbliża się do jego asymptotycznego porządku. Ponadto, może się okazać, że jakiś kod, który thought was order O (x) to tak naprawdę order O (x^2), na przykład ze względu na czas spędzony w wywołaniach biblioteki.

Zasadniczo rzecz, która pojawia się w 90% czasu, to tylko analiza pętli. Czy masz pojedyncze, podwójne, potrójne zagnieżdżone pętle? Masz O(n), O(N^2), O (N^3) Czas pracy.

Bardzo rzadko (chyba że piszesz platformę z rozbudowaną biblioteką bazową (jak na przykład. NET BCL lub STL C++) napotkasz coś trudniejszego niż tylko patrzenie na pętle (dla poleceń, while, goto itp.)...)

Rozbij algorytm na kawałki, dla których znasz notację big O i połącz za pomocą operatorów big O. Tylko tak wiem.

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

Notacja Big O jest przydatna, ponieważ jest łatwa w obsłudze i ukrywa niepotrzebne komplikacje i szczegóły(dla pewnej definicji niepotrzebnych). Jednym z miłych sposobów na wypracowanie złożoności algorytmów dzielenia i zdobywania jest metoda drzewa. Załóżmy, że masz wersję quicksort z procedurą medianą, więc za każdym razem dzielisz tablicę na idealnie zrównoważone podparyski.

Teraz zbuduj drzewo odpowiadające wszystkim tablicom, z którymi pracujesz. W katalogu głównym masz oryginalną tablicę, korzeń ma dwoje dzieci, które są subarraysami. Powtórz to, dopóki nie będziesz mieć tablic pojedynczych elementów na dole.

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

W związku z tym możemy upper bound ilość pracy przez O(N * log(n)).

Jednak Big O ukrywa pewne szczegóły, których czasami nie możemy zignorować. Rozważmy obliczenie ciągu Fibonacciego z

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

I załóżmy, że a i b są Bigintegerami w Javie lub czymś, co może obsługiwać dowolnie duże liczby. Większość ludzi powie, że jest to algorytm O(n) bez wzdęcia. Rozumowanie jest takie, że masz N iteracji w for loop I O(1) Wykonaj z boku pętlę.

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

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

Więc ten algorytm działa w czasie quadradic!

Znajomość algorytmów / struktur danych, których używam i / lub szybka analiza zagnieżdżania iteracji. Trudność polega na tym, że wywołujesz funkcję biblioteczną, prawdopodobnie wielokrotnie - często możesz być pewien, czy niepotrzebnie ją wywołujesz lub jakiej implementacji używa. Może funkcje biblioteczne powinny mieć miarę złożoności/efektywności, czy to Big O, czy jakiś inny metryk, który jest dostępny w dokumentacji lub nawet IntelliSense .

Mniej użyteczne ogólnie, myślę, ale ze względu na kompletność istnieje również Big Omega Ω , która definiuje dolną granicę złożoności algorytmu, oraz Big Theta Θ, która definiuje zarówno górną, jak i dolną granicę.

Co do "jak obliczyć" Duże O, jest to część teorii złożoności obliczeniowej . W niektórych (wielu) szczególnych przypadkach może pojawić się prosta heurystyka (np. mnożenie liczby pętli dla zagnieżdżonych pętli), esp. kiedy wszystko, co chcesz, to jakieś szacunki górnej granicy i nie masz nic przeciwko, jeśli jest to zbyt pesymistyczne - co myślę, że jest to prawdopodobnie to, o co twoje pytanie.

Jeśli naprawdę chcesz odpowiedzieć na pytanie dla dowolnego algorytmu, najlepiej jest zastosować teoria. Poza uproszczoną analizą "najgorszego przypadku" znalazłem analizę amortyzowaną bardzo przydatną w praktyce.

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

Dla drugiej pętli, i znajduje się pomiędzy 0 i n włączone dla zewnętrznej pętli; wtedy pętla wewnętrzna jest wykonywana, gdy j jest ściśle większa niż n, co jest wtedy niemożliwe.

Oprócz stosowania metody master (lub jednej z jej specjalizacji), testuję eksperymentalnie moje algorytmy. To nie może udowodnić, że dana klasa złożoności jest osiągnięta, ale może zapewnić pewność, że analiza matematyczna jest odpowiednia. Aby pomóc z tym zapewnieniem, używam narzędzi pokrycia kodu w połączeniu z moimi eksperymentami, aby upewnić się, że wykonuję wszystkie przypadki.

Jako bardzo prosty przykład powiedzmy, że chciałeś sprawdzić stan zdrowia psychicznego na prędkości sortowanie listy. NET framework. Możesz napisać coś takiego jak poniżej, a następnie przeanalizować wyniki w programie Excel, aby upewnić się, że nie przekroczyły krzywej n*log(N).

W tym przykładzie mierzę liczbę porównań, ale rozsądne jest również zbadanie rzeczywistego czasu wymaganego dla każdej wielkości próbki. Jednak musisz być jeszcze bardziej ostrożny, że po prostu mierzysz algorytm i nie uwzględniasz 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ż pozwolić na złożoność 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 algorytmu stałej przestrzeni, który jest w zasadzie sposobem na powiedzenie, ż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ęć itd. kolejna część odpowiedzi na to pytanie.

Wreszcie, big O może być używany dla najgorszych przypadków, najlepszych przypadków i przypadków amortyzacji, gdzie ogólnie jest to najgorszy przypadek, który jest używany do opisania, jak zły może być algorytm.

To, co często jest pomijane, to oczekiwane zachowanie Twoich algorytmów. to 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 twoje wartość z góry, typowe zachowanie algorytmu jest szybsze.

Aby naprawdę to zrobić, musisz być w stanie opisać rozkład prawdopodobieństwa swojej " przestrzeni wejściowej "(jeśli chcesz posortować listę, jak często ta lista będzie już posortowana? jak często jest to całkowicie odwrócone? jak często jest to najczęściej sortowane?) Nie zawsze jest to możliwe, że to wiesz, ale czasami tak.

Świetne pytanie!

Jeśli używasz Dużego O, mówisz o gorszym przypadku (więcej o tym, co to oznacza później). Dodatkowo istnieje duże theta dla przeciętnego przypadku i duża omega dla najlepszego przypadku.

Sprawdź tę stronę dla pięknej formalnej definicji Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

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

Ok, więc co rozumiemy przez" najlepszy przypadek "i" najgorszy przypadek " kompleksów?

Jest to prawdopodobnie najlepiej zilustrowane przykładami. Na przykład, jeśli używamy wyszukiwania liniowego, aby znaleźć liczbę w posortowanej tablicy, to najgorszy przypadek jest wtedy, gdy zdecydujemy się wyszukać ostatni element tablicy, ponieważ wymagałoby to tyle kroków, ile elementów w tablicy jest. The best case byłoby wtedy, gdy szukamy pierwszego elementu, ponieważ skończylibyśmy po pierwszym sprawdzeniu.

Sens tych wszystkich przymiotników-złożoności przypadków Polega na tym, że szukamy sposobu na wykresowanie czasu, przez jaki hipotetyczny program biegnie do końca pod względem wielkości poszczególnych zmiennych. Jednak dla wielu algorytmów można argumentować, że nie ma ani jednego czasu dla określonego rozmiaru wejścia. Zauważ, że jest to sprzeczne z podstawowym wymogiem funkcja, każde wejście powinno mieć nie więcej niż jedno wyjście. Więc wymyślamy wiele funkcji opisujących złożoność algorytmu. Teraz, nawet jeśli wyszukiwanie tablicy o rozmiarze n może zająć różne ilości czasu w zależności od tego, czego szukasz w tablicy i w zależności proporcjonalnie do n, możemy stworzyć informacyjny opis algorytmu za pomocą klas best-case, average-case i worst-case.

Sorry to jest tak źle napisane i brakuje mu wiele technicznych informacje. Ale mam nadzieję, że ułatwi to myślenie o klasach złożoności czasu. Gdy poczujesz się z tym komfortowo, staje się to prostą sprawą parsowania przez twój program i szukania rzeczy takich jak pętle for, które zależą od rozmiarów tablic i rozumowania opartego na Twoich strukturach danych, jakiego rodzaju dane wejściowe spowodowałyby trywialne przypadki, a jakie dane wejściowe spowodowałyby najgorsze przypadki.

Dla kodu a, zewnętrzna pętla będzie wykonywana przez n + 1 razy, Czas " 1 " oznacza proces, który sprawdza, czy i nadal spełnia wymagania. A wewnętrzna pętla działa n razy,N-2 razy.... Zatem 0+2+..+(n-2)+n= (0+n) (n + 1)/2= O(n2).

Dla kodu B, chociaż wewnętrzna pętla nie wchodzi i nie wykonuje foo (), wewnętrzna pętla będzie wykonywana przez n razy w zależności od czasu wykonania zewnętrznej pętli, który wynosi O(N)

Nie wiem jak to programowo rozwiązać, ale pierwszą rzeczą, jaką 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, termin o największej szybkości wzrostu jest zachowany, z pominięciem innych terminów.
   
2. Jeśli mamy iloczyn kilku czynników omijamy czynniki stałe.

Jeśli uprościmy f (x), gdzie f (x) jest wzorem dla liczby operacje wykonane, (4N^2 + 2n + 1 wyjaśnione powyżej), otrzymujemy wartość big-O [O (n^2) w tym przypadku]. Musiałoby to jednak uwzględniać interpolację Lagrange ' a w programie, która może być trudna do zaimplementowania. A co jeśli prawdziwa wartość big-O to O (2^n), i możemy 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 . . . .