• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność obliczeniowa algorytmów

0 głosów
161 wizyt
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

0 głosów
odpowiedź 6 grudnia 2019 przez mmarszik Mądrala (7,370 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,370 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.
0 głosów
odpowiedź 6 grudnia 2019 przez MateuszRus Użytkownik (860 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 Użytkownik (860 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 Użytkownik (860 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.

Podobne pytania

0 głosów
1 odpowiedź 92 wizyt
pytanie zadane 1 listopada 2020 w Algorytmy przez wixy0 Gaduła (3,700 p.)
0 głosów
1 odpowiedź 75 wizyt
0 głosów
1 odpowiedź 102 wizyt
pytanie zadane 25 kwietnia 2020 w C i C++ przez Tacoo Nowicjusz (150 p.)
Porady nie od parady
Zadając pytanie postaraj się o poprawną pisownię i czytelne formatowanie tekstu.Kompozycja

85,145 zapytań

133,947 odpowiedzi

296,959 komentarzy

56,260 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...