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

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 ²

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ć?

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: N²

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.

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.

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

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.

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