Czy jest to właściwa „reguła” do identyfikacji notacji „Big O” algorytmu?

29

Dowiedziałem się więcej o notacji Big O i tym, jak ją obliczyć na podstawie sposobu pisania algorytmu. Natknąłem się na interesujący zestaw „reguł” do obliczania algorytmów Notacja Big O i chciałem sprawdzić, czy jestem na dobrej drodze, czy daleko.

Duża notacja O: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Duża notacja O: N 2

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Notacja O: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Duża notacja O: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Czy moje przykłady i późniejsza notacja są poprawne? Czy są jakieś dodatkowe uwagi, o których powinienem wiedzieć?

Levi Hackwith
źródło
3
Nazwij to kciuka zamiast formuły i prawdopodobnie jesteś na dobrej drodze. Oczywiście, to całkowicie zależy od tego, co dokładnie robi „robić rzeczy”. Log (N) zazwyczaj pochodzi z algorytmów, które wykonują pewnego rodzaju partycjonowanie binarne / drzewiaste. Oto doskonały post na blogu na ten temat.
Daniel B
15
Nie ma czegoś takiego jak 2Nw notacji wielkiej-O.
vartec
15
@ JörgWMittag, ponieważ O (2n) = O (n) z definicji Big O
maniak zapadkowy
3
@ JörgWMittag: to naprawdę nie jest miejsce do trollingu.
vartec
3
@vartec - Nie sądzę, aby JörgWMittag celowo trollował. W moich ostatnich badaniach zauważyłem wiele nieporozumień między ścisłą notacją Big-O a „wspólnym językiem ojczystym”, który łączy Big-O, Theta i inne pochodne. Nie twierdzę, że powszechne użycie jest prawidłowe; po prostu to się często zdarza.

Odpowiedzi:

26

Formalnie notacja big-O opisuje stopień złożoności.

Aby obliczyć notację big-O:

  1. zidentyfikować formułę złożoności algorytmu. Powiedzmy na przykład, że dwie pętle z drugą są zagnieżdżone w środku, a następnie kolejne trzy pętle nie są zagnieżdżone:2N² + 3N
  2. usuń wszystko oprócz najwyższego terminu: 2N²
  3. usuń wszystkie stałe:

Innymi słowy, dwie pętle z drugą zagnieżdżoną w środku, a następnie kolejne trzy pętle nie zagnieżdżone to O (N²)

To oczywiście zakłada, że ​​to, co masz w swoich pętlach, to proste instrukcje. Jeśli masz na przykład sort()wewnątrz pętli, musisz pomnożyć złożoność pętli przez złożoność sort()implementacji, z której korzysta Twój podstawowy język / biblioteka.

vartec
źródło
Ściśle mówiąc, „usuń wszystkie stałe” zamieniłoby się 2N³w N. „usunięcie wszystkich stałych addytywnych i multiplikatywnych” byłoby bliższe prawdy.
Joachim Sauer
@JachachimSauer: N² = N * N, tam nie ma stałej.
vartec 10.04.13
@vartec: zgodnie z tym samym argumentem 2N = N+N.
Joachim Sauer
2
@JachachSSauer, twoje „ściśle mówiąc” jako absolutnie niekonwencjonalne. Zobacz en.wikipedia.org/wiki/Constant_(mathematics) . Mówiąc o wielomianach, „stała” zawsze odnosi się tylko do współczynników, a nie wykładników.
Ben Lee
1
@vartec, patrz mój komentarz powyżej. Twoje użycie „stałej” tutaj było absolutnie prawidłowe i konwencjonalne.
Ben Lee
6

Jeśli chcesz przeanalizować te algorytmy, musisz zdefiniować // dostuff, ponieważ to może naprawdę zmienić wynik. Załóżmy, że dostuff wymaga stałej liczby operacji O (1).

Oto kilka przykładów z tą nową notacją:

Dla twojego pierwszego przykładu, przejście liniowe: jest to poprawne!

NA):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Dlaczego jest liniowy (O (n))? W miarę dodawania do elementu (tablicy) dodatkowych elementów ilość wykonywanych operacji rośnie proporcjonalnie do liczby dodawanych elementów.

Jeśli więc potrzeba jednej operacji, aby zwiększyć liczbę całkowitą gdzieś w pamięci, możemy modelować pracę wykonywaną przez pętlę za pomocą f (x) = 5x = 5 dodatkowych operacji. Dla 20 dodatkowych elementów wykonujemy 20 dodatkowych operacji. Pojedynczy przebieg tablicy jest zwykle liniowy. Podobnie są algorytmy, takie jak sortowanie kubełkowe, które są w stanie wykorzystać strukturę danych do sortowania w jednym przejściu tablicy.

Twój drugi przykład również byłby poprawny i wygląda następująco:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

W takim przypadku dla każdego dodatkowego elementu w pierwszej tablicy musimy przetworzyć WSZYSTKIE j. Dodanie 1 do i faktycznie dodaje (długość j) do j. Masz więc rację! Ten wzorzec to O (n ^ 2) lub w naszym przykładzie jest to faktycznie O (i * j) (lub n ^ 2, jeśli i == j, co często ma miejsce w przypadku operacji macierzowych lub kwadratowej struktury danych.

Trzeci przykład to sytuacja, w której wszystko zmienia się w zależności od dostuff; Jeśli kod jest taki, jak napisano, a wykonywanie rzeczy jest stałe, w rzeczywistości jest to tylko O ​​(n), ponieważ mamy 2 przebiegi tablicy o rozmiarze n, a 2n zmniejsza się do n. Pętle znajdujące się na zewnątrz nie są kluczowym czynnikiem, który może wytworzyć kod 2 ^ n; oto przykład funkcji 2 ^ n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Ta funkcja ma wartość 2 ^ n, ponieważ każde wywołanie funkcji powoduje DWA dodatkowe wywołanie funkcji (Fibonacciego). Za każdym razem, gdy wywołujemy funkcję, ilość pracy, którą musimy wykonać, podwaja się! Rośnie to bardzo szybko, jak odcięcie głowy hydrze i za każdym razem wypuszczenie dwóch nowych!

Na przykład, jeśli używasz sortowania nlgn, takiego jak scalanie, masz rację, że ten kod będzie O (nlgn). Możesz jednak wykorzystać strukturę danych do opracowania szybszych sortowań w określonych sytuacjach (np. W znanym, ograniczonym zakresie wartości, np. Od 1 do 100). Masz jednak rację, myśląc, że dominuje kod najwyższego rzędu; więc jeśli sortowanie O (nlgn) znajduje się obok dowolnej operacji, która zajmuje mniej niż czas O (nlgn), całkowita złożoność czasu wyniesie O (nlgn).

W JavaScript (przynajmniej w Firefoksie) domyślnym sortowaniem w Array.prototype.sort () jest rzeczywiście MergeSort, więc patrzysz na O (nlgn) na swój ostateczny scenariusz.

Bryce Danz
źródło
Czy twój przykład Fibonacciego to Fibonacci? Wiem, że nie jest to sprzeczne z argumentem, który próbujesz przedstawić, ale nazwa może wprowadzać innych w błąd i dlatego może rozpraszać uwagę, jeśli tak naprawdę nie jest Fibonacciego.
Paul Nikonowicz
1

Drugi przykład (zewnętrzna pętla od 0 do n , wewnętrzna pętla od 0 do b ) to O ( nb ), a nie O ( n 2 ). Zasadą jest, że obliczasz coś n razy, a dla każdego obliczasz coś innego b razy, więc wzrost tej funkcji zależy wyłącznie od wzrostu n * b .

Twój trzeci przykład to po prostu O ( n ) - możesz usunąć wszystkie stałe, ponieważ nie rosną z n, a na tym właśnie polega notacja Big-O.

Jeśli chodzi o twój ostatni przykład, tak, twoja notacja Big-O na pewno będzie pochodzić z metody sortowania, która będzie, jeśli będzie oparta na porównaniu (jak to zwykle bywa), w najbardziej wydajnej formie, O ( n * logn ) .

Benjamin Brumfield
źródło
0

Przypomnij sobie, że jest to przybliżona reprezentacja czasu wykonywania. „Zasada praktyczna” jest przybliżona, ponieważ jest nieprecyzyjna, ale daje dobre przybliżenie pierwszego rzędu do celów oceny.

Rzeczywisty czas pracy zależeć będzie od ilości miejsca na stosie, szybkości procesora, zestawu instrukcji, użycia prefiksów lub operatorów przyrostowych po naprawie itp., Yadda. Właściwa analiza w czasie wykonywania pozwoli na określenie akceptacji, ale znajomość podstaw pozwala programować od samego początku.

Zgadzam się, że jesteś na dobrej drodze do zrozumienia, w jaki sposób Big-O jest racjonalizowany z podręcznika na praktyczne zastosowanie. To może być trudna przeszkoda do pokonania.

Szybkość asymptotycznego wzrostu nabiera znaczenia w dużych zestawach danych i dużych programach, dlatego w typowych przykładach pokazujesz, że poprawna składnia i logika nie jest tak ważna.

Bzdurny
źródło
-1

Big oh, z definicji oznacza: dla funkcji f (t) istnieje funkcja c * g (t), gdzie c jest dowolną stałą taką, że f (t) <= c * g (t) dla t> n gdzie n jest dowolną stałą, wówczas f (t) istnieje w O (g (t)). Jest to zapis matematyczny używany w informatyce do analizy algorytmów. Jeśli jesteś zdezorientowany, poleciłbym zajrzeć do relacji zamknięcia, w ten sposób możesz zobaczyć w bardziej szczegółowym widoku, w jaki sposób te algorytmy uzyskują te duże wartości.

Niektóre konsekwencje tej definicji: O (n) jest w rzeczywistości zbieżne z O (2n).

Istnieje również wiele różnych rodzajów algorytmów sortowania. Minimalna wartość Big-Oh dla sortowania porównawczego wynosi O (nlogn), jednak istnieje wiele rodzajów z gorszym big-oh. Na przykład sortowanie wyboru ma O (n ^ 2). Niektóre rodzaje nieporównywalne mogą mieć lepsze wartości o dużej wartości Sortowanie segmentowe, na przykład, ma O (n).

Jared C Miller
źródło