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

881

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?

sven
źródło
4
Może tak naprawdę nie musisz poprawiać złożoności algorytmu, ale przynajmniej powinieneś być w stanie go obliczyć, aby podjąć decyzję ...
Xavier Nodet
5
Znalazłem to bardzo jasne wyjaśnienie Big O, Big Omega i Big Theta: xoax.net/comp/sci/algorithms/Lesson6.php
Sam Dutton
33
-1: Westchnienie, kolejne nadużycie BigOh. BigOh jest tylko asymptotyczną górną granicą i może być używany do wszystkiego i nie jest związany tylko z CS. Mówienie o BigOh tak, jakby istniał jeden unikat, nie ma znaczenia (Algorytm czasu liniowego to także O (n ^ 2), O (n ^ 3) itp.). Mówienie, że pomaga nam to mierzyć efektywność, jest również mylące. A co z linkiem do klas złożoności? Jeśli interesują Cię tylko techniki obliczania czasów działania algorytmów, jakie to ma znaczenie?
34
Big-O nie mierzy wydajności; mierzy to, jak dobrze algorytm skaluje się z rozmiarem (może również dotyczyć innych rzeczy niż rozmiar, ale prawdopodobnie to nas tutaj interesuje) - i to tylko asymptotycznie, więc jeśli nie masz szczęścia, algorytm z „mniejszym” dużym- O może być wolniejsze (jeśli Big-O dotyczy cykli) niż inny, dopóki nie osiągniesz bardzo dużych liczb.
ILoveFortran
4
Wybór algorytmu na podstawie jego złożoności Big-O jest zwykle istotną częścią projektowania programu. Zdecydowanie nie jest to przypadek „przedwczesnej optymalizacji”, która w każdym razie jest nadużywaną selektywną wyceną.
user207421,

Odpowiedzi:

1480

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²)
vz0
źródło
6
@arthur To byłoby O (N ^ 2), ponieważ potrzebowałbyś jednej pętli do odczytania wszystkich kolumn i jednej do odczytania wszystkich wierszy określonej kolumny.
Abhishek Dey Das
@arthur: To zależy. To O(n)gdzie njest liczba elementów lub O(x*y)gdzie xi gdzie ysą wymiary tablicy. Big-oh jest „względne w stosunku do danych wejściowych”, więc zależy od tego, jaki jest twój wkład.
Kaczka Mooing
1
Świetna odpowiedź, ale naprawdę utknąłem. Jak sumowanie (od 1 do N / 2) (N) zmienia się w (N ^ 2/2)?
Parsa,
2
@ParsaAkbari Zasadniczo suma (i od 1 do a) (b) jest * b. To tylko kolejny sposób na powiedzenie b + b + ... (razy) + b = a * b (z definicji dla niektórych definicji mnożenia liczb całkowitych).
Mario Carneiro
Nie tak istotne, ale tylko w celu uniknięcia pomyłki, w tym zdaniu występuje drobny błąd: „indeks i przyjmuje wartości: 0, 2, 4, 6, 8, ..., 2 * N”. Indeks i faktycznie rośnie do 2 * N - 2, wówczas pętla się zatrzyma.
Albert
201

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.

DShook
źródło
Świetne wyjaśnienie! Więc jeśli ktoś powie, że jego algorytm ma złożoność O (n ^ 2), czy to oznacza, że ​​będzie używał zagnieżdżonych pętli?
Navaneeth KN
2
Nie bardzo, każdy aspekt, który prowadzi do n kwadratowych czasów, będzie uważany za n ^ 2
asyncwait
@NavaneethKN: Nie zawsze zobaczysz zagnieżdżoną pętlę, ponieważ wywołania funkcji mogą wykonywać> O(1)działać same. Na przykład w standardowych interfejsach API C bsearchjest z natury O(log n), strlenjest O(n)i qsortjest O(n log n)(technicznie nie ma żadnych gwarancji, a sam quicksort ma najgorszą złożoność przypadku O(n²), ale zakładając, że libcautor nie jest kretynem, jego średnia złożoność jest O(n log n)i używa strategia wyboru osi obrotu, która zmniejsza prawdopodobieństwo trafienia w O(n²)skrzynkę). I oba bsearchi qsortmoże być gorzej, jeśli funkcja komparator jest patologiczny.
ShadowRanger
95

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 2 ) - Mnożenie dwóch liczb n-cyfrowych przez prosty algorytm; dodanie dwóch macierzy n × n; sortowanie bąbelkowe lub wstawianie

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

O (c n ) - 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 n ) - Często używane zamiast O (n!) W celu uzyskania prostszych wzorów dla asymptotycznej złożoności

Giovanni Galbo
źródło
Dlaczego nie użyć, x&1==1aby sprawdzić dziwność?
Samy Bencherif,
2
@SamyBencherif: Byłby to typowy sposób sprawdzania (w rzeczywistości wystarczy testowanie x & 1, nie trzeba sprawdzać == 1; w C x&1==1jest oceniany jako x&(1==1) dzięki pierwszeństwu operatora , więc w rzeczywistości jest taki sam jak testowanie x&1). Myślę, że źle rozumiesz odpowiedź; jest tam średnik, a nie przecinek. Nie oznacza to, że potrzebujesz tabeli przeglądowej do testowania parzystego / nieparzystego, to znaczy, że zarówno parzyste / nieparzyste testowanie, jak i sprawdzanie tabeli przeglądowej to O(1)operacje.
ShadowRanger
Nie wiem o roszczeniu dotyczącym użycia w ostatnim zdaniu, ale ktokolwiek to robi, zastępuje klasę inną, która nie jest równoważna. Klasa O (n!) Zawiera, ale jest ściśle większa niż O (n ^ n). Rzeczywista równoważność to O (n!) = O (n ^ ne ^ {- n} sqrt (n)).
conditionalMethod
43

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 2 ) 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.

OysterD
źródło
3
W matematyce O (.) Oznacza górną granicę, a theta (.) Oznacza, że ​​masz granicę powyżej i poniżej. Czy definicja rzeczywiście różni się w CS, czy jest to zwykłe nadużycie notacji? Zgodnie z definicją matematyczną sqrt (n) jest jednocześnie O (n) i O (n ^ 2), więc nie zawsze jest tak, że istnieje n, po którym funkcja O (n) jest mniejsza.
Douglas Zare
28

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.

sven
źródło
Sven, nie jestem pewien, czy twój sposób oceny złożoności funkcji rekurencyjnej będzie działał w przypadku bardziej złożonych, takich jak wyszukiwanie od góry do dołu / sumowanie / coś w drzewie binarnym. Jasne, możesz podać prosty przykład i znaleźć odpowiedź. Ale sądzę, że musiałbyś zrobić matematykę dla rekurencyjnych?
Peteter,
3
+1 za rekursję ... Również ten jest piękny: „... nawet profesor zachęcił nas do myślenia ...” :)
TT_
Tak, to jest takie dobre. Wydaje mi się, że tak to wygląda, im wyższy termin wewnątrz O (..), tym więcej pracy wykonuje Twoja maszyna. Myślenie o czymś w związku z czymś może być przybliżeniem, ale są to również granice. Mówią tylko, w jaki sposób praca, którą należy wykonać, wzrasta, gdy zwiększa się liczba danych wejściowych.
Abhinav Gauniyal
26

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 = 2 /4 + N / 2) = O (n = 2 /4) = O (n = 2 )

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 2 ) <O ( N k ) <O (e n ) <O ( n !)

Marcelo Cantos
źródło
8
na pewno O (N) <O (NlogN)
jk.
22

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 2 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.

Mike Dunlavey
źródło
Łał. Czy masz jakieś pomocne referencje na ten temat? Uważam, że te rzeczy są dla mnie pomocne w projektowaniu / refaktoryzacji / debugowaniu programów.
Jesvin Jose,
3
@aitchnyu: Dla tego, co jest warte, napisałem książkę na ten temat i inne tematy. Już dawno się wyczerpał, ale kopie będą za rozsądną cenę. Próbowałem zdobyć GoogleBooki, ale w tej chwili trudno jest ustalić, kto jest właścicielem praw autorskich.
Mike Dunlavey,
21

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.

wprowadź opis zdjęcia tutaj

ajknzhol
źródło
Co jeśli instrukcja goto zawiera wywołanie funkcji? Coś w stylu step3: if (M.step == 3) {M = step3 (gotowe, M); } step4: if (M.step == 4) {M = step4 (M); } if (M.step == 5) {M = step5 (M); goto step3; } if (M.step == 6) {M = step6 (M); goto step4; } return cut_matrix (A, M); jak w takim razie obliczono by złożoność? czy byłoby to dodawanie czy mnożenie? biorąc pod uwagę, że krok 4 to n ^ 3, a krok 5 to n ^ 2.
Taha Tariq
14

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.

John D. Cook
źródło
Aby zaktualizować tę odpowiedź: en.wikipedia.org/wiki/Analysis_of_algorithms , ten link ma potrzebną formułę. Wiele algorytmów jest zgodnych z regułą mocy, jeśli tak, z 2 punktami czasowymi i 2 środowiskami uruchomieniowymi na maszynie, możemy obliczyć nachylenie na wykresie dziennika. Który jest a = log (t2 / t1) / log (n2 / n1), to dało mi wykładnik dla algorytmu w, O (N ^ a). Można to porównać z obliczeniami ręcznymi za pomocą kodu.
Christopher John
1
Cześć, ładna odpowiedź. Zastanawiałem się, czy znasz jakąś bibliotekę lub metodologię (na przykład pracuję z Pythonem / R) w celu uogólnienia tej metody empirycznej, co oznacza, jak dopasowanie różnych funkcji złożoności do zestawu danych o zwiększonej wielkości i sprawdzenie, które z nich są istotne. Dzięki
agenis,
10

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...)

Adam
źródło
1
Zależy od pętli.
kelalaka
8

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!


źródło
1
Nie powinieneś przejmować się sposobem przechowywania liczb, nie zmienia to faktu, że algorytm rośnie przy górnej granicy O (n).
mikek3332002
8

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ę.

Jaskółka oknówka
źródło
7

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.

Lasse V. Karlsen
źródło
7

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 .

Matt Mitchell
źródło
6

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.

Suma
źródło
6

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.

Emmanuel
źródło
5

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);
Eric
źródło
4

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.

JB King
źródło
4

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.

Baltimark
źródło
4

ś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.

Samy Bencherif
źródło
1
To jest niepoprawne. Duże O oznacza „górną granicę”, co nie jest najgorszym przypadkiem.
Samy Bencherif,
1
Jest powszechnym błędnym przekonaniem, że duże-O odnosi się do najgorszego przypadku. Jak O i Ω odnoszą się do najgorszego i najlepszego przypadku?
Bernhard Barker
1
To jest mylące. Big-O oznacza górną granicę dla funkcji f (n). Omega oznacza dolną granicę dla funkcji f (n). To wcale nie jest związane z najlepszym lub najgorszym przypadkiem.
Tasneem Haider
1
Możesz użyć Big-O jako górnej granicy dla najlepszego lub najgorszego przypadku, ale poza tym, tak, brak relacji.
Samy Bencherif
2

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. . . .

Gavriel Feria
źródło
2

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)

laynece
źródło
1

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.

wprowadź opis zdjęcia tutaj

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.

HmT
źródło