Złożoność obliczeniowa algorytmów

pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)

Cześć,

Potrzebuję zapisać złożoność obliczeniową trzech różnych algorytmów:

function znajdzNajw($tab, $comment){
    $max1 = $tab[0];
    $max2 = $tab[1];
    
    for($i = 2; $i < count($tab); $i++){
        $max1 >= $max2 ? ($tab[$i] > $max2 ? $max2 = $tab[$i] : $max2 = $max2) : ($tab[$i] > $max1 ? $max1 = $tab[$i] : $max1 = $max1);
    }
    
    $najw = array($max1, $max2);
    return wyswietlPare($najw, $comment);
}

function znajdzNajm($tab, $comment){
    $min1 = $tab[0];
    $min2 = $tab[1];
    
    for($i = 2; $i < count($tab); $i++){
        $min1 > $min2 ? ($min1 > $tab[$i] ? $min1 = $tab[$i] : $min1 = $min1) : ($min2 > $tab[$i] ? $min2 = $tab[$i] : $min2 = $min2);
    }
    
    $najm = array($min1, $min2);
    return wyswietlPare($najm, $comment); 
}

function sortujTab($tab){
    
    for($i = 0; $i < count($tab); $i++){
        for($j = 0; $j < count($tab) - 1; $j++){
            if($tab[$j] > $tab[$j + 1]){
                $tmp = $tab[$j + 1];
                $tab[$j + 1] = $tab[$j];
                $tab[$j] = $tmp;
            }
        }
    }
    
    return $tab;
}

Czy złożonością obliczeniową dla funkcji:

znajdzNajw i znajdzNajm to O(N)

sortujTab to O(N^2)

2 odpowiedzi

odpowiedź 6 grudnia 2019 przez mmarszik Mądrala (7,390 p.)

Trudno powiedzieć, do czego to potrzebujesz? Jak do praktycznego zadania, to najlepiej zmierzyć czasy. Jak do teoretycznego, to najlepiej algorytm zaprezentować w metakodzie, mój ulubiony meta-kod jest taki jak w książce Cormena.

Pozdrrawiam

komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

W zasadzie to nie bardzo wiem do czego to potrzebuje.

Mam w pracy domowej, że oprócz schematu blokowego, punktowego trzeba jeszcze zapisać złożoność obliczeniową dla tych funkcji.

komentarz 6 grudnia 2019 przez mmarszik Mądrala (7,390 p.)

Zależy od implementacji w danej wersji danego języka programowania i biblioteki. Chyba że czas jednej instrukcji przyjmiesz równy jeden, nie ważne czy count liczy ilość elementów czy ma gdzieś zapamiętaną tę ilość. Różnice też mogą wynikać z tablic, mogą być tablicami skojarzeniowymi zrealizowanymi jako drzewa, jako hash-table, albo jako liniowe tablice.

Ja w praktyce mierzę czasy, a teoretycznie można rozważać na jakimś dobrze zdefiniowanym modelu obliczeń, jak to np. jest w książce Cormena.

odpowiedź 6 grudnia 2019 przez MateuszRus Obywatel (1,060 p.)

Cześć, zerknij tu. Pisałem trochę na temat złożoności i może Ci to jakoś pomoże! :)

LINK

komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

Hej,

Widziałem, czytałem - jako tako rozumiem o czym tam jest napisane.

Jednakże od praktycznej strony mam tyle pytań, że nie wiem od czego zacząć. eh

komentarz 6 grudnia 2019 przez MateuszRus Obywatel (1,060 p.)

Pytaj tu albo prywatnie :)

komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)

Na początku to chciałbym wiedzieć czy jeśli mamy pętle for + 2 operacje przypisania poza pętlą for to jest to:

O(N) czy O(N+2) ?

komentarz 6 grudnia 2019 przez MateuszRus Obywatel (1,060 p.)

N+2.

N to ilość iteracji pętli, natomiast każde przypisanie to dodanie 1. N + 1 + 1 daje N + 2.

Jeżeli następuje na koniec metody jeszcze RETURN, to wtedy on też jest osobną operacją i złożoność będzie wynosić N + 3.

Operacje przypisania nie wpływają aż tak na złożoność algorytmu jak samo N, czyli ilość elementów tablicy, po których iterujemy. Niezależnie, czy w operacji przypisania dasz na przykład wartość liczbową równą 10 czy 10000 to nie wpłynie to na wydajność. Inaczej będzie z wielkością tablicy po której iterujesz. :) jeżeli będzie ona 10 elementowa to pętla wykona się dużo szybciej niż przy tablicy z 10000 elementami.